In Haskell, how could I embed one Free monad in another one?

Question

I have two Free monads for different operations in different contexts. However, one (major) DSL needs to contain another one (action) if the specific operation is in the context:

import Control.Monad.Free

data ActionFunctor next = Wait Timeout next
                        | Read URI next

instance Functor ActionFunctor where
  fmap f (Wait timeout next)  = Wait timeout (f next)
  fmap f (Read uri next)      = Read uri (f next)

type Action = Free ActionFunctor


data MajorFunctor next = Log LogText next
                       | Act Action next
                       | Send Message

instance Functor MajorFunctor where
  fmap f (Log text next)    = Log text (f next)
  fmap f (Act action next)  = Act action (f next)
  fmap f (Send message)     = Send message

type Major = Free MajorFunctor

The issue is, GHC will complain MajorFunctor that the Action in Act Action next is a kind of (* -> *), not just a type. This is because in the data ActionFunctor definition it should accept a next as the type parameter, and in the Act Action line it contains no such parameter. But even the message is clear to me, I'm not sure if I should declare such extra type parameter in the Major functor as well:

data MajorFunctor actionNext next = ...

It looks weird because only one data constructor will use the parameter, while such exposing will turn every MajorFunctor into MajorFunctor actionNext and it looks totally exposes too much details. So I took a look at FreeT transformer to see if it is what I want. However, in my case I only need to call Action interpreter when the DSL program has such operation, not every bind in the monadic program, so I'm also not sure if a transformer is a good solution.

Answer 1

A simpler solution, which doesn't need an existential, is to embed the next parameter inside the Action.

data MajorFunctor next = Log LogText next
                       | Act (Action next)
                       | Send Message

instance Functor MajorFunctor where
  fmap f (Log text next) = Log text (f next)
  fmap f (Act action) = Act (fmap f action)
  fmap f (Send message) = Send message

This says "When you execute the Action it'll return a next", whereas @Cactus's solution says "When you execute the Action it'll return something (of unknown (existential) type) which can (only) be turned into a next".

The co-Yoneda lemma says that these two solutions are isomorphic. My version is simpler but Cactus's may be faster for some operations such as repeated fmaps over large Actions.

Answer 2

In your Act constructor, you can embed an Action a and then continue with the next step depending on the a. You can do this by using an existential to tie the two together:

{-# LANGUAGE ExistentialQuantification #-}
data MajorFunctor next = Log LogText next
                       | forall a. Act (Action a) (a -> next)
                       | Send Message

instance Functor MajorFunctor where
  fmap f (Log text next)    = Log text (f next)
  fmap f (Act action next)  = Act action (fmap f next)
  fmap f (Send message)     = Send message