# recursion-schemes-ext
This adds several functions to
[recursion-schemes](https://hackage.haskell.org/package/recursion-schemes-5.0.2),
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
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:
```haskell
-- | 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.
```haskell
-- | 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 (ErnieF (Bert e)) = e
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.