Hylomorphism (computer Science)
   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, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, and in particular
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
, a hylomorphism is a
recursive Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
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 functional programming, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra. Catamorphisms provide generalizations of '' folds'' o ...
(which then folds 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 sav ...
). Fusion of these two recursive computations into a single recursive pattern then avoids building the intermediate
data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
. This is an example of
deforestation Deforestation or forest clearance is the removal and destruction of a forest or stand of trees from land that is then converted to non-forest use. Deforestation can involve conversion of forest land to farms, ranches, or urban use. Ab ...
, a
program optimization In computer science, program optimization, code optimization, or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources. In general, a computer program may be op ...
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, o ...
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 sp ...
\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 a set of discrete items of information collected and set forth in some format for utility, entertainment, or other purposes. A list may be memorialized in any number of ways, including existing only in the mind of the list-maker, but ...
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 pioneered several programming language ...
, 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 s ...
) it can be seen that this function, applied to any given valid input, will generate a linear call tree
isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
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/code>. The catamorphism, then, is the calculation of the
product Product may refer to: Business * Product (business), an item that can be offered to a market to satisfy the desire or need of a customer. * Product (project management), a deliverable or set of deliverables that contribute to a business solution ...
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 o ...
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 functional programming, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra. Catamorphisms provide generalizations of '' folds'' o ...
** 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 In formal methods of computer science, a paramorphism (from Greek '' παρά'', meaning "close together") is an extension of the concept of catamorphism first introduced by Lambert Meertens to deal with a form which “eats its argument and keep ...
** Extension of the idea of anamorphisms:
Apomorphism In formal methods of computer science, an apomorphism (from '' ἀπό'' — Greek for "apart") is the categorical dual of a paramorphism and an extension of the concept of anamorphism (coinduction). Whereas a paramorphism models primitive recursi ...


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