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 by repeated application, 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 may be defined.
Notation
An abbreviated notation for the above hylomorphism is.
Hylomorphisms in practice
Lists
are common data structures as they naturally reflect linear computationalprocesses. These processes arise in repeated 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
In the previous example 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 * = 120 factorial 4 = 4 * = 24 factorial 3 = 3 * = 6 factorial 2 = 2 * = 2 factorial 1 = 1 * = 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 . 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 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 nth term of the Fibonacci sequence. fibonacci :: Integer -> Integer fibonacci n | n 0 = 0 | n 1 = 1 | n > 1 = fibonacci + fibonacci
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 nodes0, 1, 1, 0, 1 and the catamorphism the summation of these leaf nodes.
