HOME

TheInfoList



Click Here for Items Related To - Hylomorphism (computer Science)
OR:
Hylomorphism (computer Science) on:   [Wikipedia]   [Google]   [Amazon]

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, and in particular
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
, a hylomorphism is a
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
function, corresponding to the
composition Composition or Compositions may refer to: Arts and literature * Composition (dance), practice and teaching of choreography *Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
of an
anamorphism In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to its previous result. You begin with some value A and apply a function f to it to get B. Then you apply f to B to get C, and ...
(which first builds a set of results; also known as 'unfolding') followed by a
catamorphism In category theory, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra. In functional programming, catamorphisms provide generaliza ...
(which then
folds Benjamin Scott Folds (born September 12, 1966) is an American singer-songwriter, musician, and composer, who is the first artistic advisor to the National Symphony Orchestra at the John F. Kennedy Center for the Performing Arts, Kennedy Center in ...
these results into a final
return value In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after the instruction which called the subroutine, known as its return address. The return address is s ...
). Fusion of these two recursive computations into a single recursive pattern then avoids building the intermediate data structure. This is an example of
deforestation Deforestation or forest clearance is the removal of a forest or stand of trees from land that is then land conversion, converted to non-forest use. Deforestation can involve conversion of forest land to farms, ranches, or urban area, urban ...
, a program optimization strategy. A related type of function is a metamorphism, which is a catamorphism followed by an anamorphism.


Formal definition

A hylomorphism h : A \rightarrow C can be defined in terms of its separate anamorphic and catamorphic parts. The anamorphic part can be defined in terms of a unary function g : A \rightarrow B \times A defining the list of elements in B by repeated application (''"unfolding"''), and a
predicate Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, ...
p : A \rightarrow \text providing the terminating condition. The catamorphic part can be defined as a combination of an initial value c \in C for the fold and a binary
operator Operator may refer to: Mathematics * A symbol indicating a mathematical operation * Logical operator or logical connective in mathematical logic * Operator (mathematics), mapping that acts on elements of a space to produce elements of another ...
\oplus : B \times C \rightarrow C used to perform the fold. Thus a hylomorphism : h\,a = \begin c & \mbox p\,a \\b \oplus h\,a' \,\,\,where \,(b, a') = g\,a & \mbox \end may be defined (assuming appropriate definitions of p & g).


Notation

An abbreviated notation for the above hylomorphism is h = ![(c, \oplus),(g, p)!">c,_\oplus),(g,_p).html" ;"title="!
![(c, \oplus),(g, p)!/math>.


Hylomorphisms in practice


Lists

List (computing)">Lists A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby union ...
are common data structures as they naturally reflect linear computational processes. These processes arise in repeated (Iteration">iterative Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
) 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 (n - 1) In the previous example (written in
Haskell Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, a
purely functional programming language In computer science, purely functional programming usually designates a programming paradigm—a style of building the structure and elements of computer programs—that treats all computation as the evaluation of mathematical functions. Program ...
) 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, 2, 3, 4, 5 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
/code>. The catamorphism, then, is the calculation of the
product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Prod ...
of the
elements Element or elements may refer to: Science * Chemical element, a pure substance of one type of atom * Heating element, a device that generates heat by electrical resistance * Orbital elements, parameters required to identify a specific orbit of ...
of this list. Thus, in the notation given above, the factorial function may be written as \text = ![(1,\times),(g, p)!">1,\times),(g,_p).html" ;"title="![(1,\times),(g, p)">![(1,\times),(g, p)!/math> where g\ n = (n, n - 1) and p\ n = (n = 0).


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 ''n''th term of the Fibonacci sequence">Term (logic)">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 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.


See also

* Morphism * Morphisms of F-algebra, F-algebras ** From an initial algebra to an algebra:
Catamorphism In category theory, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra. In functional programming, catamorphisms provide generaliza ...
** From a coalgebra to a final coalgebra:
Anamorphism In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to its previous result. You begin with some value A and apply a function f to it to get B. Then you apply f to B to get C, and ...
** Extension of the idea of catamorphisms: Paramorphism ** Extension of the idea of anamorphisms: Apomorphism


References

* {{cite web , url=http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf , title=Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire , author1=Erik Meijer , author2=Maarten Fokkinga , author3=Ross Paterson , pages=4, 5 , year=1991


External links


Hylomorphisms in Haskell

More Hylomorphisms in Haskell
Articles with example Haskell code Category theory Recursion schemes