recursion-schemes-ext: Amateur addenda to recursion-schemes

[ bsd3, control, library ] [ Propose Tags ]

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


[Skip to Readme]

Flags

Manual Flags

NameDescriptionDefault
development

Enable `-Werror`

Disabled

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

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 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, 0.2.0.0, 0.2.0.1, 0.2.1.0, 1.0.0.0, 1.0.0.1, 1.0.0.2, 1.0.0.3, 1.0.0.4
Dependencies base (>4.9 && <4.11), composition-prelude (<1.2.0.0), deepseq, lens, recursion-schemes (>=5.0), template-haskell [details]
License BSD-3-Clause
Copyright Copyright: (c) 2017 Vanessa McHale
Author Vanessa McHale
Maintainer vanessa.mchale@reconfigure.io
Revised Revision 1 made by vmchale at 2018-04-02T02:54:55Z
Category Control
Home page https://hub.darcs.net/vmchale/recursion-schemes-ext#readme
Source repo head: git clone https://hub.darcs.net/vmchale/recursion-schemes-ext
Uploaded by vmchale at 2017-10-12T05:21:29Z
Distributions NixOS:1.0.0.4
Reverse Dependencies 2 direct, 1 indirect [details]
Downloads 8992 total (31 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-10-12 [all 1 reports]

Readme for recursion-schemes-ext-0.2.1.0

[back to package description]

recursion-schemes-ext

This adds several functions to recursion-schemes, 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:

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

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.