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

Question

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?

Answer 1

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 ms into one m. That's why []'s join is concat. Applicative only lets you smash together heretofore-unrelated fs.

It's no coincidence that the free monad's Free constructor contains a whole f full of Free fs, 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 fs:

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.