What are freer monads?

Question

I heard this term few times, but I still don't know what certainly is a so-called "Freer Monad". The name makes me think about Free Monads, but I don't see how are they actually related. There is some library I found on hackage: http://hackage.haskell.org/package/freer, but the example out there didn't help me a lot.

I don't think I understand the idea at all and therefore I don't see any good usecases for them. I also wonder what advantages do they provide over free monads and classic mtl stacks.

Answer 1

I know this is an old thread, but i thought I'd answer it anyway just in case

what [...] is a so-called "Freer Monad"

according to the original paper Freer Monads, More Extensible Effects a "Freer Monad" is essentially a Free Monad without the necessary Functor constraint of a Free Monad.

A free monad is basically the essence of the monadic structure; the "smallest" thing that is still a monad. A very nice practial explanation approach can be found in this article. This article also shows that the "normal" free monad needs a Functor constraint.

However, it is often quite tedious adding the functor constraint in every function (and sometimes maybe even weird to implement), and as it turns out, by "moving the functor functionality" to an argument for the Impure constructor so that the implementing side can alter the type of the output itself (so without a general functor), it is possible to get rid of this constraint. This is done by using GADTs: (example from the Freer Monads paper)

data Free f a = Pure a
              | Impure (f (Free f a))

instance Functor f => Monad (Free f) where 

becomes

data FFree f a where
    Pure :: a → FFree f a
    Impure :: f x → (x → FFree f a) → FFree f a

instance Monad (FFree f) where 
    [...]
    Impure fx k’ >>= k = Impure fx (k’ >>> k)

This basically lets the later implementation choose how to perform the fmap operation fixed [pun not intended] to the appropriate "output/wrapped type". So the fundamental difference is essentially usability and generality.

As there was some confusion: FFree is the Freer monad and corresponds to Eff in the package freer-simple.

good usecases for them

Freer monads, just as well as Free monads lend themselves for constructing DSLs.

consider for example a type

data Lang r where
    LReturn     :: Var -> Lang Int
    LPrint      :: IntExpr -> Lang ()
    LAssign     :: Var -> IntExpr -> Lang ()
    LRead       :: Var -> Lang Int

this tells me that there are a couple of operations to be performed in Lang: return x print x assign x y read y.

We use GADTs here so that we can also specify what output the individual actions are going to have. This comes in quite handy if we write functions in our DSL, because their output can be tpechecked.

adding some convenience functions (that can acutally be derived):

lReturn :: Member Lang effs
        => Var -> Eff effs Int
lReturn = send . LReturn

lPrint  :: Member Lang effs
        => IntExpr -> Eff effs ()
lPrint  = send . LPrint

lAssign :: Member Lang effs
        => Var -> IntExpr -> Eff effs ()
lAssign v  i = send $ LAssign v i

lRead   :: Member Lang effs
        => Var -> Eff effs Int
lRead   = send . LRead

(this is already written using freer)

now we can use them like this: (assuming that IntExpr contains Variables and Ints)

someFunctionPrintingAnInt = do
    lAssign (Var "a") (IE_Int 12)
    lPrint (IE_Var $ Var "a")

these functions now enable you to have a DSL that can be interpreted in different ways. All needed for this is an interpreter with a specific type for effs (which is ~~ a type level list of freer monad "instances)

so freer takes the idea of the freer monads and packs it into an effect system.

this interpreter could look something like this:

runLangPure :: Eff '[Lang] Int -> Either () Int -- [StateMap]
runLangPure program = fst . fst $
    run (runWriter (runState empty (runError (reinterpret3 go program))))
  where
    go :: Lang v -> Eff '[Error (), State StateMap, Writer [String]] v
    go (LReturn var) = get >>= go (Eval stmt) >>= tell . []
    go (LPrint expr) = do
        store <- get
        value <- evalM expr
        tell [show value]
    go (LAssign var expr) = do
        value <- evalM expr
        --modify state (change var) 
    go (LRead var) = do
        strValue <- getLine
        get >>= insert var (stringToInt strValue)

the run... part specifies the initial "state" of the monads. the go part is the interpreter itself, interpreting the different possible actions.

Note that one can use the functions get and tell in the same do block even though they are part of different monads, which brings us to

I also wonder what advantages do they provide over free monads and classic mtl stacks.

the implementation allows to use monadic actions of different parts of the "monad stack" without lifting.

About the implementation:

To understand this, we look at it from a high level of abstraction: the auxiliary functions of our DSL are send to Eff effs where it is required that Member Lang effs.

So the Member constraint is just a way of declaing that Lang is in the type-level list effs in Member Lang effs. (basically typelevel elem)

The Eff monad has the functionality to "ask" the Members of the type level list of monads whether they can handle the current value (remeber, the operations are just values that are intrepreted subsequently). if so their intrepretation is executed, if not, the question is handed off to the next monad in the list.

This becomes more intuitive and understandable when spending some time in the freer-simple code base.