`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 rIn 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 strWe 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: " ++ strThis 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 somethingThe

`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`.

`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 -> rIn 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.

`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 rAnd 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 rI 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.

I'd be willing to rename Free to Wrap in free and incorporate the transformers-free contents if you'd like. I've been meaning to add it to free for some time now.

ReplyDeleteAlright. I also think it would be better to use your Free type for the ordinary version, so you can throw out mine and keep just FreeT. As far as my pipes library is concerned, I just use runFreeT and the constructors so you can take liberties with the rest of the API. I can also send you my codensity code for FreeT but I imagine you already know how to implement it.

Delete