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]
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, 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 Mon Apr 2 02:54:55 UTC 2018
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 Thu Oct 12 05:21:29 UTC 2017
Distributions NixOS:1.0.0.4
Downloads 2114 total (45 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-10-12 [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

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

For package maintainers and hackage trustees


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.