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