Hylomorphism (computer science)
From Wikipedia, the free encyclopedia
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') and 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 a particular form of the optimizing program transformation techniques collectively known as deforestation. The categorical dual of a hylomorphism is called a metamorphism, and is a catamorphism followed by an anamorphism.
Contents |
[edit] Formal definition
 |
This article may be more technical than it needs to be and needs attention from an expert on its subject. Please help improve the article by making the article accessible to the widest possible audience. |
A hylomorphism 
can be defined in terms of its separate anamorphic and catamorphic parts.
The anamorphic part can be defined in terms of a unary function 
defining the list, and a predicate 
providing the terminating condition.
The catamorphic part can be defined as a combination of an initial value 
for the fold and a binary operator 
used to perform the fold.
Thus a hylomorphism
(where 
) may be defined (assuming appropriate definitions of p, g, h).
[edit] Notation
An abbreviated notation for the above hylomorphism is ![h = [\![(c, \oplus),(g, p)]\!]](http://upload.wikimedia.org/math/7/8/b/78bb0df139cf159d31584f873e712c4b.png)
.
[edit] Hylomorphisms in practice
[edit] Lists
Lists are common data structures (as they naturally arise whenever a linear process must be applied to a number of inputs); as such, it is sometimes necessary (or, at least, preferable) to generate a temporary list of intermediate results before performing an operation to reduce this list to a single final results.
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 ![\mathit{factorial} = [\![(1,\times),(g, p)]\!]](http://upload.wikimedia.org/math/3/f/6/3f61b20b4a271ba20f680007f12ea677.png)
where 
and 
.
[edit] Trees
However, it should be noted that 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 nth 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 following example, the call tree generated by applying the fibonacci function to the input 4.
fib 4 <- 1 + 2 = 3
/ \
0 + 1 = 1 -> fib 2 fib 3 <- 1 + 1 = 2
/ \ / \
fib 0 fib 1 fib 1 fib 2 <- 0 + 1 = 1
| | | /\
0 1 1 / \
fib 0 fib 1
| |
0 1
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.
[edit] See also
[edit] References
- Erik Meijer, Maarten Fokkinga, Ross Paterson (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" (HTML with PNG images). pp. 4, 5. http://citeseer.ist.psu.edu/cachedpage/214108/1.
