Provided intersecting F-algebra, is it possible to have a catamorphism over an applicative algebra?

Question

I have this F-Algebra ( presented in the previous question ) and I want to impose an effective algebra on it. In a desperate trial, I managed to put together a monadic catamorphism that works. I wonder if it can be generalized to 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 a monadic catamorphism:

 type AlgebraM afb = ab -> fb cataM :: (Monad f, Traversable a) => AlgebraM afb -> Fix a -> fb cataM fx = f =<< (traverse (cataM f) . unFix $ x) 

And here 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 is that I could rewrite it like this:

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

Unfortunately, the value here depends on the subtree and in accordance with the document on the applicative do-notation , in this case we cannot expectorate. There seems to be no way around this; we need a monad to swim out of the depths of nesting.

It's true? Can I conclude with confidence that only flat structures can only be folded using applicative effects?

Answer 1

Is it possible to conclude with confidence that only flat structures can develop only with the help of applicative effects?

You can say it again! After all, “flattening nested structures” is exactly what makes a monad a monad, not an Applicative , which can only combine adjacent structures. Compare (version) the signatures of two abstractions:

 class Functor f => Applicative f where pure :: a -> fa (<.>) :: fa -> fb -> f (a, b) class Applicative m => Monad m where join :: m (ma) -> ma 

What Monad adds to Applicative is the ability to smooth nested m into one m . Therefore, [] join concat . Applicative only allows you to break up hitherto unrelated f s.

It is no coincidence that the free monad Free constructor contains the integer f , full of Free f s, while the free applicative constructor Ap contains only one Ap f .

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

Hopefully this will give you some intuition as to why you should expect it is not possible to collapse a tree using Applicative .

Let play small tennis to see how he trembles. We want to write

 cataA :: (Traversable f, Applicative m) => (fa -> ma) -> Fix f -> ma cataA f (Fix xs) = _ 

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

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

The hole now has the target type m (fa) -> ma . Since f :: fa -> ma knocking there, try switching under m to convert the contained f s:

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

Now we have the target type m (ma) -> ma , which is equal to join . So you need Monad .