Free monad transformers

I'm spinning off the Control.Monad.Trans.Free module from pipes into its own package: transformers-free. Some people requested this because they wanted to experiment with the FreeT type in their own code without making pipes a full-blown dependency.

Free monad transformers

Recently I've evangelized the use of free monads for building abstract syntax trees that let you abstract away the interpreter. This lets you seamlessly build custom domain-specific languages in Haskell.

However, sometimes we can't specify the syntax tree all at once. Often we want to interleave the syntax tree with some other monad to generate streaming or interactive computations. FreeT solves this problem by allowing us to mix building steps of the abstract syntax tree with calling actions in some base monad:

data FreeF f a x = Pure a | Free (f x)

newtype FreeT f m a = FreeT {
    runFreeT :: m (FreeF f a (FreeT f m a)) }

For example, let's say we want to write our own Python-style generator:

type Generator b m r = FreeT ((,) b) m r

In this case, our syntax tree is an ordinary list where we run the base monad to generate the next element. We can even duplicate Python syntax:

yield :: b -> Generator b m ()
yield b = liftF (b, ())

We can set the base monad to IO if we want to prompt the user to enter each subsequent element of the list:

prompt :: Generator String IO r
prompt = forever $ do
    lift $ putStrLn "Enter a string:"
    str <- lift getLine
    yield str

We can then demand the next element from our generator using runFreeT:

main = do
    x <- runFreeT prompt
    case x of
        Pure       _  -> return ()
        Free (str, _) -> putStrLn $ "User entered: " ++ str

This does not prompt the user for an infinite number of values. Instead, we only prompt the user to enter as many values as we demand from the generator, which was just one value in the above example. However, if we wanted to bleed our user dry, we could gratuitously demand the entire generator:

main = putStrLnAllTheThings prompt

putStrLnAllTheThings gen = do
    x <- runFreeT gen
    case x of
        Pure         _   -> return ()
        Free (str, gen') -> do
            putStrLn str
            putStrLnAllTheThings gen'

However, even that still streams the values and never retains them in memory.

Denotation

Sometimes we want to give our free monad a complete denotation, but our base functor does not cut it. The classic example is simulating the State monad using a free monad. We could try adding the following two terms to our base functor to act like a State monad:

data BaseF s x
  = Get (s -> x)
  | Put s x
  | Something x
  ...

... and we even can write the following State-like primitives:

get' :: Free (BaseF s) s
get' = liftF $ Get id

put' :: s -> Free (BaseF s) ()
put' s = liftF $ Put s ()

... but these simulated primitives do not necessarily obey the State monad equations such as:

put x >> put y = put y
get >>= put = return ()

However, we can instead outsource part of the denotation to the actual State monad. All we do is delete the Get and Put constructors from our base functor:

data BaseF x
  = Something x
  ...

... and instead just use State (or StateT m) as the base monad:

doSomething :: FreeT BaseF (State s) ()
doSomething = do
    x <- lift get
    lift $ put x
    something

The FreeT monad transformer is correct by construction, so we can use the monad transformer laws to equationally reason about our program to eliminate the dead code at the end of our function:

-- lift m >>= lift . f = lift (m >>= f)
doSomething = do
    lift $ do
        x <- get
        put x
    something

-- get >>= put = return ()
doSomething = do
    lift $ return ()
    something

-- lift (return x) = return x
doSomething = do
    return ()
    something

-- return () >> m = m
doSomething = something

FreeT offers us a nice way to selectively outsource our denotation to other monads whenever we need stronger equational guarantees.

free compatibility

I do not intend to use transformers-free to replace the free package for free monads that are not monad transformers. Even in my own code I still use free for ordinary free monads. I only provide the ordinary Free type to keep the transformers tradition of formulating the ordinary monad in terms of the corresponding monad transformer.

When designing the transformers-free library, I tried to adhere to the free package as closely as possible for naming conventions. I really only disagree with one naming convention Edward used, which is naming one of the constructors Free, for two reasons:

• It shares the same name as the type, which is confusing since it's not the only constructor.
• It does not share the same name as its smart constructor, wrap, which is confusing because Pure does share the same name as its smart constructor, pure.

So he probably should have named the constructor Wrap, but I decided to stick with his name and not buck convention.

I also structured the FreeT type so that the derived Free type would resemble Free from the free package as closely as possible. The only difference is that in transformers-free you have to use the runFree observation function first before you can pattern match on the constructors, but otherwise it's identical:

-- using the "free" package
f :: Free f r -> ...
f x = case x of
    Pure r -> ...
    Free w -> ...

-- using the "transformers-free" package
f :: Free f r -> ...
f x = case runFree x of
    Pure r -> ...
    Free w -> ...

I also found that this was the most natural way to write the FreeT type and the easiest to use, based on my experience using it within the pipes library. Of course, your own mileage might vary!

I haven't copied all the functions that the free package provides. I mainly omitted the recursion schemes because there are a few other recursion schemes that I was also considering:

foldFree1 :: (a -> r) -> (f r -> r) -> Free f a -> r
-- or
foldFree2 :: (FreeF f a r -> r) -> Free f a -> r

... and their FreeT equivalents, which use m r as the carrier of the algebra instead:

foldFreeT1 :: (a -> m r) -> (f (m r) -> m r) -> FreeT f m a -> r
-- or
foldFreeT2 :: (FreeF f a (m r) -> m r) -> FreeT f m a -> r

In the end, I chose not to include anything yet and leave it up to discussion, since it is easier to add API functions than remove them.

Performance

I also wrote up a codensity version implemented using the following type:

newtype FreeT {
    foldFreeT :: (a -> m r) -> (f (m r) -> m r) -> m r }

This gives large speed differences for code that never uses the base monad. I'm on vacation, so I don't have access to my work computer to reproduce the benchmarks, but I vaguely remember that they ranged from a best case improvement of roughly 50% faster for operations on the tail of the list to a worst case penalty of roughly 30% slower for operations on the head of the list. However, for real world use cases where you intermingle IO operations like simple print statements at each step then the performance differences drop to less than 5%.

The main reasons I haven't released the codensity version yet are:

• If I release multiple implementations, I want to type-class them with appropriate laws.
• Type-class signatures cannot be easily updated, so I want to solidify the API first.

Note: Some reddit readers may remember me remarking on the naive implementation giving linear time complexity for left-associative code, but this was a false alarm: the code was actually right-associative. Since do notation is right-associative, the time complexity difference between left-associative code doesn't arise frequently in practice, but one should always still keep it in mind, especially when writing code like:

do x <- longFreeMonad
   somethingElse

transformers compatibility

I'm proposing this library as a candidate for inclusion in the transformers package, so the documentation is structured very similarly.

I also provide a MonadIO instance for the type, something I was very reluctant to do since I consider MonadTrans to be sufficient for that purpose. However, I relented since:

• I've gotten a lot of feedback in favor of a MonadIO instance for this type
• If this ever does get accepted into transformers, it will get a MonadIO instance anyway.

Iteratees

The FreeT type (or its isomorphic codensity version) arises very frequently in iteratee libraries. For example, the Iteratee type from the enumerator package is isomorphic to:

data IterateeF a next
  = Continue (a -> next)
  | Error SomeException
  
Iteratee a m r ~ FreeT (IterateeF (Stream a)) (r, Stream a)

The Iteratee type from the iteratee package is isomorphic to:

data IterateeF a next
  = Await (a -> next) (Maybe SomeException)

Iteratee a m r ~ FreeT (IterateeF (Stream a)) (r, Stream a)

The Pipe type from pipes is:

data PipeF a b next
  = Await (a -> next)
  | Yield (b, next)

type Pipe a b m r = FreeT (PipeF a b) m r

And the Pipe type from conduit is (sort of) isomorphic to:

data ConduitF l i o u m next
  = HaveOutput (m ()) o next
  | NeedInput (i -> next) (u -> next)
  | LeftOver l next

Pipe l i o u m r ~ FreeT (ConduitF l i o u m) m r

I say "sort of" because conduit followed the pipes-1.0 approach that made the base monad optional, which only gives a correct monad transformer when viewed through the lens of runPipe. However, in principle, conduit with congruence laws implements something isomorphic to FreeT since conduit requires its users only use runPipe to inspect conduits.

pipes

The pipes-2.2 package now uses transformers-free to provide Control.Monad.Trans.Free meaning that Pipe now has a MonadIO instance, something which many people have requested before.

Also, if you install transformers-free on its own and have an existing pipes installation, make sure that you upgrade pipes to version 2.2 to avoid conflicting exports for Control.Monad.Trans.Free.

However, I have no plans yet to shift Control.IMonad.Trans.Free to an external package since I doubt other people will use it any time in the near future.

Conclusion

The transformers-free package provides the unifying theoretical abstraction for streaming or interactive programs: the free monad transformer. Once you learn the abstraction, you will start to see it everywhere, even in non-iteratee libraries.