In my last post, I explored the problem of Applicative effects in free monads. After some great discussion between Edward Kmett, Dave Menendez, /u/MitchellSalad, and myself, I think I’ve come to a new understanding.

For reference, here’s my “free monad given an applicative.”

```
data Free f a where
Pure :: a -> Free f a
Free :: f (Free f a) -> Free f a
instance Functor f => Functor (Free f) where
fmap f (Pure a) = Pure (f a)
fmap f (Free a) = Free (fmap (fmap f) a)
instance Applicative f => Applicative (Free f) where
pure = Pure
Pure f <*> a = fmap f a
Free f <*> Pure a = Free $ fmap (fmap ($ a)) f
Free f <*> Free a = Free (fmap (<*>) f <*> a)
instance Applicative f => Monad (Free f) where
Pure a >>= k = k a
Free a >>= k = Free (fmap (>>= k) a)
```

The core of the issue is that under my implementation,
`(<*>)`

was purposefully different than `ap`

.
Turns out, it’s a law that `(<*>)`

must be morally equivalent to `ap`

.
So if the two turn out effectively different, that’s illegal.

Dave Menendez gave a good counter example to the original post using `Const`

.

```
instance Monoid m => Applicative (Const m) where
pure _ = mempty
Const f <*> Const v = Const (f `mappend` v)
liftFree (Const "a") <*> liftFree (Const "b") = Free (Const "ab")
liftFree (Const "a") `ap` liftFree (Const "b") = Free (Const "a")
```

As you can see, `(<*>)`

gives a fundamentally different answer than `ap`

.

### Cheating on the Ap Test

The truth is, `(<*>)`

doesn’t have to literally be assigned `ap`

.
`(<*>)`

just has to be *morally* equivalent to `ap`

.
In the `Const`

example, morally different results were computed.
But in my original example with Haxl, the results were legal.
The difference is that with `Const`

,
`(<*>)`

is morally different than anything `ap`

could ever do.
It basically shouldn’t be legal to interpret `Free (Const m)`

.

According to Edward Kmett, it’s all up to interpretation!
The solution is to provide a limited view into `Free`

.
If the interpreter of the free monad agrees to certain laws,
then interpretation can be guaranteed valid.
Essentially, we’re shifting the burden of proof for `(<*>) = ap`

to the interpreter.

Let’s recall the Applicative-optimized instance of Applicative for Free.

```
instance Applicative f => Applicative (Free f) where
pure = Pure
Pure a <*> Pure b = Pure $ a b
Pure a <*> Free mb = Free $ fmap a <$> mb
Free ma <*> Pure b = Free $ fmap ($ b) <$> ma
Free ma <*> Free mb = Free $ fmap (<*>) ma <*> mb -- <- The important line
```

In that last line, `(<*>)`

is used on the `f`

Applicative.
We’re basically asking `f`

to perform this computation.
So we know that as long as `f`

is being responsible with `(<*>)`

,
we will get a correct applicative computation.
The question then, is how to use this to make a correct monadic computation?

For a simple example, let’s turn to `retract`

.
This function doesn’t actually need any porting to work with this `Free`

.

```
retract :: Monad f => Free f a -> f a
retract (Pure a) = return a
retract (Free as) = as >>= retract
```

If `(<*>) = ap`

in `f`

, which it has to, then all the work is done for us.
There’s no way to construct a computation that can misuse `(<*>)`

and `ap`

to
break `f`

’s monad laws.

But what about examples where `f`

isn’t a monad?
The simplest way to use these `f`

s is with `foldFree`

.

```
foldFree :: (Functor f, Monad m) => (forall x . f x -> m x) -> Free f a -> m a
foldFree _ (Pure a) = return a
foldFree f (Free as) = f as >>= foldFree f
```

In the conventional `Free`

, the first parameter is a natural transformation.
Given any `f`

, create a corresponding `m`

,
and `foldFree`

will handle the monadic bits.
But this interpreter won’t work with the Applicative-optimized `Free`

.
Well, it will compile and run just fine.
It just won’t produce law-abiding results.
Given that `f`

is actually an Applicative,
and `(<*>)`

was used in the computation, it’s possible that the natural
transformation doesn’t correctly transcribe applicative effects.
If this is the case, we don’t know for sure that the `m`

s returned are correct,
so we don’t know that the result is equivalent to using `ap`

.

That natural transformation has to be something stronger.
It has to preserve the meaning of applicative computations between `f`

and `m`

.
So it needs to be an applicative homomorphism.
That is, it needs to be a natural transformation that obeys these laws.

```
hm :: (Applicative f, Applicative m) => f x -> m x
hm (pure a) = pure a
hm (f <*> g) = hm f <*> hm g
```

In code, the only change we can make is strengthening that `Functor`

constraint.

```
foldFree :: (Applicative f, Monad m) => (forall x . f x -> m x) -> Free f a -> m a
foldFree _ (Pure a) = return a
foldFree f (Free as) = f as >>= foldFree f
```

We just have to take for granted that the user is supplying
a natural transformation that obeys those laws.
If it does,
then we know that the meanings of applicative computations are being preserved.
Then, as with `retract`

, the rest is properly guaranteed by the monad laws.

### Back to Freer

So what about the `Freer`

monad?
Considering, once again, that we have a free applicative,
which takes any type of kind `* -> *`

,
we can get the freer monad the same way as before.

```
type Freer f = Free (Ap f)
```

Now the interpreter’s job is to take `Ap`

,
which is effectively a linked list of `f`

s,
and use those `f`

s to make an applicative homomorphism.
Now, we have a freer monad that turns any `* -> *`

into a monad,
and allows the interpreter to optimize applicative effects.

It’s still extremely slow.
I plan to look into church encoding it to improve the performance.
But I’m not sure if that will work well with `(<*>)`

.
Anyway, I’m very happy just knowing a solution for this exists.
Let me know if I’ve made any other mistakes.