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') followed by a catamorphism (which then folds these results into a final return value).

A related type of function is a metamorphism, which is a catamorphism followed by an anamorphism.

can be defined in terms of its separate anamorphic and catamorphic parts.

The anamorphic part can be defined in terms of a unary function

Lists are common data structures as they naturally reflect linear computational processes.

These processes arise in repeated (iterative) function calls.

One example of a commonly encountered hylomorphism is the canonical factorial function.

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: 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].

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.

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.