# Granted a traversable F-Algebra, is it possible to have a catamorphism over an applicative algebra?

I have this F-Algebra (introduced in a previous question), and I want to cast an effectful algebra upon it. Through desperate trial, I managed to put together a monadic catamorphism that works. I wonder if it may be generalized to an applicative, and if not, why.

This is how I defined `Traversable`:

``````instance Traversable Expr where
traverse f (Branch xs) = fmap Branch \$ traverse f xs
traverse f (Leaf   i ) = pure \$ Leaf i
``````

This is the monadic catamorphism:

``````type AlgebraM a f b = a b -> f b

cataM :: (Monad f, Traversable a) => AlgebraM a f b -> Fix a -> f b
cataM f x = f =<< (traverse (cataM f) . unFix \$ x)
``````

And this is how it works:

``````λ let printAndReturn x = print x >> pure x
λ cataM (printAndReturn . evalSum) \$ branch [branch [leaf 1, leaf 2], leaf 3]
1
2
3
3
6
6
``````

My idea now is that I could rewrite like this:

``````cataA :: (Applicative f, Traversable a) => AlgebraM a f b -> Fix a -> f b
cataA f x = do
subtree <- traverse (cataA f) . unFix \$ x
value <- f subtree
return value
``````

Unfortunately, `value` here depends on `subtree` and, according to a paper on applicative do-notation, in such case we cannot desugar to Applicative. It seems like there's no way around this; we need a monad to float up from the depths of nesting.

Is it true? Can I safely conclude that only flat structures can be folded with applicative effects alone?

Solution

• Can I safely conclude that only flat structures can be folded with applicative effects alone?

You can say that again! After all, "flattening nested structures" is exactly what makes a monad a monad, rather than `Applicative` which can only combine adjacent structures. Compare (a version of) the signatures of the two abstractions:

``````class Functor f => Applicative f where
pure :: a -> f a
(<.>) :: f a -> f b -> f (a, b)

class Applicative m => Monad m where
join :: m (m a) -> m a
``````

What `Monad` adds to `Applicative` is the ability to flatten nested `m`s into one `m`. That's why `[]`'s `join` is `concat`. `Applicative` only lets you smash together heretofore-unrelated `f`s.

It's no coincidence that the free monad's `Free` constructor contains a whole `f` full of `Free f`s, whereas the free applicative's `Ap` constructor only contains one `Ap f`.

``````data Free f a = Return a | Free (f (Free f a))
data Ap f a where
Pure :: a -> Ap f a
Cons :: f a -> Ap f b -> Ap f (a, b)
``````

Hopefully that gives you some intuition as to why you should expect that it's not possible to fold a tree using an `Applicative`.

Let's play a little type tennis to see how it shakes out. We want to write

``````cataA :: (Traversable f, Applicative m) => (f a -> m a) -> Fix f -> m a
cataA f (Fix xs) = _
``````

We have `xs :: f (Fix f)` and a `Traversable` for `f`. My first instinct here is to `traverse` the `f` to fold the contained subtrees:

``````cataA f (Fix xs) = _ \$ traverse (cataA f) xs
``````

The hole now has a goal type of `m (f a) -> m a`. Since there's an `f :: f a -> m a` knocking about, let's try going under the `m` to convert the contained `f`s:

``````cataA f (Fix xs) = _ \$ fmap f \$ traverse (cataA f) xs
``````

Now we have a goal type of `m (m a) -> m a`, which is `join`. So you do need a `Monad` after all.