# Hylomorphism (computer science)

__: Recursive function__

**Short description**In computer science, and in particular functional programming, a **hylomorphism** is a recursive function, corresponding to the composition of an anamorphism (which first builds a set of results; also known as 'unfolding') followed by a catamorphism (which then 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, 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]\displaystyle{ 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 unary function [math]\displaystyle{ g : A \rightarrow B \times A }[/math] defining the list of elements in [math]\displaystyle{ B }[/math] by repeated application (*"unfolding"*), and a predicate [math]\displaystyle{ p : A \rightarrow \text{Boolean} }[/math] providing the terminating condition.

The catamorphic part can be defined as a combination of an initial value [math]\displaystyle{ c \in C }[/math] for the fold and a binary operator [math]\displaystyle{ \oplus : B \times C \rightarrow C }[/math] used to perform the fold.

Thus a hylomorphism

- [math]\displaystyle{ 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]\displaystyle{ p }[/math] & [math]\displaystyle{ g }[/math]).

### Notation

An abbreviated notation for the above hylomorphism is [math]\displaystyle{ 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 (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 function.

factorial :: Integer -> Integer factorial n | n == 0 = 1 | n > 0 = n * factorial (n - 1)

In the previous example (written in 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 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 `[1, 1, 2, 3, 4, 5]`

. The catamorphism, then, is the calculation of the product of the elements of this list. Thus, in the notation given above, the factorial function may be written as [math]\displaystyle{ \text{factorial} = [\![(1,\times),(g, p)]\!] }[/math] where [math]\displaystyle{ g\ n = (n, n - 1) }[/math] and [math]\displaystyle{ 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*^{th} term of the Fibonacci sequence.

fibonacci :: Integer -> Integer fibonacci n | n == 0 = 0 | n == 1 = 1 | n > 1 = fibonacci (n - 2) + fibonacci (n - 1)

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 `fibonacci`

function to the input `4`

.

This time, the anamorphism is the generation of the call tree isomorphic to the tree with leaf nodes `0, 1, 1, 0, 1`

and the catamorphism the summation of these leaf nodes.

## See also

- Morphism
- Morphisms of 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

- "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire". 1991. pp. 4, 5. http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf.

## External links

Original source: https://en.wikipedia.org/wiki/Hylomorphism (computer science).
Read more |