The recursion-schemes-ext package

[Tags:benchmark, bsd3, library, test]

This package provides some exotic recursion schemes that I miss when I leave Idris.


[Skip to Readme]

Properties

Versions 0.1.0.0, 0.1.0.1, 0.1.0.2, 0.1.0.3, 0.1.0.4, 0.1.0.5, 0.1.1.0, 0.1.1.1
Dependencies base (>4.9 && <4.11), composition-prelude, deepseq, recursion-schemes (>=5.0), template-haskell [details]
License BSD3
Copyright Copyright: (c) 2017 Vanessa McHale
Author Vanessa McHale
Maintainer vanessa.mchale@reconfigure.io
Category Control
Home page https://hub.darcs.net/vmchale/recursion-schemes-ext#readme
Source repository head: git clone https://hub.darcs.net/vmchale/recursion-schemes-ext
Uploaded Fri Aug 18 00:08:49 UTC 2017 by vmchale
Distributions NixOS:0.1.1.0
Downloads 212 total (212 in the last 30 days)
Votes
0 []
Status Docs available [build log]
Last success reported on 2017-08-18 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Flags

NameDescriptionDefaultType
development

Enable -Werror

DisabledManual

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Readme for recursion-schemes-ext

Readme for recursion-schemes-ext-0.1.1.1

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.