[Haskell-cafe] Typing efficient folds

[Brent Yorgey]

On Fri, Apr 24, 2009 at 06:52:09PM +0000, Keith Battocchi wrote:
> I'm trying to write some code to do folds on nested datatypes as in 
> http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/efolds.pdf but 
> running into trouble getting things to typecheck.
> 
> Given the types
> 
> data Nest a = Nil | Cons(a, (Nest (Pair a)))
> type Pair a = (a,a)
> 
> and the following function to map over pairs:
> 
> pair f (a,b) = (f a, f b)
> 
> the paper indicates that an efficient fold over a nest is defined as follows
> 
> efold :: forall n m b. 
>   (forall a. n a) 
>   -> (forall a . (m a, n (Pair a)) -> n a)
>   -> (forall a. Pair (m a) -> m (Pair a))
>   -> (forall l z. (l b -> m (z b)) -> Nest (l b) -> n (z b))
> efold e f g h Nil = e
> efold e f g h (Cons(x, xs)) = f(h x, efold e f g (g . pair h) xs)
> 
> However, when I try to compile this, I get the error "Couldn't match expected 
> type `l' against inferred type `z'".  I'm new to Haskell so I'm probably 
> missing something obvious, but this code looks to me like it ought to work.  
> Any thoughts on what I'm doing wrong?

Well, I'm pretty sure you're not 'missing something obvious'!  I
stared at this code for fifteen minutes and can't really figure out
what's going on.  If you change the 'z's in the type signature to
'l's, it type checks, but that may make the function slightly less
general than intended.

-Brent