recursion-schemes-ext 0.2.1.0 → 1.0.0.0

raw patch · 9 files changed

+132/−219 lines, 9 filesdep −template-haskelldep ~recursion-schemesPVP ok

version bump matches the API change (PVP)

Dependencies removed: template-haskell

Dependency ranges changed: recursion-schemes

API changes (from Hackage documentation)

Files

• .travis.yml +0/−18
• README.md +3/−77
• bench/Bench.hs +4/−5
• recursion-schemes-ext.cabal +10/−8
• src/Data/Functor/Foldable/Examples.hs +0/−77
• src/Data/Functor/Foldable/Exotic.hs +12/−17
• stack.yaml +0/−9
• test/Examples.hs +96/−0
• test/Spec.hs +7/−8

@@ -1,18 +0,0 @@-sudo: false-language: default-cache:-  directories:-  - $HOME/.stack-addons:-    apt:-        packages:-            - libgmp3-dev-before_install:-- mkdir -p ~/.local/bin-- export PATH=$HOME/.local/bin:$PATH-- travis_retry curl -L https://www.stackage.org/stack/linux-x86_64 | tar xz --wildcards --strip-components=1 -C ~/.local/bin '*/stack'-- chmod a+x ~/.local/bin/stack-install:-- stack --no-terminal --install-ghc test --only-dependencies-script:-- stack --no-terminal test --bench --haddock --no-haddock-deps

@@ -4,85 +4,11 @@ [recursion-schemes](https://hackage.haskell.org/package/recursion-schemes-5.0.2), including a `cataM`. -## Pitch--### Monadic Functions+## 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:--```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--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+## Dendromorphisms etc. -This library is experimental! The API of dendromorphisms and chemamorphisms in-particular is subject to change.+This section of documentation is under construction.

@@ -1,10 +1,9 @@ module Main where -import           Criterion.Main                 (bench, bgroup, defaultMain, nf)-import           Data.Functor.Foldable.Examples (Bert (Add, Bert, Num),-                                                 Ernie (Ernie, Multiply),-                                                 collapseBertSyntaxTree,-                                                 collapseBertSyntaxTree')+import           Criterion.Main (bench, bgroup, defaultMain, nf)+import           Examples       (Bert (Add, Bert, Num), Ernie (Ernie, Multiply),+                                 collapseBertSyntaxTree,+                                 collapseBertSyntaxTree')  bert :: Bert bert = Add (Num 2) (Num 3)

@@ -1,7 +1,7 @@ name:                recursion-schemes-ext-version:             0.2.1.0+version:             1.0.0.0 synopsis:            Amateur addenda to recursion-schemes-description:         This package provides some exotic recursion schemes that I miss when I leave Idris.+description:         This package provides some exotic recursion schemes as well monadic versions of some morphisms. homepage:            https://hub.darcs.net/vmchale/recursion-schemes-ext#readme license:             BSD3 license-file:        LICENSE@@ -12,8 +12,6 @@ build-type:          Simple stability:           experimental extra-source-files:  README.md-                   , stack.yaml-                   , .travis.yml cabal-version:       >=1.10  Flag development {@@ -25,13 +23,10 @@ library   hs-source-dirs:      src   exposed-modules:     Data.Functor.Foldable.Exotic-                     , Data.Functor.Foldable.Examples   build-depends:       base > 4.9 && < 4.11                      , recursion-schemes >= 5.0                      , lens                      , composition-prelude-                     , deepseq-                     , template-haskell   default-language:    Haskell2010   if flag(development)     ghc-options:       -Werror@@ -41,8 +36,11 @@   type:                exitcode-stdio-1.0   hs-source-dirs:      test   main-is:             Spec.hs+  other-modules:       Examples   build-depends:       base                      , recursion-schemes-ext+                     , recursion-schemes >= 5.0+                     , deepseq                      , hspec   ghc-options:         -threaded -rtsopts -with-rtsopts=-N   default-language:    Haskell2010@@ -53,11 +51,15 @@ benchmark recursion-schemes-bench   type:                exitcode-stdio-1.0   hs-source-dirs:      bench+                     , test   main-is:             Bench.hs+  other-modules:       Examples   build-depends:       base                      , recursion-schemes-ext                      , criterion-  ghc-options:         -threaded -rtsopts -with-rtsopts=-N -O3+                     , recursion-schemes+                     , deepseq+  ghc-options:         -O2   default-language:    Haskell2010   if flag(development)     ghc-options:       -Werror

@@ -1,77 +0,0 @@-{-# LANGUAGE AllowAmbiguousTypes   #-}-{-# LANGUAGE DeriveAnyClass        #-}-{-# LANGUAGE DeriveFoldable        #-}-{-# LANGUAGE DeriveFunctor         #-}-{-# LANGUAGE DeriveGeneric         #-}-{-# LANGUAGE DeriveTraversable     #-}-{-# LANGUAGE FlexibleContexts      #-}-{-# LANGUAGE MultiParamTypeClasses #-}-{-# LANGUAGE TemplateHaskell       #-}-{-# LANGUAGE TypeFamilies          #-}---- | This module contains an example used by the test suite.-module Data.Functor.Foldable.Examples ( -- * Data Types-                                        Bert (..)-                                      , Ernie (..)-                                      , BertF (..)-                                      , ErnieF (..)-                                      -- * Catamorphisms-                                      , collapseErnieSyntaxTree-                                      , collapseErnieSyntaxTree'-                                      , collapseBertSyntaxTree-                                      , collapseBertSyntaxTree'-                                      ) where--import           Control.DeepSeq              (NFData)-import           Data.Functor.Foldable-import           Data.Functor.Foldable.Exotic-import           Data.Functor.Foldable.TH-import           GHC.Generics                 (Generic)---- | 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-           deriving (Show, Eq, Generic, NFData)--data Ernie = Ernie Bert-           | Multiply Ernie Ernie-           | List [Ernie]-           deriving (Show, Eq, Generic, NFData)--makeBaseFunctor ''Ernie-makeBaseFunctor ''Bert---- | BertF-algebra-bertAlgebra :: BertF Bert -> Bert-bertAlgebra (AddF (Num i) (Num j)) = Num $ i + j-bertAlgebra x                      = embed x---- | ErnieF-algebra-ernieAlgebra :: ErnieF Ernie -> Ernie-ernieAlgebra (MultiplyF (Ernie (Num i)) (Ernie (Num j))) = Ernie . Num $ i * j-ernieAlgebra x                                           = embed x---- | Dendromorphism collapsing the tree. Note that we can use the same--- F-algebras here as we would in a normal catamorphism.-collapseErnieSyntaxTree :: (Recursive Ernie, Recursive Bert) => Ernie -> Ernie-collapseErnieSyntaxTree = dendro undefined bertAlgebra ernieAlgebra---- | We can generate two functions by swapping the F-algebras and the dummy--- type.-collapseBertSyntaxTree :: (Recursive Bert, Recursive Ernie) => Bert -> Bert-collapseBertSyntaxTree = dendro undefined ernieAlgebra bertAlgebra---- | Catamorphism, which collapses the tree the usual way.-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

@@ -17,12 +17,14 @@     , hyloM     -- * Recursion schemes for interdependent data types     , dendro-    , symplecto+    , scolio     , chema     -- * Exotic recursion schemes     , dicata     , micro     , mutu+    -- * Data type for transformations+    , Trans     ) where  import           Control.Arrow@@ -30,25 +32,25 @@ import           Control.Lens import           Data.Functor.Foldable ---margaritari ::+-- margaritari :: --- TODO-type UnsafePrism s a = ∀ f. Functor f => (f a -> a) -> f s -> s+-- | A map of F-algebras+type Trans s a = ∀ f. Functor f => (f a -> a) -> f s -> s --- | Just wanted this available somewhere+-- | Mutumorphism mutu :: Recursive t => (Base t (b, a) -> b) -> (Base t (b, a) -> a) -> t -> a mutu f g = snd . cata (f &&& g) --- | Entangle two hylomorphisms. Not the same thing as a symplectomorphism from geometry.-symplecto :: (Functor f, Functor g)-    => ((f b -> b) -> UnsafePrism b b) -- ^ A prism parametric in an F-algebra that allows `b` to inspect itself.+-- | Entangle two hylomorphisms.+scolio :: (Functor f, Functor g)+    => ((f b -> b) -> Trans b b) -- ^ A prism parametric in an F-algebra that allows `b` to inspect itself.     -> ((a -> f a) -> Lens' a a) -- ^ A lens parametric in an F-coalgebra that allows `b` to inspect itself.     -> (g b -> b) -- ^ A g-algebra     -> (a -> g a) -- ^ A g-coalgebra     -> (f b -> b) -- ^ An f-algebra     -> (a -> f a) -- ^ An f-coalgebra     -> a -> b-symplecto p l alg coalg alg' coalg' = hylo (p alg' alg) (l coalg' coalg)+scolio p l alg coalg alg' coalg' = hylo (p alg' alg) (l coalg' coalg)  -- Entangle two anamorphisms. chema :: (Corecursive t', Functor f)@@ -58,12 +60,9 @@     -> b -> t' chema = (ana .*) --- better idea: have a function to lift any f-algebra into a (f . w)-algebra for w a comonad--- ℤ ∀ ∈ ≠ ≤ ≥ ⇒ → ∧ ∨ ¬ 𝔹 ≡ ∪ ⊕ ∅--- -- | A dendromorphism entangles two catamorphisms dendro :: (Recursive t', Functor f)-    => ((f a -> a) -> UnsafePrism b b) -- ^ A prism parametric in an F-algebra that allows `b` to inspect itself.+    => ((f a -> a) -> Trans b b) -- ^ A prism parametric in an F-algebra that allows `b` to inspect itself.     -> (f a -> a) -- ^ A (Base t)-algebra     -> (Base t' b -> b) -- ^ A (Base t')-algebra     -> t' -> b@@ -88,7 +87,3 @@ -- | A monadic hylomorphism hyloM :: (Functor f, Monad m, Traversable f) => (f b -> m b) -> (a -> m (f a)) -> a -> m b hyloM phi psi = h where h = phi <=< mapM h <=< psi---- | Unicode synonym for `cata`--- 🐱 :: Recursive t => (Base t a -> a) -> t -> a--- 🐱 = cata

@@ -1,9 +0,0 @@-resolver: lts-9.1-packages:-- '.'-extra-deps:-    - composition-prelude-0.1.0.4-flags:-    recursion-schemes-ext:-        development: true-extra-package-dbs: []

@@ -0,0 +1,96 @@+{-# LANGUAGE AllowAmbiguousTypes   #-}+{-# LANGUAGE DeriveAnyClass        #-}+{-# LANGUAGE DeriveFoldable        #-}+{-# LANGUAGE DeriveFunctor         #-}+{-# LANGUAGE DeriveGeneric         #-}+{-# LANGUAGE DeriveTraversable     #-}+{-# LANGUAGE FlexibleContexts      #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE RankNTypes            #-}+{-# LANGUAGE TemplateHaskell       #-}+{-# LANGUAGE TypeFamilies          #-}++-- | This module contains an example used by the test suite.+module Examples ( -- * Data Types+         Bert (..)+       , Ernie (..)+       , BertF (..)+       , ErnieF (..)+       -- * Catamorphisms+       , collapseErnieSyntaxTree+       , collapseErnieSyntaxTree'+       , collapseBertSyntaxTree+       , collapseBertSyntaxTree'+       ) where++import           Control.DeepSeq              (NFData)+import           Data.Functor.Foldable+import           Data.Functor.Foldable.Exotic+import           Data.Functor.Foldable.TH+import           GHC.Generics                 (Generic)++-- | 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+           deriving (Show, Eq, Generic, NFData)++data Ernie = Ernie Bert+           | Multiply Ernie Ernie+           | List [Ernie]+           deriving (Show, Eq, Generic, NFData)++makeBaseFunctor ''Ernie+makeBaseFunctor ''Bert++-- TODO bifunctor ??+ernieHelper :: (BertF Bert -> Bert) -> Trans Ernie Ernie+ernieHelper alg = (mapErnie g .) -- . (. fmap (mapErnie g))+    where g (Ernie b) = Ernie $ dendro bertHelper ernieAlgebra alg b+          g x         = x+          mapErnie f (Ernie (Bert e)) = mapErnie f e+          mapErnie f (Multiply e e') = Multiply (mapErnie f e) (mapErnie f e')+          mapErnie f (List es) = List (mapErnie f <$> es)+          mapErnie f e = f e++bertHelper :: (ErnieF Ernie -> Ernie) -> Trans Bert Bert -- TODO more flexible data type that allows us to use BertF or whatever+bertHelper alg = (mapBert g .) . (. fmap (mapBert g))+    where g (Bert e) = Bert $ dendro ernieHelper bertAlgebra alg e -- FIXME cata alg e?+          g x        = x+          mapBert f (Bert (Ernie b)) = mapBert f b+          mapBert f (Add b b')       = Add (mapBert f b) (mapBert f b')+          mapBert f x                = f x++-- | BertF-algebra+bertAlgebra :: BertF Bert -> Bert+bertAlgebra (AddF (Num i) (Num j)) = Num $ i + j+bertAlgebra x                      = embed x++-- | ErnieF-algebra+ernieAlgebra :: ErnieF Ernie -> Ernie+ernieAlgebra (MultiplyF (Ernie (Num i)) (Ernie (Num j))) = Ernie . Num $ i * j+ernieAlgebra x                                           = embed x++-- | Dendromorphism collapsing the tree. Note that we can use the same+-- F-algebras here as we would in a normal catamorphism.+collapseErnieSyntaxTree :: (Recursive Ernie, Recursive Bert) => Ernie -> Ernie+collapseErnieSyntaxTree = dendro ernieHelper bertAlgebra ernieAlgebra++-- | We can generate two functions by swapping the F-algebras and the dummy+-- type.+collapseBertSyntaxTree :: (Recursive Bert, Recursive Ernie) => Bert -> Bert+collapseBertSyntaxTree = dendro bertHelper ernieAlgebra bertAlgebra++-- | Catamorphism, which collapses the tree the usual way.+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

@@ -1,10 +1,7 @@-import           Data.Functor.Foldable.Examples (Bert (Add, Bert, Num),-                                                 Ernie (Ernie, Multiply),-                                                 collapseBertSyntaxTree,-                                                 collapseErnieSyntaxTree,-                                                 collapseErnieSyntaxTree')-import           Test.Hspec                     (describe, hspec, it, parallel,-                                                 shouldBe)+import           Examples   (Bert (Add, Bert, Num), Ernie (Ernie, Multiply),+                             collapseBertSyntaxTree, collapseErnieSyntaxTree,+                             collapseErnieSyntaxTree')+import           Test.Hspec (describe, hspec, it, parallel, shouldBe)  bertSum :: Bert bertSum = Add (Num 2) (Num 3)@@ -35,5 +32,7 @@             collapseErnieSyntaxTree' ernieMult `shouldBe` collapseErnieSyntaxTree ernieMult         parallel $ it "collapses complex syntax trees" $             collapseBertSyntaxTree bertComplex `shouldBe` Num 18-        parallel $ it "should work would when triply wrapped" $+        parallel $ it "should work would when triply wrapped (1/2)" $+            collapseErnieSyntaxTree (Ernie (Bert (Ernie (Num 15)))) `shouldBe` resultErnie+        parallel $ it "should work would when triply wrapped (2/2)" $             collapseErnieSyntaxTree (Ernie (Bert ernieComplex)) `shouldBe` resultErnie