# recursion-schemes-ext

This adds several functions to
recursion-schemes,
including a `cataM`

.

At the moment, you should be careful using functions from this package. While
APIs will likely be stable, they may have poor performance.

## Pitch

### Monadic Functions

This package provides `cataM`

, `anaM`

, and `hyloM`

. That means you can have
(co)algebras that return a monadic value.

### Dendromorphisms etc.

Let's say you want to collapse a syntax tree. Suppose further that it's a
relatively involved syntax tree, and you have some data types that encapsulate
others. Here's a simple-minded example, where we collapse using traditional
recursion schemes:

```
-- | We call our co-dependent data types 'Ernie' and 'Bert'. They represent mutually recursive
data Bert = Bert Ernie
| Num Integer
| String String
| Add Bert Bert
data Ernie = Ernie Bert
| Multiply Ernie Ernie
| List [Ernie]
makeBaseFunctor ''Ernie
makeBaseFunctor ''Bert
collapseErnieSyntaxTree :: (Recursive Ernie) => Ernie -> Ernie
collapseErnieSyntaxTree = cata algebra
where algebra (ErnieF e) = Ernie $ collapseBertSyntaxTree' e
algebra (MultiplyF (Ernie (Num i)) (Ernie (Num j))) = Ernie . Num $ i * j
algebra x = embed x
collapseBertSyntaxTree :: (Recursive Bert) => Bert -> Bert
collapseBertSyntaxTree = cata algebra
where algebra (BertF e) = Bert $ collapseErnieSyntaxTree' e
algebra (AddF (Num i) (Num j)) = Num $ i + j
algebra x = embed x
```

Contrast this to the solution using a dendromorphism, viz.

```
-- | We call our co-dependent data types 'Ernie' and 'Bert'. They represent mutually recursive
data Bert = Bert Ernie
| Num Integer
| String String
| Add Bert Bert
data Ernie = Ernie Bert
| Multiply Ernie Ernie
| List [Ernie]
makeBaseFunctor ''Ernie
makeBaseFunctor ''Bert
entangleFunctors [(''Ernie, ''Bert), (''Bert, ''Ernie)]
bertAlgebra :: BertF Bert -> Bert
bertAlgebra (AddF (Num i) (Num j)) = Num $ i + j
bertAlgebra x = embed x
ernieAlgebra :: ErnieF Ernie -> Ernie
ernieAlgebra (MultiplyF (Ernie (Num i)) (Ernie (Num j))) = Ernie . Num $ i * j
ernieAlgebra x = embed x
collapseErnieSyntaxTree :: (Recursive Ernie) => Ernie -> Ernie
collapseErnieSyntaxTree = dendro (dummy :: Bert) bertAlgebra ernieAlgebra
collapseBertSyntaxTree :: (Recursive Bert) => Bert -> Bert
collapseBertSyntaxTree = dendro (dummy :: Ernie) ernieAlgebra bertAlgebra
```

## Anti-Pitch

Using dendromorphisms rather than catamorphisms is slow. As such, for the above
example, you'd probably pick the catamorphism most of the time. In fact,
dendromorphisms are really only useful on sufficiently complicated projects
where writing correct code would be difficult or inconvenient without them.

Moreover, the template Haskell isâ€¦ unwieldy. It'll definitely be shorter and
more elegant once all is said and done, but you do need to be careful to name
everything the "correct" way.