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

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.