2 -----------------------------------------------------------------------------
4 -- Module : Generics.Pointless.RecursionPatterns
5 -- Copyright : (c) 2008 University of Minho
8 -- Maintainer : hpacheco@di.uminho.pt
9 -- Stability : experimental
10 -- Portability : non-portable
13 -- point-free programming with recursion patterns as hylomorphisms
15 -- This module defines recursion patterns as hylomorphisms.
17 -- Recursion patterns can be seen as high-order functions that encapsulate typical forms of recursion.
18 -- The hylomorphism recursion pattern was first defined in <http://research.microsoft.com/~emeijer/Papers/CWIReport.pdf>,
19 -- along with its relation with derived more specific recursion patterns such as catamorphisms, anamorphisms and paramorphisms.
21 -- The seminal paper that introduced point-free programming and defined many of the laws for catamorphisms and anamorphisms
22 -- can be found in <http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf>.
24 -- More complex and exotic recursion patterns have been discovered later, such as accumulations, apomorphisms, zygomorphisms,
25 -- histomorphisms, futumorphisms, dynamorphisms or chronomorphisms.
27 -----------------------------------------------------------------------------
29 module Generics.Pointless.RecursionPatterns where
31 import Generics.Pointless.Combinators
32 import Generics.Pointless.Functors
33 import Control.Monad.Instances hiding (Functor(..))
34 import Prelude hiding (Functor(..))
36 -- | Definition of an hylomorphism
37 hylo :: Functor (PF b) => b -> (F b c -> c) -> (a -> F b a) -> a -> c
38 hylo b g h = g . pmap b (hylo b g h) . h
40 -- | Definition of a catamorphism as an hylomorphism.
42 -- Catamorphisms model the fundamental pattern of iteration, where constructors for recursive datatypes are repeatedly consumed by arbitrary functions.
43 -- They are usually called folds.
44 cata :: (Mu a,Functor (PF a)) => a -> (F a b -> b) -> a -> b
45 cata a f = hylo a f out
47 -- | Recursive definition of a catamorphism.
48 cataRec :: (Mu a,Functor (PF a)) => a -> (F a b -> b) -> a -> b
49 cataRec a f = f . pmap a (cataRec a f) . out
51 -- | Definition of an anamorphism as an hylomorphism.
53 -- Anamorphisms resembles the dual of iteration and, hence, deï¬ne the inverse of catamorphisms.
54 -- Instead of consuming recursive types, they produce values of those types.
55 ana :: (Mu b,Functor (PF b)) => b -> (a -> F b a) -> a -> b
58 -- | Recursive definition of an anamorphism.
59 anaRec :: (Mu b,Functor (PF b)) => b -> (a -> F b a) -> a -> b
60 anaRec b f = inn . pmap b (anaRec b f) . f
62 -- | The functor of intermediate type of a paramorphism is the functor of the consumed type 'a'
63 -- extended with an extra annotation to itself in recursive definitions.
64 type Para a = a :@!: (I :*!: K a)
66 -- | Definition of a paramorphism.
68 -- Paramorphisms supply the gene of a catamorphism with a recursively computed copy of the input.
70 -- The first introduction to paramorphisms is reported in <http://www.cs.uu.nl/research/techreps/repo/CS-1990/1990-04.pdf>.
71 para :: (Mu a,Functor (PF a)) => a -> (F a (b,a) -> b) -> a -> b
72 para (a::a) f = hylo (_L :: Para a) f (pmap a (idA /\ idA) . out)
76 -- | Recursive definition of a paramorphism.
77 paraRec :: (Mu a,Functor (PF a)) => a -> (F a (b,a) -> b) -> a -> b
78 paraRec (a::a) f = f . pmap a (paraRec a f >< idA) . pmap a (idA /\ idA) . out
82 -- | The functor of intermediate type of a paramorphism is the functor of the generated type 'b'
83 -- with an alternative annotation to itself in recursive definitions.
84 type Apo b = b :@!: (I :+!: K b)
86 -- | Definition of an apomorphism as an hylomorphism.
88 -- Apomorphisms are the dual recursion patterns of paramorphisms, and therefore they can express functions deï¬ned by primitive corecursion.
90 -- They were introduced independently in <http://www.cs.ut.ee/~varmo/papers/nwpt97.ps.gz> and /Program Construction and Generation Based on Recursive Types, MSc thesis/.
91 apo :: (Mu b,Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> b
92 apo (b::b) f = hylo (_L :: Apo b) (inn . pmap b (idB \/ idB)) f
96 -- | Recursive definition of an apomorphism.
97 apoRec :: (Mu b,Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> b
98 apoRec (b::b) f = (inn . pmap b (idB \/ idB) . pmap b (apoRec b f -|- idB) . f)
102 -- | In zygomorphisms we extend the recursive occurences in the base functor functor of type 'a' with an extra annotation 'b'.
103 type Zygo a b = a :@!: (I :*!: K b)
105 -- | Definition of a zygomorphism as an hylomorphism.
107 -- Zygomorphisms were introduced in <http://dissertations.ub.rug.nl/faculties/science/1990/g.r.malcolm/>.
109 -- They can be seen as the asymmetric form of mutual iteration, where both a data consumer and an auxiliary function are defined (<http://www.fing.edu.uy/~pardo/papers/njc01.ps.gz>).
110 zygo :: (Mu a, Functor (PF a),F a (a,b) ~ F (Zygo a b) a) => a -> (F a b -> b) -> (F (Zygo a b) b -> b) -> a -> b
111 zygo a g f = aux a (_L :: b) g f
112 where aux :: (Mu a,Functor (PF a),F a (a,b) ~ F (Zygo a b) a) => a -> b -> (F a b -> b) -> (F (Zygo a b) b -> b) -> a -> b
113 aux (a::a) (b::b) g f = hylo (_L :: Zygo a b) f (pmap a (id /\ cata a g) . out)
115 -- | In accumulations we add an extra annotation 'b' to the base functor of type 'a'.
116 type Accum a b = a :*!: K b
118 -- | Definition of an accumulation as an hylomorphism.
120 -- Accumulations <http://www.fing.edu.uy/~pardo/papers/wcgp02.ps.gz> are binary functions that use the second parameter to store intermediate results.
122 -- The so called "accumulation technique" is tipically used in functional programming to derive efficient implementations of some recursive functions.
123 accum :: (Mu a,Functor (PF d)) => d -> ((F a a,b) -> F d (a,b)) -> (F (Accum d b) c -> c) -> (a,b) -> c
124 accum (d::d) g f = hylo (_L :: Accum d b) f ((g /\ snd) . (out >< id))
126 -- | In histomorphisms we add an extra annotation 'c' to the base functor of type 'a'.
127 type Histo a c = K c :*!: a
129 -- | Definition of an histomorphism as an hylomorphism (as long as the catamorphism is defined as an hylomorphism).
131 -- Histomorphisms (<http://cs.ioc.ee/~tarmo/papers/inf.ps.gz>) capture the powerfull schemes of course-of-value iteration, and differ from catamorphisms for being able to apply the gene function at a deeper depth of recursion.
132 -- In other words, they allow to reuse sub-sub constructor results.
133 histo :: (Mu a,Functor (PF a)) => a -> (F a (Histo a c) -> c) -> a -> c
134 histo (a::a) g = fst . outH . cata a (inn . (g /\ id))
135 where outH :: Histo a c -> F (Histo a c) (Histo a c)
138 -- | The combinator 'outl' unpacks the functor of an histomorphism and selects the annotation.
139 outl :: Histo a c -> c
142 -- | The combinator 'outr' unpacks the functor of an histomorphism and discards the annotation.
143 outr :: Histo a c -> F a (Histo a c)
146 -- | In futumorphisms we add an alternative annotation 'c' to the base functor of type 'b'.
147 type Futu b c = K c :+!: b
149 -- | Definition of a futumorphism as an hylomorphism (as long as the anamorphism is defined as an hylomorphism).
151 -- Futumorphisms are the dual of histomorphisms and are proposed as 'cocourse-of-argument' coiterators by their creators (<http://cs.ioc.ee/~tarmo/papers/inf.ps.gz>).
153 -- In the same fashion as histomorphisms, it allows to seed the gene with multiple levels of depth instead of having to do 'all at once' with an anamorphism.
154 futu :: (Mu b,Functor (PF b)) => b -> (a -> F b (Futu b a)) -> a -> b
155 futu (b::b) g = ana b ((g \/ id) . out) . innF . inl
156 where innF :: F (Futu b a) (Futu b a) -> Futu b a
159 -- | The combinator 'innl' packs the functor of a futumorphism from the base functor.
160 innl :: c -> Futu b c
163 -- | The combinator 'innr' packs the functor of an futumorphism from an annotation.
164 innr :: F b (Futu b c) -> Futu b c
167 -- | Definition of a dynamorphism as an hylomorphisms.
169 -- Dynamorphisms (<http://math.ut.ee/~eugene/kabanov-vene-mpc-06.pdf>) are a more general form of histomorphisms for capturing dynaming programming constructions.
171 -- Instead of following the recursion pattern of the input via structural recursion (as in histomorphisms),
172 -- dynamorphisms allow us to reuse the annotated structure in a bottom-up approach and avoiding rebuilding
173 -- it every time an annotation is needed, what provides a more efficient dynamic algorithm.
174 dyna :: (Mu b, Functor (PF b)) => b -> (F b (Histo b c) -> c) -> (a -> F b a) -> a -> c
175 dyna (b::b) g h = fst . outH . hylo b (inn . (g /\ id)) h
176 where outH :: Histo b c -> F (Histo b c) (Histo b c)
179 -- | Definition of a chronomorphism as an hylomorphism.
181 -- This recursion pattern subsumes histomorphisms, futumorphisms and dynamorphisms
182 -- and can be seen as the natural hylomorphism generalization from composing an histomorphism after a futumorphism.
183 -- Therefore, chronomorphisms can 'look back' when consuming a type and 'jump forward' when generating one, via it's fold/unfold operations, respectively.
185 -- The notion of chronomorphism is a recent recursion pattern (at least known as such).
186 -- The first and single reference available is <http://comonad.com/reader/2008/time-for-chronomorphisms/>.
187 chrono :: (Mu c,Functor (PF c)) => c -> (F c (Histo c b) -> b) -> (a -> F c (Futu c a)) -> a -> b
188 chrono (c::c) g h = fst . outH . hylo c (inn . (g /\ id)) ((h \/ id) . out) . innF . inl
189 where outH :: Histo c b -> F (Histo c b) (Histo c b)
191 innF :: F (Futu c a) (Futu c a) -> (Futu c a)
194 -- | The Fixpoint combinator as an hylomorphism.
196 -- 'fix' is a fixpoint combinator if @'fix' = 'app' '.' ('id' '/\' 'fix')@.
198 -- After expanding the deï¬nitions of '.', '/\' and 'app' we see that this corresponds to the expected pointwise equation @'fix' f = f ('fix' f)@.
200 fix = hylo (_L :: K (a -> a) :*!: I) app (id /\ id)
202 -- | The combinator for isomorphic type transformations.
204 -- It can translate between types that share the same functor.
205 nu d = (inn . pmap d nu . out) d