Free Monad vs explicitly passing functions

Even if we restrict ourselves to choosing between free monads and records-of-functions (leaving out solutions involving monad transformer stacks and MTL-like typeclasses) there's a lot of debate ongoing, and the matter it's not settled.

The simple free monad has been traditionally accused of suffering from two flaws: runtime inefficiency (which might or not be important, depending on how slow the interpreter operations are by comparison) and lack of extensibility (how to lift a program into another having a richer set of effects?).

"Data types a la carte" first attempted a solution to the extensibility problem. Later, the "Freer Monads, More Extensible Effects" paper came out, which proposed a more sophisticated free type to increase the efficiency of the monadic bind, and also an extensible way of defining sets of operations. The main libraries implementing this approach are:

  • freer-simple The simplest to understand of the bunch, apparently also the slowest. It seems to have some limitations on bracket-type operations.

  • fused-effects More efficient library that allows bracket-type operations. But the types are also more complex.

  • polysemy Relatively new library which aims to be fast and support bracket-type operations while retaining simple types.

One appealing aspect of these libraries is that they let you interpret effects piecemeal, picking out one effect while leaving the rest uninterpreted. You can also interpret an abstract effect into other abstract effects, without having to go down to IO right away.

As for the record-of-functions approach. Programs like programWithCapabilities which are polymorphic over a base monad, and which take a record of functions parameterized by the monad, are conceptually related to what is called the van Laarhoven Free Monad:

-- (ops m) is required to be isomorphic to (Π n. i_n -> m j_n)
newtype VLMonad ops a = VLMonad { runVLMonad :: forall m. Monad m => ops m -> m a }

instance Monad (VLMonad ops) where
  return a = VLMonad (\_ -> return a)
  m >>= f = VLMonad (\ops -> runVLMonad m ops >>= f' ops)
   where
    f' ops a = runVLMonad (f a) ops

From the linked post:

Swierstra notes that by summing together functors representing primitive I/O actions and taking the free monad of that sum, we can produce values use multiple I/O feature sets. Values defined on a subset of features can be lifted into the free monad generated by the sum. The equivalent process can be performed with the van Laarhoven free monad by taking the product of records of the primitive operations. Values defined on a subset of features can be lifted by composing the van Laarhoven free monad with suitable projection functions that pick out the requisite primitive operations.

There don't seem to exist (?) libraries that give you a pre-fabricated VLMonad type. What does exist are libraries that take a record of functions but otherwise work over IO, like RIO. One can still abstract over the base monad in one's logic, and later use RIO when running the logic. Or prefer simplicity and rip the polymorphic veil that hides the IO from one's logic.

The record-of-functions approach has perhaps the merit of being more easily grasped, being an incremental step-up from working directly on IO. It also more closely resembles the object-oriented way of doing dependency injection.

The ergonomics of working with the record itself become central. Right now it is common to use "classy lenses" to make the program logic independent of the concrete record type and facilitate program composition. Perhaps one day extensible records could be used as well (like extensible sum types are used in the freer approach).


There may be some non-style considerations like performance or ease of type inference that favor one over the other (my guess is that the Capabilites-style approach is probably a little better for both, but benchmark before you take that as truth), but by and large they are equivalent. You can take a program expressed with Capabilities and run it with ioInterprefer [sic], and you can take a program expressed with Free MyGatd [sic] and run it with an arbitrary Capabilities.

Like this:

freeToCaps :: Monad m => FreeMonad.Free MyGatd () -> Capabilities m -> m ()
freeToCaps (FreeMonad.Pure x) _ = return x
freeToCaps (FreeMonad.Free (Read f)) c = myRead c >>= flip freeToCaps c . f
freeToCaps (FreeMonad.Free (Write str x)) c = myWrite c str >> freeToCaps x c

capsToFree :: Capabilities (FreeMonad.Free MyGatd)
capsToFree = Capabilities {myRead = FreeMonad.Free $ Read FreeMonad.Pure, myWrite = FreeMonad.Free . flip Write (FreeMonad.Pure ())}

runFreeToCaps :: IO ()
runFreeToCaps = freeToCaps programWithFreeMonad $ Capabilities {myRead = getLine, myWrite = putStrLn}

runCapsToFree :: IO ()
runCapsToFree = ioInterprefer $ programWithCapabilities capsToFree

My advice is to pick whichever feels more natural given the rest of your program, and know that if you change your mind, you can always write adapters like the above to help you refactor your program incrementally.

Tags:

Haskell

Recent Posts