Catamorphisms - Revision history
https://wiki.haskell.org/index.php?title=Catamorphisms&action=history
Revision history for this page on the wikienMediaWiki 1.19.14+dfsg-1Mon, 02 May 2016 04:09:57 GMTPiet Delport: /* References */ fix broken link to Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=58631&oldid=prev
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=58631&oldid=prev<p><span dir="auto"><span class="autocomment">References: </span> fix broken link to Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire</span></p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 22:28, 3 August 2014</td>
</tr></table>Sun, 03 Aug 2014 22:28:17 GMTPiet Delporthttps://wiki.haskell.org/Talk:CatamorphismsEvalquote: /* Alternate Definitions */
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=41370&oldid=prev
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=41370&oldid=prev<p><span dir="auto"><span class="autocomment">Alternate Definitions</span></span></p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 00:44, 31 July 2011</td>
</tr></table>Sun, 31 Jul 2011 00:44:29 GMTEvalquotehttps://wiki.haskell.org/Talk:CatamorphismsEvalquote: /* Haskell Implementation */
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=41369&oldid=prev
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=41369&oldid=prev<p><span dir="auto"><span class="autocomment">Haskell Implementation</span></span></p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 00:44, 31 July 2011</td>
</tr></table>Sun, 31 Jul 2011 00:44:12 GMTEvalquotehttps://wiki.haskell.org/Talk:CatamorphismsHenk-Jan van Tuyl: Improved lay-out
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=35030&oldid=prev
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=35030&oldid=prev<p>Improved lay-out</p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 18:02, 21 June 2010</td>
</tr></table>Mon, 21 Jun 2010 18:02:45 GMTHenk-Jan van Tuylhttps://wiki.haskell.org/Talk:CatamorphismsHenk-Jan van Tuyl: Coverted laws to table
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=34990&oldid=prev
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=34990&oldid=prev<p>Coverted laws to table</p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 20:06, 16 June 2010</td>
</tr></table>Wed, 16 Jun 2010 20:06:18 GMTHenk-Jan van Tuylhttps://wiki.haskell.org/Talk:CatamorphismsHenk-Jan van Tuyl at 19:48, 16 June 2010
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=34989&oldid=prev
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=34989&oldid=prev<p></p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 19:48, 16 June 2010</td>
</tr></table>Wed, 16 Jun 2010 19:48:39 GMTHenk-Jan van Tuylhttps://wiki.haskell.org/Talk:CatamorphismsHenk-Jan van Tuyl: Copied with permission from http://knol.google.com/k/catamorphisms
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=34988&oldid=prev
https://wiki.haskell.org/index.php?title=Catamorphisms&diff=34988&oldid=prev<p>Copied with permission from http://knol.google.com/k/catamorphisms</p>
<p><b>New page</b></p><div>== Folding data structures ==<br />
An overview and derivation of the category-theoretic notion of a catamorphism as a recursion scheme, and an exploration of common variations on the theme.<br />
<br />
<br />
== Description ==<br />
Catamorphisms are generalizations of the concept of a fold in functional programming. A catamorphism deconstructs a data structure with an F-algebra for its underlying functor.<br />
<br />
== History ==<br />
The name catamorphism appears to have been chosen by Lambert Meertens [1]. The category theoretic machinery behind these was resolved by Grant Malcolm [2][3], and they were popularized by Meijer, Fokkinga and Paterson[4][5]. The name comes from the Greek 'κατα-' meaning "downward or according to". A useful mnemonic is to think of a catastrophe destroying something.<br />
<br />
== Notation ==<br />
A catamorphism for some F-algebra (X,f) is denoted (| f |)F. When the functor F can be determined unambiguously, it is usually written (|φ|) or cata φ. Due to this choice of notation, a catamorphism is sometimes called a banana and the (|.|) notation is sometimes referred to as banana brackets.<br />
<br />
== Haskell Implementation ==<br />
type Algebra f a = f a -> a <br />
newtype Mu f = InF { outF :: f (Mu f) } <br />
cata :: Functor f => Algebra f a -> Mu f -> a <br />
cata f = f . fmap (cata f) . outF <br />
Alternate Definitions <br />
cata f = hylo f outF <br />
cata f = para (f . fmap fst) <br />
Duality<br />
A catamorphism is the categorical dual of an anamorphism.<br />
<br />
== Derivation ==<br />
If (μF,inF) is the initial F-algebra for some endofunctor F and (X,φ) is an F-algebra, then there is a unique F-algebra homomorphism from (μF,inF) to (X,φ), which we denote (| φ |)F. <br />
<br />
That is to say, the following diagram commutes:<br />
[[Image:cata-diagram.png|center]]<br />
<br />
== Laws == <br />
Rule Haskell<br />
cata-cancel cata phi . InF = phi . fmap (cata phi)<br />
cata-refl cata InF = id<br />
cata-fusion f . phi = phi . fmap f => <br />
f . cata phi = cata phi <br />
cata-compose eps :: f :~> g =><br />
cata phi . cata (In . eps) =<br />
cata (phi . eps)<br />
<br />
<br />
== Examples ==<br />
<br />
The underlying functor for a string of Chars and its fixed point<br />
data StrF x = Cons Char x | Nil <br />
type Str = Mu StrF<br />
instance Functor StrF where <br />
fmap f (Cons a as) = Cons a (f as) <br />
fmap f Nil = Nil <br />
The length of a string as a catamorphism.<br />
length :: Str -> Int <br />
length = cata phi where <br />
phi (Cons a b) = 1 + b <br />
phi Nil = 0 <br />
The underlying functor for the natural numbers. <br />
data NatF a = S a | Z deriving (Eq,Show) <br />
type Nat = Mu NatF <br />
instance Functor NatF where <br />
fmap f Z = Z <br />
fmap f (S z) = S (f z) <br />
Addition as a catamorphism. <br />
plus :: Nat -> Nat -> Nat <br />
plus n = cata phi where <br />
phi Z = n <br />
phi (S m) = s m <br />
Multiplication as a catamorphism <br />
times :: Nat -> Nat -> Nat <br />
times n = cata phi where <br />
phi Z = z <br />
phi (S m) = plus n m <br />
z :: Nat <br />
z = InF Z <br />
s :: Nat -> Nat <br />
s = InF . S <br />
<br />
<br />
== Mendler Style ==<br />
A somewhat less common variation on the theme of a catamorphism is a catamorphism as a recursion scheme a la Mendler, which removes the dependency on the underlying type being an instance of Haskell's Functor typeclass [6].<br />
<br />
type MendlerAlgebra f c = forall a. (a -> c) -> f a -> c [8]<br />
mcata :: MendlerAlgebra f c -> Mu f -> c <br />
mcata phi = phi (mcata phi) . outF <br />
<br />
From which we can derive the original notion of a catamorphism:<br />
<br />
cata :: Functor f => Algebra f c -> Mu f -> c <br />
cata phi = mcata (\f -> phi . fmap f) <br />
This can be seen to be equivalent to the original definition of cata by expanding the definition of mcata.<br />
<br />
The principal advantage of using Mendler-style is it is independent of the definition of the Functor definition for f.<br />
<br />
== Mendler and the Contravariant Yoneda Lemma ==<br />
The definition of a Mendler-style algebra above can be seen as the application of the contravariant version of the Yoneda lemma to the functor in question. <br />
<br />
In type theoretic terms, the contravariant Yoneda lemma states that there is an isomorphism between (f a) and ∃b. (b -> a, f b), which can be witnessed by the following definitions.<br />
<br />
data CoYoneda f a = forall b. CoYoneda (b -> a) (f b) <br />
toCoYoneda :: f a -> CoYoneda f a <br />
toCoYoneda = CoYoneda id <br />
fromCoYoneda :: Functor f => CoYoneda f a -> f a <br />
fromCoYoneda (CoYoneda f v) = fmap f v <br />
Note that in Haskell using an existential requires the use of data, so there is an extra bottom that can inhabit this type that prevents this from being a true isomorphism.<br />
<br />
However, when used in the context of a (CoYoneda f)-Algebra, we can rewrite this to use universal quantification because the functor f only occurs in negative position, eliminating the spurious bottom.<br />
Algebra (CoYoneda f) a <br />
= (by definition) CoYoneda f a -> a <br />
~ (by definition) (exists b. (b -> a, f b)) -> a <br />
~ (lifting the existential) forall b. (b -> a, f b) -> a <br />
~ (by currying) forall b. (b -> a) -> f b -> a <br />
= (by definition) MendlerAlgebra f a<br />
Generalized Catamorphisms<br />
Most more advanced recursion schemes for folding structures, such as paramorphisms and zygomorphisms can be seen in a common framework as "generalized" catamorphisms[7]. A generalized catamorphism is defined in terms of an F-W-algebra and a distributive law for the comonad W over the functor F which preserves the structure of the comonad W.<br />
<br />
type Dist f w = forall a. f (w a) -> w (f a) <br />
type FWAlgebra f w a = f (w a) -> a <br />
g_cata :: (Functor f, Comonad w) => <br />
Dist f w -> FWAlgebra f w a -> Mu f -> a <br />
g_cata k g = extract . c where <br />
c = liftW g . k . fmap (duplicate . c) . outF <br />
However, a generalized catamorphism can be shown to add no more expressive power to the concept of a catamorphism. That said the separation of a number of the "book keeping" concerns by isolating them in a reusable distributive law can ease the development of F-W-algebras.<br />
<br />
We can transform an F-W-algebra into an F-algebra by including the comonad in the carrier for the algebra and then extracting after we perform this somewhat more stylized catamorphism:<br />
<br />
lowerAlgebra :: (Functor f, Comonad w) => <br />
Dist f w -> FWAlgebra f w a -> Algebra f (w a) <br />
lowerAlgebra k phi = liftW phi . k . fmap duplicate <br />
g_cata :: (Functor f, Comonad w) => <br />
Dist f w -> FWAlgebra f w a -> Mu f -> a <br />
g_cata k phi = extract . cata (lowerGAlgebra k phi) <br />
<br />
and we can trivially transform an Algebra into an F-W-Algebra by mapping the counit of the comonad over F. Then using the trivial identity functor, we can represent every catamorphism as a generalized-catamorphism. <br />
liftAlgebra :: (Functor f, Comonad w) => <br />
Algebra f a -> FWAlgebra f w a<br />
<br />
liftAlgebra phi = phi . fmap extract<br />
<br />
<br />
cata :: Functor f => Algebra f a -> Mu f -> a<br />
cata f = g_cata (Identity . fmap runIdentity) (liftAlgebra f)<br />
Between these two definitions we can see that a generalized catamorphism does not increase the scope of a catamorphism to encompass any more operations, it simply further stylizes the pattern of recursion.<br />
<br />
== References ==<br />
# L. Meertens. First Steps towards the theory of Rose Trees. Draft Report, CWI, Amsterdam, 1987.<br />
# G. Malcolm. PhD. Thesis. University of Gronigen, 1990.<br />
# G. Malcolm. Data structures and program transformation. Science of Computer Programming, 14:255--279, 1990.<br />
# E. Meijer. [http://research.microsoft.com/~emeijer/Papers/Thesis.pdf Calculating Compilers], Ph.D Thesis, Utrecht State University, 1992.<br />
# E. Meijer, M. Fokkinga, R. Paterson, [http://research.microsoft.com/~emeijer/Papers/fpca91.pdf Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire], 5th ACM Conference on Functional Programming Languages and Computer Architecture.<br />
# T. Uustalu, V. Vene. [http://citeseer.ist.psu.edu/314266.html Coding Recursion a la Mendler. Proceedings 2nd Workshop on Generic Programming], WGP'2000, Ponte de Lima, Portugal, 6 July 2000<br />
# T. Uustalu, V. Vene, A. Pardo. [http://citeseer.ist.psu.edu/uustalu01recursion.html Recursion schemes from Comonads. Nordic Journal of Computing.] Volume 8 , Issue 3 (Fall 2001). 366--390, 2001 ISSN:1236-6064<br />
# E. Kmett. [http://comonad.com/reader/2008/catamorphism/ Catamorphism. The Comonad.Reader, 2008.]</div>Wed, 16 Jun 2010 19:45:26 GMTHenk-Jan van Tuylhttps://wiki.haskell.org/Talk:Catamorphisms