Search code examples
haskellrecursion-schemes

Having an issue extending Data.Functor.Foldable

This question uses the concepts/imports from http://hackage.haskell.org/package/recursion-schemes-4.0/docs/Data-Functor-Foldable.html

I'm trying to extend this to thread a given monad through a catamorphism. Here is the code that I'm trying to compile:

class (Monad m, Foldable t) => FoldableM m t where
  distM :: Base t (m a) -> m (Base t a)

  cataM :: (Base t a -> m a) -> t -> m a 
  cataM f = join . liftM f . distM . fmap (cataM f) . project

But the call to distM in cataM for some reason can't figure out to use the same t.

The error I get is:

Expected type: Base t (m a) -> m (Base t a)
Actual type: Base t0 (m a) -> m (Base t0 a)

I made the code a bit less sexy and a bit easier to debug here:

cataM :: forall a . (Base t a -> m a) -> t -> m a
cataM f t = join d
  where
  a :: Base t t
  a = project t

  b :: Base t (m a)
  b = fmap (cataM f) a

  g :: Base t (m a) -> m (Base t a)
  g = distM

  c :: m (Base t a)
  c = g b

  d :: m (m a)
  d = liftM f c

The definition of g is what causes the issue.

EDIT: The problem as I understand it is that when it calls distM it only has Base t to infer the type from, so it cannot work out t. This is frustrating, since I know what t I want to use. In fact, I think if I could supply the type arguments to distM manually it would fix the problem, but I don't think that's possible.

Here is a solution but I'm not happy with it:

class (Monad m, Foldable t) => FoldableM m t where
  distM :: t -> Base t (m a) -> m (Base t a)

  cataM :: forall a . (Base t a -> m a) -> t -> m a
  cataM f = join . liftM f . distM (undefined :: t) . fmap (cataM f) . project

EDIT 2: Cool to learn about Proxy (thanks Antal). I've been Haskelling for years now and just learnt yet another new thing. I love this language. The solution I'm using is:

class (Monad m, Foldable t) => FoldableM m t where
  distM :: proxy t -> Base t (m a) -> m (Base t a)

  cataM :: forall a . (Base t a -> m a) -> t -> m a
  cataM f = join . liftM f . distM (Proxy :: Proxy t) . fmap (cataM f) . project
Solution

  • Base t is a type family, so GHC can't know t from Base t. There's no way to get distM to work without mentioning t.