[Haskell] Re: how to write a list builder? fixpoint?

oleg at pobox.com oleg at pobox.com
Tue Jun 8 17:12:17 EDT 2004


Ben Yu wrote:

> I'm new to haskell, new to this group, don't even know what this
> "cafe" refers to. Is there a special place for discussing further
> details?

Yes, http://haskell.org/mailman/listinfo/haskell-cafe

>Similarly, a builder can be built for binary functions like addToFM.

Here's a bit more general variant of it:

> class Builder2 c a b r | r -> a where
>   build2 :: (a->b->c a b->c a b) -> c a b -> a -> b -> r
> instance Builder2 c k v (c k v) where
>   build2 acc seed k v = acc k v seed
> instance Builder2 c a b r => Builder2 c a b (a->b->r) where
>   build2 acc seed a b x y = build2 acc (acc a b seed) x y
>
> newtype AL a b = AL [(a,b)] deriving Show
>
> test1::AL String Bool
> test1 = build2 (\x y (AL l) -> AL $ (x,y):l) (AL []) "a" True "b" False
>
> test2:: FiniteMap String Bool
> test2 = build2 (\x y m -> addToFM m x y) emptyFM "a" True "b" False "c" True

The function build2 not only has the variable number of
arguments. These arguments don't even have to be of the same type.


> However, I don't quite like having to say buildl (1::Int). If I can say
> [1,2,3], which types to Num a => [a], why can't I say buildl 1 2 3 which
> also types to Num a => [a]?

[1,2,3] is a syntactic sugar for 1:(2:(3:[])). The operator (:) has
the type
	(:) :: forall a. a -> [a] -> [a]
Since (:) is actually a function, the type of the result (which is
[a]->[a]) is unambiguously determined by the type of the argument,
'a'. Informally, the type of a function has a functional dependency. 

The function build' is a member of a class such that the type of the
result of build' unambiguously determines the type of the
argument. Note the reverse implication. Therefore, once we specify
the type of the result, everything works out. And it does:

Foo> build 1 2 3 4 :: [Int]
[1,2,3,4]

In Hugs. But not in GHC (6.0.1). My impression is that GHC assumes
overlapping instances when choosing instances -- even if no
-fallow-overlapping-instances flag is present. In order to get the
example work in GHC, we have to assure that all arguments to build
have the same type in some other way, e.g., using local type
variables:

*Foo> let (a::t)=1 in let b=(2::t); c=(3::t) in build a b c a b c ::[t]
[1,2,3,1,2,3]

The result is actually polymorphic, Num t => [t].



More information about the Haskell mailing list