Now we have all the functionality for Free monad replicated for the its more general clone Free f = FreeT f Identity. The same is going to happen with F and FT (I believe we are gonna get that one soon). We can also have the same situation with Cofree and CofreeT.

So I propose to reorganize the library in a way transformers and mtl do it. So that Control.Monad.X will just reexport Control.Monad.Trans.X and type X = XT Identity.

Specifically:

• Control.Monad.Free -> Control.Monad.Trans.Free
• Control.Monad.Free.Church -> Control.Monad.Trans.Free.Church
• Control.Comonad.Free -> Control.Comonad.Trans.Free
• and perhaps also these two:
  • Control.Monad.Iter -> Control.Monad.Trans.Iter
  • Control.Comonad.Coiter -> Control.Comonad.Trans.Coiter

I can make a corresponding pull request if this is a desired situation.

I am totally not sure about implementation of pass function.
Otherwise MonadWriter instance for IterT seems correct.
Perhaps it can be rewritten in more concise form.

instance (Functor m, MonadWriter w m) => MonadWriter w (IterT m) where
  tell = lift . tell
  listen (IterT m) = IterT . liftM concat' $ listen (fmap listen `liftM` m)
    where
      concat' (Left  x, w) = Left (x, w)
      concat' (Right y, w) = Right $ second (w <>) <$> y
  pass m = IterT . pass' . runIterT . hoistIterT clean $ listen m
    where
      clean = pass . fmap (\x -> (x, const mempty))
      pass' = fmap (either (\((x, f), w) -> Right $ tell (f w) >> return x) (Right . IterT . pass' . runIterT))

The idea behind pass is to clean output for each iteration and add extra tell (f w) iteration in the end. This can possibly break some laws, but maybe not.

The implementation for FreeT should be the same, so once IterT implementation is considered okay, we get MonadWriter and MonadRWS instances for both IterT and FreeT.

Some context: in issue #46, @fizruk suggested generalizing a function for interleaving in the IterT example into something more general, and came up with some implementations.

I've been playing with them; the concise version works quite well, even if already-computed values are traversed again and again.

interleave :: Monad m => [IterT m a] -> IterT m [a]
interleave ms = IterT $ do
  xs <- mapM runIterT ms
  if null (rights xs)
     then return . Left $ lefts xs
     else return . Right . interleave $ map (either return id) xs

With interleave, each step takes time linear in the total number of iterative computations, both finished and pending. One could make it take time linear in the number of pending computations by collapsing neighbouring values; this is a rough sketch:

interleave2 :: Monad m => [IterT m a] -> IterT m [a]
interleave2 = interleave' . map (Right . fmap (:[]))
  where
  interleave' :: (Monad m, Monoid a) => [Either a (IterT m a)] -> IterT m a
  interleave' ms = IterT $ do
    xs <- mapM (either (return . Left) runIterT) ms
    case compact xs of
      [l@(Left _)] -> return l
      xs'          -> return . Right $ interleave' xs'

  compact :: (Monoid a) => [Either a b] -> [Either a b]
  compact []               = []
  compact (r@(Right _):xs) = r:(compact xs)
  compact (l@(Left a) :xs)  = compact' a xs

  compact' a []               = [Left a] 
  compact' a (r@(Right _):xs) = (Left a):(r:(compact xs))
  compact' a (  (Left a'):xs) = compact' (a <> a') xs

And, if we are not interested in the return values:

interleave_ :: (Monad m) => [IterT m ()] -> IterT m ()
interleave_ [] = return ()
interleave_ xs = IterT $ liftM (Right . interleave_ . rights) $ 
                                            mapM runIterT xs

Some caveats:

• Appending lists is costly; the (dlist)[http://hackage.haskell.org/package/dlist] package may provide a good alternative.
• mapM overflows the stack if the number of iterative computations is larger than ~400000. This (thread)[https://groups.google.com/forum/#!topic/haskell-cafe/ey2k1aWmsKo] discusses some solutions.
• Some benchmarks are due. In the example (drawing fractals), the main bottleneck is pushing pixels to the screen, and half of the IterT never finish execution; this may not correspond to other use cases.

When building with GHC-8.1.2017xxxx

[14 of 19] Compiling Control.Monad.Trans.Free.Church ( src/Control/Monad/Trans/Free/Church.hs, /home/ogre/Documents/kmettverse/dist-newstyle/build/x86_64-linux/ghc-8.1.20170123/free-5/build/Control/Monad/Trans/Free/Church.o )

src/Control/Monad/Trans/Free/Church.hs:83:10: warning: [-Wsimplifiable-class-constraints]
    The constraint ‘Eq (FreeT f m a)’ matches an instance declaration
    instance [safe] (Data.Functor.Classes.Eq1 f,
                     Data.Functor.Classes.Eq1 m, Eq a) =>
                    Eq (FreeT f m a)

We should rewrite those instances too, to use lifted classes, shouldn't we?

The new 'either' package dependency drags in transitive dependencies on "transformers-base" "MonadRandom" "monad-control" into upstream packages like "lens".

This instance might not be worth the dependency cost.

These are the current instances for IterT of Alternative and MonadPlus. Both of them were added when the Iter module was first commited; they are equivalent to the ones that would be created by GeneralizedNewtypeDeriving.

instance MonadPlus m => Alternative (IterT m) where
  empty = IterT mzero
  {-# INLINE empty #-}
  IterT a <|> IterT b = IterT (mplus a b)
  {-# INLINE (<|>) #-}

instance MonadPlus m => MonadPlus (IterT m) where
  mzero = IterT mzero
  {-# INLINE mzero #-}
  IterT a `mplus` IterT b = IterT (mplus a b)
  {-# INLINE mplus #-}

In Capretta's slides, a race function is defined. It tries several approaches for the same result (some of them, maybe non terminating), and the earliest one to succeed is picked out. Venanzio b is equivalent to Iter b.

race :: Venanzio b -> Venanzio b -> Venanzio b 
race (Now b0) _ = Now b0
race (Later _) (Now b1) = Now b1
race (Later c0) (Later c1) = Later (race c0 c1)

If race is generalized to the IterT m b, the following instances can be defined. They are analogous to the ones for the MaybeT transformer, and satisfy the same subset of laws : namely, monad plus with left catch.

instance (Monad m) => Alternative (IterT m) where
  empty = never
  {-# INLINE empty #-}
  (<|>) = mplus 
  {-# INLINE (<|>) #-}

instance (Monad m) => MonadPlus (IterT m) where
  mzero = never
  x `mplus` y = IterT $ do
    x' <- runIterT x
    case x' of
      l@(Left _) -> return l
      Right a -> do
        y' <- runIterT y
        case y' of
          l@(Left _) -> return l
          Right b    -> return . Right $ a <|> b

These new semantics might be more useful, but they would break the API.

The culprit are these two pieces of code in Control.Monad.Free.TH, which don't properly handle the new GadtC and RecGadtC constructors from template-haskell-2.11.0.0 (previously, all GADTs would be represented by ForallC, whereas this is no longer the case on GHC 8.0). I'm not sure what exactly the intended behavior for ForallC should be, but regardless, that behavior should be propagated through to GadtC and RecGadtC.

@fizruk, as the original author of Control.Monad.Free.TH, would you mind looking into this?

Like the title says, the MonadTrans instance for Free violates both monad transformer laws. I'll begin with the first law:

-- The first monad transformer law, written as a functor identity law
(lift .) return /= return

This is because the left-hand side creates a Pure embedded within a Free:

lift . return
= Free . liftM Pure . return
= Free . return . Pure

... but the right-hand side creates just a naked Pure:

return
= Pure

The MonadTrans instance for Free also violates the second monad transformer law:

-- The second monad transformer law, written as a functor composition law
(lift .) (f >=> g) /= (lift .) f >=> (lift .) g

The left-hand side comes out to:

lift . (f >=> g)
= Free . liftM Pure . (f >=> g)
= \x -> Free $ liftM Pure $ f x >>= g

... which gives a Pure embedded within a single Free, whereas the right-hand side:

lift . f >=> lift . g
= \x -> lift (f x) >>= lift . g
= \x -> Free (liftM Pure $ f x) >>= Free . liftM Pure . g
= \x -> Free (liftM (Free . liftM Pure . g) $ f x)

... gives a Pure embedded within two Frees.

The laws are only true if you apply retract to both sides of the equation, but retract is not a monomorphism.

Would you be okay with adding this function?

foldFree :: (Functor m, Monad m) => (forall x . f x -> m x) -> Free f a -> m a
foldFree nat = retract . hoistFree nat

As you already know, this is basically one of the isomorphisms in the adjunction that defines the free monad. You have iterM, which is pretty close, but sometimes I find myself reaching for the above signature.

We wind up with a nominal role for the 'm' parameter, because it occurs inside f in the body of FT

newtype FT f m a = FT { runFT :: forall r. (a -> m r) -> (f (m r) -> m r) -> m r }

We should be able to achieve representational by smashing that occurrence of f with Yoneda.

newtype FT f m a = FT { runFT :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r }

This is the same trick that drives the Mendler-style catamorphism.

I was looking at Control.Monad.Free.Church, and I thought of two ways it could be improved.

1. Add an explicit definition for foldMap of (F f): foldMap f x = runF x f fold

2. Change the definition of cutoff:
   cutoff n _ | n <= 0 = return Nothing
   cutoff n (F m) = F $ \kp kf -> m (\a n -> kp (if n <= 0 then Nothing else Just a)) (\f n -> if n <= 0 then kp Nothing else let n' = n - 1 in n' seq kf (fmap ($ n') f)) n

I would submit these improvements, but my computer just died.

The reason I'm interested in a version of makeFree without type signatures is:

• So that I can provide type signatures specialized to a particular monad
• So that I can document auto-generated commands

As far as I can tell, the only way to document commands in haddocks is to put a comment above the type signature, but if I add my own type signature it conflicts with the auto-generated type signature.

When using the Iter monad, it is common to, at some point, run the computation until it terminates by using runIdentity . retract.

This could be implemented as a separate function, named, for example unsafeIter :: Iter a -> a, in the same spirit as fromMaybe :: Maybe a -> a or unsafePerformIO :: IO a -> a. The unsafe monicker warns that the safety guarantees from the Iter monad are lost, namely, evaluation might not terminate.

• Implementation
• Usage example

Any input on the name, the implementation or the usefulness of the proposed function is welcome.

There is From monoids to near-semirings: the essence of MonadPlus and Alternative article worth including in free.

The kan-extensions package provides the largely unrelated Church-encoded Free monad. Lets move it here where it seems to belong.

We're already adding Rank2Types in 3.2 in order to support natural transformations, and they are fairly non-controversial.

E.g.

foldCofree :: Functor f => (a -> f b -> b) -> Cofree f a -> b
foldCofree f = go where
    go (x :< ts) = f x (fmap go ts)

Currently anyone using free monads is forced to write some boilerplate code, e.g.:

data Lang next
  = Output String next
  | Input (String -> next)
  | Done
  deriving (Functor)

-- here goes boilerplate code...
output :: (MonadFree Lang m) => String -> m ()
output s = liftF $ Output s ()

input :: (MonadFree Lang m) => m String
input = liftF $ Input id

done :: (MonadFree Lang m) => m a
done = liftF Done

I'd be happy to substitute that with:

data Lang next
  = Output String next
  | Input (String -> next)
  | Done
  deriving (Functor)
makeOps ''Lang

I'm not sure this can be done in general, but there certainly is some pattern we could probably use. I am not familiar with TH enough to implement the idea right now.

Also I guess this TH stuff should be placed in a separate package?

The error is pretty straightforward:

src/Control/Monad/Free.hs:222:3:
    foldl' is not a (visible) method of class `Foldable'

src/Control/Monad/Free.hs:227:14:
    foldl' is not a (visible) method of class `Foldable'

You would either need to increase the lower bound on base or guard the implementation of foldl' in a CPP pragma.

..due to accepting #10 which requires a bump per the PVP.

It may be a good time to fix up the other issues.

When trying to make a simple schema EDSL, I inadvertently recreated the Control.Applicative.Free part of this library. When someone directed me to this library, I was able to streamline mine, adding the equivalents of lift and runAp.

However, I went a bit further in my module: FList is a free Applicative functor, Monad, and Alternative functor. The interface barely changes, only requiring the result of runFList to be monadic as well. runFList also takes an additional sum function, so that the user can supply their own semantics for <|>.

Is there a chance the free library will be extended, so I can use that instead of my attempt to have free Alternative functors (plus Monad)?

Dave Menendez has written two articles on how to make faster free applicatives with Church encoding. He has benchmarks showing his final solution, B2, is much faster (O(n) instead of O(n²)). It can also become a free Alternative by changing z in the solution to (z -> z), the same way the CPS list monad works.

It spins endlessly and produces an infinite string of repeating "CofreeT (". It's a one line fix but I added a test for it anyway:

diff --git a/free.cabal b/free.cabal
index 86df40e..30ff931 100644
--- a/free.cabal
+++ b/free.cabal
@@ -95,3 +95,12 @@ library
     Control.Monad.Trans.Iter

   ghc-options: -Wall
+
+test-suite CofreeTShowRead
+  hs-source-dirs: test/
+  default-language:   Haskell2010
+  type:           exitcode-stdio-1.0
+  main-is:        CofreeTShowRead.hs
+  build-depends:
+    base                 == 4.*,
+    free
diff --git a/src/Control/Comonad/Trans/Cofree.hs b/src/Control/Comonad/Trans/Cofree.hs
index bdf8ce7..20e6ad3 100644
--- a/src/Control/Comonad/Trans/Cofree.hs
+++ b/src/Control/Comonad/Trans/Cofree.hs
@@ -139,7 +139,7 @@ instance (Functor f, Comonad w) => ComonadCofree f (CofreeT f w) where
   unwrap = tailF . extract . runCofreeT

 instance Show (w (CofreeF f a (CofreeT f w a))) => Show (CofreeT f w a) where
-  showsPrec d w = showParen (d > 10) $
+  showsPrec d (CofreeT w) = showParen (d > 10) $
     showString "CofreeT " . showsPrec 11 w

 instance Read (w (CofreeF f a (CofreeT f w a))) => Read (CofreeT f w a) where
diff --git a/test/CofreeTShowRead.hs b/test/CofreeTShowRead.hs
new file mode 100644
index 0000000..dc471b7
--- /dev/null
+++ b/test/CofreeTShowRead.hs
@@ -0,0 +1,10 @@
+import Control.Comonad.Trans.Cofree
+import Control.Monad
+import System.Exit
+
+main = do
+  let x :: CofreeT Maybe [] Bool
+      x = CofreeT [True :< Nothing]
+      x' :: CofreeT Maybe [] Bool
+      x' = read . show $ x
+  when (x /= x') exitFailure

These have been useful to me in the past when working on parser EDSLs, etc, it might be good to supply them in a canonical location.

http://www.reddit.com/r/haskell/comments/zlr0l/towards_free_applicatives/

In master/src/Control/Monad/Free.hs, line 323, it says:

 foldFree :: (Functor m, Monad m) => (forall x . f x -> m x) -> Free f a -> m a

It should probably be Functor f, not Functor m. It still typechecks because fmap isn't actually used in the definition, I think. (It would only be used in the proof of correctness, e.g. the naturality square.)

Given that it is written primarily for compatibility perhaps this makes sense to rename?

tailed?

Cannot build projects that depend on both 'free' and 'pointed', because free excludes comonad-transformers >= 1.7 and pointed excludes comonad-transformers < 1.7.

When you get a chance, would you please update the dependency? 'free' builds fine for me with comonad-transformers 1.7.

The following race-like Alternative instance insane? The corresponding instance for FreeT would make IterT really reduce to FreeT Identity , since IterT uses such an instance.

instance Applicative v => Alternative (Free v) where
  empty = Free (pure empty)
  {-# INLINE empty #-}
  l <|> r = case l of
    Pure a -> Pure a
    Free a -> case r of 
      Pure b -> Pure b
      Free b -> Free (liftA2 (<|>) a b)
  {-# INLINE (<|>) #-}

It makes clear sense for e.g. Free ((,)a) where it would require a to be a monoid, and empty would thus be the infinite stream of memptys. When you (<|>) them, you append the elements monoidally as you go along, but then stop when either of them stops. In the case of ((->) a) mempty would be an infinite sink of 'a's. Maybe it's nonsense in other cases?

Would you be interested in adding the following function to FreeT:

mapFreeT :: (Functor f, Monad m) => (forall x . m x -> n x) -> FreeT f m r -> FreeT f n r
mapFreeT nat = FreeT . nat . liftM (fmap (mapFreeT nat)) . runFreeT

This greatly resembles an IFunctor instance, except for the (Monad m) (or (Functor m)) constraint. In the longer run, when working on your indexed package you might consider N versions of all the indexed classes (i.e. NFunctor, NMonad) that have functor constraints on the last type variable that are appropriate for the world of natural transformations.

This kind of transformation is generally useful for all monad transformers since it allows you to change the base monad for a pre-existing function. For example, if I write a pipe like:

fileReader :: Producer ByteString IO ()

... and let's say I have another pipe that folds its input:

someFold :: (Monad m) => Pipe a b (WriterT m) r

I could make them compatible just by writing:

pipe :: someFold <+< mapFreeT lift fileReader

This isn't a blocking issue for me switching to free for pipes, and I plan on switching soon regardless. This is more of a "nice to have" thing. Also, it doesn't have to be a named function. If you find an appropriate class for it you can use that, too.

I noticed that Cofree implements every superclass of Representable, but not Representable itself. Here's a possible instance:

instance Representable f => Representable (Cofree f) where
  tabulate f = f Seq.empty :< tabulate (\k -> tabulate (f . (k Seq.<|)))

The documentation for free states that these instances should be handled "with care", but provides no extra information as to what this means. For some people (e.g., me), it's not clear what could go wrong, and how I may shoot myself in the foot by using these instances. I think free should expand on its disclaimer a little bit more, so that it is actionable to users.

Can the latest version of this package be pushed to hackage? (lens too I guess) This package (and lens) have higher upper bounds for mtl than they do on hackage and cause dependency issues.

https://hackage.haskell.org/package/free-4.7.1/free.cabal --> mtl >= 2.0.1.0 && < 2.2
https://raw.githubusercontent.com/ekmett/free/master/free.cabal --> mtl >= 2.0.1.0 && < 2.3

For Free monad we have iterM that makes it easy to write arbitrary interpreters for the underlying functor. For FreeT we have iterT which is more like iter: we can't introduce an arbitrary monad and are forced to use the underlying one.

The problem with implementing iterM' for FreeT is that monads are not (easily) composable. But monad transformers are! This gave me the idea that iterM' should accept FreeT f (t Identity) a or (forall m. Monad m => FreeT f (t m) a as a second argument instead of FreeT f m a.

Using hoist from mmorph package iterM' can be implemented like this:

-- This is analog of 'iterM' for a 'Free' 'Monad' (@Free f = FreeT f Identity@)
iterM' :: (MFunctor t, Monad m, Functor f, Monad (t Identity), Monad (t m)) =>
  (f (t m a) -> t m a) -> FreeT f (t Identity) a -> t m a
iterM' phi = iterT phi . hoistFreeT (hoist $ return . runIdentity)

Note the similarity with iterM implementation:

-- | 'iterM' from 'Control.Monad.Trans.Free'
iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a
iterM phi = iterT phi . hoistFreeT (return . runIdentity)

I believe this similarity suggests I'm on the right way at least.

Without any extra dependencies (e.g. mmorph) iterM' can be alternatively defined as follows:

iterM'' :: (Monad m, Functor f, Monad (t m)) =>
  (f (t m a) -> t m a) -> (forall n. Monad n => FreeT f (t n) a) -> t m a
iterM'' phi m = iterT phi m

But that last definition forces users to write values of higher rank types.

So I suggest to add iterM' (perhaps with a better name) to the library.

From "Monad transformers and modular algebraic effects: What binds them together"

fold :: Functor sig => (a -> b) -> (sig b -> b) -> (Free sig a -> b)
fold gen alg (Pure x) = gen x
fold gen alg (Free op) = alg (fmap (fold gen alg) op)

My working assumption is it'd look something like:

data AltF f a where
  Pure :: a -> AltF f a
  Ap   :: f a -> Alt f (a -> b) -> AltF f b
#if __GLASGOW_HASKELL__ >= 707
  deriving Typeable
#endif

data Alt f a = Alt [AltF f a]
#if __GLASGOW_HASKELL__ >= 707
  deriving Typeable
#endif

-- | Given a natural transformation from @f@ to @g@, this gives a canonical monoidal natural transformation from @'Alt' f@ to @g@.
runAlt :: forall f g a. Alternative g => (forall x. f x -> g x) -> Alt f a -> g a
runAlt u xs0 = go xs0 where
  go :: Alt f a -> g a
  go (Alt xs) = foldr (\a r -> go2 a <|> r) empty xs

  go2 :: AltF f a -> g a
  go2 (Pure a) = pure a
  go2 (Ap f x) = flip id <$> u f <*> runAlt u x

instance Functor (AltF f) where
  fmap f (Pure a)   = Pure (f a)
  fmap f (Ap x y)   = Ap x (fmap f <$> y)

instance Functor (Alt f) where
  fmap f (Alt as)   = Alt (fmap f <$> as)

Thoughts?

Hi! Big fan; maybe I'm doing this wrong but the following code produces an error (Mac OS X 10.10.2, GHC 7.10.1 installed via homebrew, free-4.12.1):

import Control.Comonad
import Control.Comonad.Cofree
import Data.Functor.Identity

type Stream = Cofree Maybe

nums :: Stream Int
nums = unfold (\x -> (x, Just (x+1))) 0

firstNum :: Int
firstNum = extract nums -- error!

The error message is this:

<interactive>:1:1:
    No instance for (Comonad (Cofree Identity))
      arising from a use of ‘extract’
    In the expression: extract nums

I don't have this issue on my Arch setup, but that's at home and perhaps not as up-to-date. I get a similar issue with Data.Stream.Future (extract (Last True) produces a similar error).

Ørjan's version stores values in a more natural order.

Please see the code and detailed description in my article.

With GHC 7.10 and base-4.8.0.0 Data.Monoid gained a new Alt type constructor (which is an Alternative wrapper).

Should Control.Alternative.Free.Alt be renamed to avoid confusion and qualified imports?
Not sure it's an issue though.

Attempting to build the haddocks for the gh-pages branch, but I'm getting something I've never seen before.

Macintosh:free ekmett$ cabal haddock
Running Haddock for free-4.6...
Preprocessing library free-4.6...
Warning: The documentation for the following packages are not installed. No
links will be generated to these packages: bifunctors-4.1.1, comonad-4.0,
contravariant-0.4.4, distributive-0.4, hashable-1.2.1.0, mtl-2.1.2,
nats-0.1.2, profunctors-4.0.2, semigroupoids-4.0, semigroups-0.12.2,
tagged-0.7, text-1.1.0.1, transformers-compat-0.1.1.1,
unordered-containers-0.2.3.3

<no location info>:
    module ‘free-4.6:Main’ is defined in multiple files: dist/build/tmp-92156/src/Control/Applicative/Free.hs
                                                         dist/build/tmp-92156/src/Control/Alternative/Free.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Cofree.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Cofree/Class.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Trans/Cofree.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Trans/Coiter.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free/Church.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free/Class.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free/TH.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Trans/Free.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Trans/Free/Church.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Trans/Iter.hs
                                                         dist/build/tmp-92156/src/Control/MonadPlus/Free.hs

Please forgive me if this is already defined somewhere--I couldn't find a precise match--but this function would be useful to have:

hoistCofree :: (Functor f) => (forall x . f x -> g x) -> Cofree f a -> Cofree g a
hoistCofree f (x :< y) = x :< f (hoistCofree f <$> y)

The type signature of hoistCofree is currently:

hoistCofree :: Functor f => (forall x. f x -> g x) -> Cofree f a -> Cofree g a

However, it can be generalized to:

hoistCofree :: Functor f => (f (Cofree g a) -> g (Cofree g a)) -> Cofree f a -> Cofree g a

Cofree forms a Monad when the functor is an Alternative, but the instance is missing for CofreeT.

Pipes.Group has

concats :: Monad m => FreeT (Producer a m) m x -> Producer a m x

which could generalize to

retractT :: (MonadTrans t, Monad m) => FreeT (t m) m x -> t m x

Alternately we might work with a monad homomorphism instead.

When applying foldFree id I got

foldFree id :: Monad m => Free m a -> m a

same type as

retract :: Monad m => Free m a -> m a

and at a quick glance they appear to be equal: if so should that be added as a law? I googled foldFree id and didn't find much.

The statement that the monad m is free over the functor f corresponds to the following universal property:

Given a monad m' and a natural transformation n: f ~> m' there exists a unique monad morphism nhat: m ~> m' such that
nhat . wrap . fmap return == n.

So it should be possible to write the following generalization of foldFree:

phi :: (MonadFree f m, Monad m') => (forall x. f x -> m' x) -> m a -> m' a

but it appears to me that wrap :: f (m a) -> m a is not sufficient for this. I find myself itching for something like unwrap :: m a -> Either a (f m a).

pure and return have differing results. In the case of Cofree Maybe for instance, pure yields an infinite string of its argument, where as return yields a one-element string containing its argument.

Eg:

newtype FT f m a = FT {runFT :: forall r. (a -> m r) -> (f r -> m r) -> m r}

Code here

This is a first attempt at a Church-encoded free monad transformer, represented by the type:

newtype FT f m a = FT { runFT :: forall r. (a -> m r) -> (f (m r) -> m r) -> m r }

The module includes equivalents of hoistFreeT and transFreeT from Control.Monad.Trans.Free.

There are also three recursion schemes:

cataFT :: (a -> m b) -> (f (m b) -> m b) -> FT f m a -> m b
cataFT kp kf ft = runFT ft kp kf

foldFT :: (Traversable f, Monad m) => (a -> m b) -> (f b -> m b) -> FT f m a -> m b
foldFT kp kf = cataFT kp $ kf <=< sequence

sequenceFT :: (Traversable f, Monad m, MonadFree f n) => FT f m a -> m (n a)
sequenceFT = foldFT (return . return) (return . wrap)

The code also adds analogues of these recursion schemes for the existing FreeT class. The isomorphism of FreeT and FT is witnessed by the functions toFreeT and fromFreeT.

If the cataFT and cataFreeT definitions can be moved to a type class for free monad transformers (the transformer version of MonadFree), the recursion schemes can be written generically. I'm not sure if this is a good design choice.

There are some more functions in the control-monad-free package not yet included in free. I think it would be worth porting over those that are likely to be useful.

(Note: This code is a first draft. There are only the bare minimum of type class instances, no documentation, and not very good names for the new types and functions.)