Deep fmap with GADTs and type families.

David Menendez dave at
Thu Mar 5 23:25:21 EST 2009

On Thu, Mar 5, 2009 at 10:07 PM, Dan Doel <dan.doel at> wrote:
> But we've so far not been able to find a way of merely annotating the original
> into working. So, I was wondering if any of the more knowledgeable folks here
> could illuminate what's going wrong here, and whether I should expect my
> original code to work or not.

I'll bet the problem has to do with the fact that "f" only appears in
"Nest n f a", so the type checker can't figure out what "f" is.

Here are two other variants that work.

deepFMap :: Functor f => Nat n -> (a -> b) -> Nest n f a -> Nest n f b
deepFMap Z     f = fmap f
deepFMap (S n) f = deepFMapS n f

deepFMapS :: Functor f => Nat n -> (a -> b) -> f (Nest n f a) -> f (Nest n f b)
deepFMapS Z     f = fmap (fmap f)
deepFMapS (S n) f = fmap (deepFMapS n f)
-- alternative:
-- deepFMapS (S n) f = fmap (deepFMap (S n) f)

type family Nest' n (f :: * -> *) a :: *

type instance Nest' Z f a = a
type instance Nest' (S n) f a = f (Nest' n f a)

deepFMap' :: Functor f => Nat n -> (a -> b) -> f (Nest' n f a) -> f
(Nest' n f b)
deepFMap' Z     f = fmap f
deepFMap' (S n) f = fmap (deepFMap' n f)

Dave Menendez <dave at>

More information about the Glasgow-haskell-users mailing list