# recursion-schemes-ext
This adds several functions to
[recursion-schemes](https://hackage.haskell.org/package/recursion-schemes-5.0.2),
including a `cataM`.
## 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:
```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
bertLens :: Lens' Bert Bert
bertLens = ...
ernieLens :: Lens' Ernie Ernie
ernieLens = ...
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) ernieLens bertAlgebra ernieAlgebra
collapseBertSyntaxTree :: (Recursive Bert) => Bert -> Bert
collapseBertSyntaxTree = dendro (dummy :: Ernie) bertLens ernieAlgebra bertAlgebra
```
## Anti-Pitch
This library is experimental! The API of dendromorphisms and chemamorphisms in
particular is subject to change.