composeList

David Feuer dfeuer@cs.brown.edu
Sun, 12 May 2002 23:57:27 -0400


See comments below.

On Sun, May 12, 2002, David Feuer wrote:
> On Sun, May 12, 2002, Emre Tezel wrote:
> > Hi all,
> > 
> > I recently bought Simon Thompson's Haskell book. I have been doing the 
> > exercises while I read on. There are couple questions that I can not 
> > solve. Any help would be greatly appreciated.
> > 
> > I got stuck on this question in Chapter 10.
> > 
> > Define a function composeList which composes a list of functions into a 
> > single function. What is the type of composeList?
> > 
> > I naively tried the following but the hugs compiler complained about the 
> > inferred type not being generic enough.
> > 
> > composeList :: [(a -> b)] -> (c -> b)
> > composeList [] = id
> > composeList (x:xs) = x . (composeList xs)

<snip>

> You can do a lot better in Glasgow Haskell:
> 
> data Fun a b = forall c . Comp (c -> b) (Fun a c) | End (a -> b)
> 
> compose :: Fun a b -> a -> b   --GHC needs this type signature
>                                --to compile the program, but
>                                --I don't understand why.
>                                --Any tips?
> compose (End f) = f
> compose (Comp f l) = f . compose l

Well, I figured out why the type signature is necessary (polymorphic
recursion), but I don't understand the error message I got from GHC:

cc.hs:5:
    Inferred type is less polymorphic than expected
        Quantified type variable `c' escapes
    When checking a pattern that binds
        f :: c -> b
        l :: Fun a c
    In the definition of `compose':
        compose (Comp f l) = f . (compose l)

What makes it think that `c' escapes?  This message had me staring at the code
the wrong way for quite a while before I decided to add a type signature and
see if that gave me any more useful information.

> 
> f::Int -> Float
> f x = fromIntegral x
> 
> g::String -> Int
> g = read
> 
> h::Int -> String
> h x = take x "123456789"
> 
> main = do
>    putStrLn "hello!"
>    print $ compose (End (\x -> "Foo!")) 3
>    print $ compose (Comp f (Comp g (End h))) 4

-- 
Night.  An owl flies o'er rooftops.  The moon sheds its soft light upon
the trees.
David Feuer