The recursion-schemes-ext package

[ Tags: bsd3, control, library ] [ Propose Tags ]

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, 0.2.0.0, 0.2.0.1, 0.2.1.0
Dependencies base (>4.9 && <4.11), composition-prelude, deepseq, lens, 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 Thu Oct 12 05:21:29 UTC 2017 by vmchale
Distributions NixOS:0.2.0.1
Downloads 371 total (71 in the last 30 days)
Rating 0.0 (0 ratings) [clear 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

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.