 Hylomorphism (computer science)

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
Formal definition
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 of elements in B by repeated application ("unfolding"), 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 (b,a') = ga) may be defined (assuming appropriate definitions of p, g, h).
Notation
An abbreviated notation for the above hylomorphism is .
Hylomorphisms in practice
Lists
Lists are common data structures, as they naturally reflect linear computational processes arising in repeated (iterative) chain of applications of a function. 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 where and .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 nonlinear 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 nonlinear. In the example on the right, the call tree generated by applying the
fibonacci
function to the input4
.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
References
 Erik Meijer, Maarten Fokkinga, Ross Paterson (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire". pp. 4, 5. http://citeseer.ist.psu.edu/cachedpage/214108/1.
External links
Categories: Articles with example Haskell code
 Category theory
 Recursion schemes
Wikimedia Foundation. 2010.
Look at other dictionaries:
Deforestation (computer science) — In the theory of programming languages in computer science, deforestation (also known as fusion) is a program transformation to eliminate tree structures. The term deforestation was originally coined by Philip Wadler in his paper Deforestation:… … Wikipedia
Hylomorphism — This article is about the concept of hylomorphism in Aristotelian philosophy. For the concept in computer science, see Hylomorphism (computer science). Part of a series on … Wikipedia
List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… … Wikipedia
Fibonacci — Infobox Scientist box width = 300px name = Leonardo of Pisa (Fibonacci) image width = 150px caption = Leonardo of Pisa, Fibonacci birth date = c. 1170 birth place = Pisa, Italy death date = c. 1250 death place = Pisa, Italy residence = Italy… … Wikipedia
Aristotle — For other uses, see Aristotle (disambiguation). Ἀριστοτέλης, Aristotélēs Marble bust of Aristotle. Roman copy after a Gree … Wikipedia
Metaphysics — This article is about the branch of philosophy dealing with theories of existence and knowledge. For the work of Aristotle, see Metaphysics (Aristotle). For the occult field, see Metaphysics (supernatural). Philosophy … Wikipedia
Metamorphism (disambiguation) — Metamorphism, in geology, is the solid state recrystallisation of rocks under environmental forces. Metamorphism may also refer to: Metamorphism (Merzbow album) (2006) Metamorphism (computer science), the categorical dual of a hylomorphism… … Wikipedia
Dualism (philosophy of mind) — René Descartes s illustration of dualism. Inputs are passed on by the sensory organs to the epiphysis in the brain and from there to the immaterial spirit. In philosophy of mind, dualism is a set of views about the relationship between mind and… … Wikipedia