View source for Hylomorphism (computer science)

{{Short description|Recursive function}}
In [[Computer science|computer science]], and in particular [[Functional programming|functional programming]], a '''hylomorphism''' is a [[Recursion (computer science)|recursive]] function, corresponding to the [[Function composition|composition]] of an [[Anamorphism|anamorphism]] (which first builds a set of results; also known as 'unfolding') followed by a [[Catamorphism|catamorphism]] (which then [[Fold (higher-order function)|folds]] these results into a final return value). Fusion of these two recursive computations into a single recursive pattern then avoids building the intermediate data structure. This is an example of [[Deforestation (computer science)|deforestation]], a program optimization strategy. A related type of function is a '''metamorphism''', which is a catamorphism followed by an anamorphism.

==Formal definition==

A hylomorphism <math>h : A \rightarrow C</math> can be defined in terms of its separate anamorphic and catamorphic parts.

The anamorphic part can be defined in terms of a [[Arity|unary]] function <math>g : A \rightarrow B \times A</math> defining the list of elements in <math>B</math> by repeated application (''"unfolding"''), and a predicate <math>p : A \rightarrow \text{Boolean}</math> providing the terminating condition.

The catamorphic part can be defined as a combination of an initial value <math>c \in C</math> for the fold and a binary [[Operation (mathematics)|operator]] <math>\oplus : B \times C \rightarrow C</math> used to perform the fold.

Thus a hylomorphism
:<math>
h\,a = \begin{cases}
 c & \mbox{if } p\,a
 \\b \oplus h\,a' \,\,\,where \,(b, a') = g\,a & \mbox{otherwise}
 \end{cases}
 </math>
may be defined (assuming appropriate definitions of <math>p</math> & <math>g</math>).

===Notation===
An abbreviated notation for the above hylomorphism is <math>h = [\![(c, \oplus),(g, p)]\!]</math>.

==Hylomorphisms in practice==

===Lists===
Lists are common data structures as they naturally reflect linear computational processes.  These processes arise in repeated ([[Iteration|iterative]]) function calls.  Therefore, it is sometimes necessary to generate a temporary list of intermediate results before reducing this list to a single result.

One example of a commonly encountered hylomorphism is the canonical [[Factorial|factorial]] function.

<source lang="haskell">
factorial :: Integer -> Integer
factorial n
  | n == 0 = 1
  | n > 0 = n * factorial (n - 1)
</source>

In the previous example (written in [[Haskell (programming language)|Haskell]], a purely functional programming language) it can be seen that this function, applied to any given valid input, will generate a linear call tree [[Isomorphism|isomorphic]] to a list. For example, given ''n'' = 5 it will produce the following:

 factorial 5 = 5 * (factorial 4) = 120
 factorial 4 = 4 * (factorial 3) = 24
 factorial 3 = 3 * (factorial 2) = 6
 factorial 2 = 2 * (factorial 1) = 2
 factorial 1 = 1 * (factorial 0) = 1
 factorial 0 = 1

In this example, the anamorphic part of the process is the generation of the call tree which is isomorphic to the list <code>[1, 1, 2, 3, 4, 5]</code>. The catamorphism, then, is the calculation of the [[Product (mathematics)|product]] of the [[Element (mathematics)|elements]] of this list. Thus, in the notation given above, the factorial function may be written as <math>\text{factorial} = [\![(1,\times),(g, p)]\!]</math> where <math>g\ n = (n, n - 1)</math> and <math>p\ n = (n = 0)</math>.

===Trees===

However, the term 'hylomorphism' does not apply solely to functions acting upon isomorphisms of lists. For example, a hylomorphism may also be defined by generating a non-linear call tree which is then collapsed. An example of such a function is the function to generate the ''n''<sup>th</sup> [[Philosophy:Term (logic)|term]] of the [[Fibonacci sequence]].

<source lang="haskell">
 fibonacci :: Integer -> Integer
 fibonacci n
   | n == 0 = 0
   | n == 1 = 1
   | n > 1 = fibonacci (n - 2) + fibonacci (n - 1)
</source>

[[Image:Fib 4.png|thumb|300px|Call tree for <code>fibonacci 4</code>]]

This function, again applied to any valid input, will generate a call tree which is non-linear. In the example on the right, the call tree generated by applying the <code>fibonacci</code> function to the input <code>4</code>.

This time, the anamorphism is the generation of the call tree isomorphic to the tree with [[Leaf node|leaf node]]s <code>0, 1, 1, 0, 1</code> and the catamorphism the [[Summation|summation]] of these leaf nodes.

==See also==
* [[Morphism]]
* Morphisms of [[F-algebra|F-algebras]]
** From an initial algebra to an algebra: [[Catamorphism]]
** From a coalgebra to a final coalgebra: [[Anamorphism]]
** Extension of the idea of catamorphisms: Paramorphism
** Extension of the idea of anamorphisms: Apomorphism

==References==
* {{cite web
|url=http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf
|title=Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
|author1=Erik Meijer |author2=Maarten Fokkinga |author3=Ross Paterson |pages=4, 5
|year=1991
}}

==External links==
* [http://ulissesaraujo.wordpress.com/2009/04/09/hylomorphisms-in-haskell/ Hylomorphisms in Haskell]
* [http://ulissesaraujo.wordpress.com/2009/04/09/more-hylomorphisms-in-haskell/ More Hylomorphisms in Haskell]

[[Category:Category theory]]

{{Sourceattribution|Hylomorphism (computer science)}}