Portability | non-portable |
---|---|
Stability | experimental |
Maintainer | hpacheco@di.uminho.pt |
Pointless Haskell: point-free programming with recursion patterns as hylomorphisms
This module defines recursion patterns as hylomorphisms.
Recursion patterns can be seen as high-order functions that encapsulate typical forms of recursion. The hylomorphism recursion pattern was first defined in http://research.microsoft.com/~emeijer/Papers/CWIReport.pdf, along with its relation with derived more specific recursion patterns such as catamorphisms, anamorphisms and paramorphisms.
The seminal paper that introduced point-free programming and defined many of the laws for catamorphisms and anamorphisms can be found in http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf.
More complex and exotic recursion patterns have been discovered later, such as accumulations, apomorphisms, zygomorphisms, histomorphisms, futumorphisms, dynamorphisms or chronomorphisms.
- hylo :: Functor (PF b) => b -> (F b c -> c) -> (a -> F b a) -> a -> c
- cata :: (Mu a, Functor (PF a)) => a -> (F a b -> b) -> a -> b
- cataRec :: (Mu a, Functor (PF a)) => a -> (F a b -> b) -> a -> b
- ana :: (Mu b, Functor (PF b)) => b -> (a -> F b a) -> a -> b
- anaRec :: (Mu b, Functor (PF b)) => b -> (a -> F b a) -> a -> b
- type Para a = a :@!: (I :*!: K a)
- para :: (Mu a, Functor (PF a)) => a -> (F a (b, a) -> b) -> a -> b
- paraRec :: (Mu a, Functor (PF a)) => a -> (F a (b, a) -> b) -> a -> b
- type Apo b = b :@!: (I :+!: K b)
- apo :: (Mu b, Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> b
- apoRec :: (Mu b, Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> b
- type Zygo a b = a :@!: (I :*!: K b)
- 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
- type Accum a b = a :*!: K b
- accum :: (Mu a, Functor (PF a)) => a -> (F (Accum a b) c -> c) -> ((F a a, b) -> F a (a, b)) -> (a, b) -> c
- type Histo a c = K c :*!: a
- histo :: (Mu a, Functor (PF a)) => a -> (F a (Histo a c) -> c) -> a -> c
- outl :: Histo a c -> c
- outr :: Histo a c -> F a (Histo a c)
- type Futu b c = K c :+!: b
- futu :: (Mu b, Functor (PF b)) => b -> (a -> F b (Futu b a)) -> a -> b
- innl :: c -> Futu b c
- innr :: F b (Futu b c) -> Futu b c
- dyna :: (Mu b, Functor (PF b)) => b -> (F b (Histo b c) -> c) -> (a -> F b a) -> a -> c
- chrono :: (Mu c, Functor (PF c)) => c -> (F c (Histo c b) -> b) -> (a -> F c (Futu c a)) -> a -> b
- fix :: (a -> a) -> a
Documentation
hylo :: Functor (PF b) => b -> (F b c -> c) -> (a -> F b a) -> a -> cSource
Definition of an hylomorphism
cata :: (Mu a, Functor (PF a)) => a -> (F a b -> b) -> a -> bSource
Definition of a catamorphism as an hylomorphism.
Catamorphisms model the fundamental pattern of iteration, where constructors for recursive datatypes are repeatedly consumed by arbitrary functions. They are usually called folds.
cataRec :: (Mu a, Functor (PF a)) => a -> (F a b -> b) -> a -> bSource
Recursive definition of a catamorphism.
ana :: (Mu b, Functor (PF b)) => b -> (a -> F b a) -> a -> bSource
Definition of an anamorphism as an hylomorphism.
Anamorphisms resembles the dual of iteration and, hence, dene the inverse of catamorphisms. Instead of consuming recursive types, they produce values of those types.
anaRec :: (Mu b, Functor (PF b)) => b -> (a -> F b a) -> a -> bSource
Recursive definition of an anamorphism.
type Para a = a :@!: (I :*!: K a)Source
The functor of the intermediate type of a paramorphism is the functor of the consumed type a
extended with an extra annotation to itself in recursive definitions.
para :: (Mu a, Functor (PF a)) => a -> (F a (b, a) -> b) -> a -> bSource
Definition of a paramorphism.
Paramorphisms supply the gene of a catamorphism with a recursively computed copy of the input.
The first introduction to paramorphisms is reported in http://www.cs.uu.nl/research/techreps/repo/CS-1990/1990-04.pdf.
paraRec :: (Mu a, Functor (PF a)) => a -> (F a (b, a) -> b) -> a -> bSource
Recursive definition of a paramorphism.
type Apo b = b :@!: (I :+!: K b)Source
The functor of the intermediate type of an apomorphism is the functor of the generated type b
with an alternative annotation to itself in recursive definitions.
apo :: (Mu b, Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> bSource
Definition of an apomorphism as an hylomorphism.
Apomorphisms are the dual recursion patterns of paramorphisms, and therefore they can express functions defined by primitive corecursion.
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.
apoRec :: (Mu b, Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> bSource
Recursive definition of an apomorphism.
type Zygo a b = a :@!: (I :*!: K b)Source
In zygomorphisms we extend the recursive occurences in the base functor functor of type a
with an extra annotation b
.
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 -> bSource
Definition of a zygomorphism as an hylomorphism.
Zygomorphisms were introduced in http://dissertations.ub.rug.nl/faculties/science/1990/g.r.malcolm/.
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).
type Accum a b = a :*!: K bSource
In accumulations we add an extra annotation b
to the base functor of type a
.
accum :: (Mu a, Functor (PF a)) => a -> (F (Accum a b) c -> c) -> ((F a a, b) -> F a (a, b)) -> (a, b) -> cSource
Definition of an accumulation as an hylomorphism.
Accumulations http://www.fing.edu.uy/~pardo/papers/wcgp02.ps.gz are binary functions that use the second parameter to store intermediate results.
The so called accumulation technique is tipically used in functional programming to derive efficient implementations of some recursive functions.
type Histo a c = K c :*!: aSource
In histomorphisms we add an extra annotation c
to the base functor of type a
.
histo :: (Mu a, Functor (PF a)) => a -> (F a (Histo a c) -> c) -> a -> cSource
Definition of an histomorphism as an hylomorphism (as long as the catamorphism is defined as an hylomorphism).
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. In other words, they allow to reuse sub-sub constructor results.
The combinator outl
unpacks the functor of an histomorphism and selects the annotation.
outr :: Histo a c -> F a (Histo a c)Source
The combinator outr
unpacks the functor of an histomorphism and discards the annotation.
type Futu b c = K c :+!: bSource
In futumorphisms we add an alternative annotation c
to the base functor of type b
.
futu :: (Mu b, Functor (PF b)) => b -> (a -> F b (Futu b a)) -> a -> bSource
Definition of a futumorphism as an hylomorphism (as long as the anamorphism is defined as an hylomorphism).
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).
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.
The combinator innl
packs the functor of a futumorphism from the base functor.
innr :: F b (Futu b c) -> Futu b cSource
The combinator innr
packs the functor of an futumorphism from an annotation.
dyna :: (Mu b, Functor (PF b)) => b -> (F b (Histo b c) -> c) -> (a -> F b a) -> a -> cSource
Definition of a dynamorphism as an hylomorphisms.
Dynamorphisms (http://math.ut.ee/~eugene/kabanov-vene-mpc-06.pdf) are a more general form of histomorphisms for capturing dynaming programming constructions.
Instead of following the recursion pattern of the input via structural recursion (as in histomorphisms), dynamorphisms allow us to reuse the annotated structure in a bottom-up approach and avoiding rebuilding it every time an annotation is needed, what provides a more efficient dynamic algorithm.
chrono :: (Mu c, Functor (PF c)) => c -> (F c (Histo c b) -> b) -> (a -> F c (Futu c a)) -> a -> bSource
Definition of a chronomorphism as an hylomorphism.
This recursion pattern subsumes histomorphisms, futumorphisms and dynamorphisms and can be seen as the natural hylomorphism generalization from composing an histomorphism after a futumorphism. Therefore, chronomorphisms can 'look back' when consuming a type and 'jump forward' when generating one, via it's fold/unfold operations, respectively.
The notion of chronomorphism is a recent recursion pattern (at least known as such). The first and single reference available is http://comonad.com/reader/2008/time-for-chronomorphisms/.