en>Nick Number: sp surface WP:TYPO

2014-01-22T15:51:02Z

sp surface WP:TYPO

New page

In [[category theory]], the concept of '''catamorphism''' (from [[Greek language|Greek]]: [[wikt:κατά|κατά]] = ''downwards'' or ''according to''; [[wikt:μορφή|μορφή]] = ''form'' or ''shape'') denotes the unique [[homomorphism]] from an [[initial algebra]] into some other algebra. The concept has been applied to [[functional programming]] as ''[[Fold (higher-order function)|folds]]''.

The dual concept is that of [[anamorphism]]. See also [[Hylomorphism (computer science)]]

== Catamorphisms in functional programming ==

In functional programming, a '''catamorphism''' is a generalization of the ''[[Fold (higher-order function)|folds]]'' on [[List (computing)|lists]] known from [[functional programming]] to arbitrary [[algebraic data type]]s that can be described as [[initial algebra]]s.

One of the first publications to introduce the notion of a catamorphism in the context of programming was the paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by [[Erik Meijer (computer scientist)|Erik Meijer]] ''et al.''[http://citeseer.ist.psu.edu/meijer91functional.html], which was in the context of the [[Squiggol]] formalism.

The dual concept is that of [[anamorphism]]s, a generalization of ''unfolds''.

=== Example ===
The following example is in [[Haskell (programming language)|Haskell]]:

<source lang="haskell">
data Tree a = Leaf a
| Branch (Tree a) (Tree a)

type TreeAlgebra a r = (a -> r, r -> r -> r)

foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree (f, g) (Leaf x) = f x
foldTree (f, g) (Branch l r) = g (foldTree (f, g) l) (foldTree (f, g) r)

treeDepth :: TreeAlgebra a Integer
treeDepth = (const 1, \l r -> 1 + max l r)

sumTree :: (Num a) => TreeAlgebra a a
sumTree = (id, (+))
</source>

Here <code>foldTree (''f'', ''g'')</code> is a ''catamorphism'' for the <code>Tree ''a''</code> [[abstract datatype|datatype]]; <code>treeDepth</code> and <code>sumTree</code> are called ''algebras''.

== Catamorphisms in category theory ==

Category theory provides the necessary concepts to give a generic definition that accounts for all initial data types (using an identification of functions in functional programming with the [[morphisms]] of the [[Category (mathematics)|category]] '''Set''' or some related concrete category). This was done by [[Grant Malcolm]].<ref>{{Citation |last=Malcolm |first=Grant Reynold |year=1990 |title=Algebraic Data Types and Program Transformation |url=http://cgi.csc.liv.ac.uk/~grant/PS/thesis.pdf |format=PDF |type=Ph.D. Thesis |publisher=University of Groningen}}.</ref><ref>{{Citation |last=Malcolm |first=Grant |year=1990 |title=Data structures and program transformation |periodical=Science of Computer Programming |volume=14 |issue=2-3 |pages=255–279 |doi=10.1016/0167-6423(90)90023-7}}.</ref>

Returning to the above example, consider a [[functor]] ''F'' sending <code>r</code> to <code>a + r × r</code>.
An [[F-algebra|''F''-algebra]] for this specific case is a pair (<code>r</code>, <nowiki>[</nowiki><code>f1</code>,<code>f2</code><nowiki>]</nowiki>), where <code>r</code> is an object, and <code>f1</code> and <code>f2</code> are two morphisms defined as <code>f1: a → r</code>, and <code>f2: r × r → r</code>.

In the category of ''F''-algebras over such ''F'', an initial algebra, if it exists, represents a <code>Tree</code>, or, in Haskell terms, it is <code>(Tree a, [Leaf, Branch])</code>.

<code>Tree a</code> being an initial object in the category of ''F''-algebras, there is a unique homomorphism of ''F''-algebras from <code>Tree a</code> to any given ''F''-algebra. This unique homomorphism is called ''catamorphism''.

=== The general case ===

In [[category theory]], catamorphisms are the [[categorical dual]] of [[anamorphism]]s (and anamorphisms are the categorical dual of catamorphisms).

That means the following.
Suppose (''A'', ''in'') is an [[Initial algebra|initial]] [[F-algebra|''F''-algebra]] for some [[endofunctor]] ''F'' of some [[category (mathematics)|category]] into itself.
Thus, ''in'' is a [[morphism]] from ''FA'' to ''A'', and since it is assumed to be initial we know that whenever (''X'', ''f'') is another ''F''-algebra (a morphism ''f'' from ''FX'' to ''X''), there will be a unique [[homomorphism]] ''h'' from (''A'', ''in'') to (''X'', ''f''), that is a morphism ''h'' from ''A'' to ''X'' such that ''h '''.''' in = f '''.''' Fh''.
Then for each such ''f'' we denote by '''cata''' '''''f''''' that uniquely specified morphism ''h''.

In other words, we have the following defining relationship, given some fixed ''F'', ''A'', and ''in'' as above:

*<math>h = \mathrm{cata}\ f</math>
*<math>h \circ in = f \circ Fh</math>

=== Notation ===
Another notation for cata ''f'' found in the literature is <math>(\!|f|\!)</math>. The open brackets used are known as '''banana brackets''', after which catamorphisms are sometimes referred to as ''bananas'', as mentioned in {{Harvnb|Meijer|1991}}.

== See also ==
*[[Anamorphism]]
*[[Apomorphism]]
*[[Hylomorphism (computer science)|Hylomorphism]]
*[[Paramorphism]]
*[[Morphism]]

== References ==
{{reflist|2}}

== Further reading ==
* {{cite conference |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125
|title=Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
|first1=Erik |last1=Meijer |authorlink=Erik Meijer (computer scientist)
|first2=Maarten |last2=Fokkinga
|first3=Ross |last3=Paterson
|year=1991 |conference=Conference on Functional Programming Languages and Computer Architecture (FPCA)
|publisher=Springer |pages=124-144 |isbn=3-540-54396-1
|id = {{citeseerx|10.1.1.41.125}} }}
* {{cite conference | author1 = Ki Yung Ahn | author2 = Tim Sheard | year = 2011 | url = http://dl.acm.org/citation.cfm?id=2034807 | title = A hierarchy of mendler style recursion combinators: taming inductive datatypes with negative occurrences | booktitle = Proceedings of the 16th ACM SIGPLAN international conference on Functional programming | conference = ICFP '11 }}

== External links ==
* [http://www.haskell.org/haskellwiki/Catamorphisms Catamorphisms] at HaskellWiki
* [http://comonad.com/haskell/catamorphisms.html Catamorphisms] by Edward Kmett
* Catamorphisms in [[F Sharp (programming language)|F#]] (Part [http://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/ 1], [http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/ 2], [http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/ 3], [http://lorgonblog.wordpress.com/2008/05/24/catamorphisms-part-four/ 4], [http://lorgonblog.wordpress.com/2008/05/31/catamorphisms-part-five/ 5], [http://lorgonblog.wordpress.com/2008/06/02/catamorphisms-part-six/ 6], [http://lorgonblog.wordpress.com/2008/06/07/catamorphisms-part-seven/ 7]) by Brian McNamara
* [http://ulissesaraujo.wordpress.com/2007/12/19/catamorphisms-in-haskell/ Catamorphisms in Haskell]

[[Category:Category theory]]
[[Category:Recursion schemes]]
[[Category:Functional programming]]
[[Category:Morphisms]]
[[Category:Iteration in programming]]

Optical flat - Revision history

en>Nick Number: sp surface WP:TYPO