Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
Anamorphosis is a distorted projection or perspective requiring the viewer to use special devices or occupy a specific vantage point to reconstitute the image...
(which first builds a set of results; also known as 'unfolding') and a catamorphism
Catamorphism
In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...
In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...
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
Deforestation (computer science)
In the theory of programming languages in computer science, deforestation is a program transformation to eliminate tree structures....
. The categorical dual of a hylomorphism is called a metamorphism, and is a catamorphism followed by an anamorphism.
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
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
function defining the list of elements in 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
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....
used to perform the fold.
Thus a hylomorphism
(where ) may be defined (assuming appropriate definitions of , , ).
Notation
An abbreviated notation for the above hylomorphism is .
Lists
Lists are common data structures, as they naturally reflect linear computational processes arising in repeated (iterative
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
) 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
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
function.
factorial :: Integer -> Integer
factorial n
| n 0 = 1
| n > 0 = n * factorial (n - 1)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
) it can be seen that this function, applied to any given valid input, will generate a linear call tree isomorphic
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
to a list. For example, given n = 5 it will produce the following:
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
Product (mathematics)
In mathematics, a product is the result of multiplying, or an expression that identifies factors to be multiplied. The order in which real or complex numbers are multiplied has no bearing on the product; this is known as the commutative law of multiplication...
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 non-linear call tree which is then collapsed. An example of such a function is the function to generate the nthterm
Term (mathematics)
A term is a mathematical expression which may form a separable part of an equation, a series, or another expression.-Definition:In elementary mathematics, a term is either a single number or variable, or the product of several numbers or variables separated from another term by a + or - sign in an...
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
Summation
Summation is the operation of adding a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum, or running total of the summation. The numbers to be summed may be integers, rational numbers,...
can be defined in terms of its separate anamorphic and catamorphic parts.
defining the list of elements in 
by repeated application ("unfolding"), and a predicate 
providing the terminating condition.
for the fold and a binary operator
used to perform the fold.
) may be defined (assuming appropriate definitions of 
, 
, 
).
.
where 
and 
.