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