haskellcategory-theorycatamorphism# 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.

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code