How do I implement Reader using free monads?

Question

Ok, so I have figured out how to implement `Reader` (and `ReaderT`, not shown) using the `operational` package: ``` {-# LANGUAGE GADTs, ScopedTypeVariables #-} import Control.Monad.Operational data ReaderI r a where Ask :: ReaderI r r type Reader r a = Program (ReaderI r) a ask :: Reader r r ask = singleton Ask runReader :: forall r a. Reader r a -> r -> a runReader = interpretWithMonad evalI where evalI :: forall b. ReaderI r b -> (r -> b) evalI Ask = id ``` But I can't figure out for my life how to do this with free monads (I'm using Edward Kmett's `free` package). The closest I've gotten is this, which I understand is cheating (something about how `((->) r)` is already a monad): ``` import Control.Monad.Free type Reader r a = Free ((->) r) a ask :: Reader r r ask = Free Pure runReader :: Reader r a -> r -> a runReader (Pure a) _ = a runReader (Free k) r = runReader (k r) r -- Or, more simply and tellingly: -- -- > runReader = retract ``` Even if this wasn't as dumb as I suspect it…

Accepted Answer

I don't think it can be done except they way you have. But, I don't think this is unique to reader. Consider the free monad version of writer

```
data WriterF m a = WriterF m a deriving (Functor)

type Writer m = Free (WriterF m)
```

obviously, `WriterF` is isomorphic to writer, but this does behave the way we would expect with the simple algebra

```
algebraWriter :: Monoid m => WriterF m (m,a) -> (m,a)
algebraWriter (WriterF m1 (m2,a)) = (m1 <> m2,a)
```

thus

```
runWriter :: Monoid m => Writer m a -> (m,a)
runWriter (Pure a) = (mempty,a)
runWriter (Free x) = algebraWriter . fmap runWriter $ x
```

Similarly, I think of the Free reader as

```
type ReaderF r = (->) r

type Reader r = Free (ReaderF r)
```

I like this, because adding them gives you the state monad

```
type State x = Free ((ReaderF x) :+: (WriterF x))

runState :: State x a -> x -> (a,x)
runState (Pure a) x                    = (a,x)
runState (Free (Inl f)) x              = runState (f x) x
runState (Free (Inr (WriterF x f))) _  = runState f x
```

Note, that your operational solution could be made to work with `Free` by using the "free functor", as can anything that works with operational

```
data FreeFunctor f x = forall a. FreeFunctor (f a) (a -> x)
```

but, that `FreeFunctor ReaderI` is also isomorphic to `(->)`.

How do I implement Reader using free monads?

Solution

Problem