|
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 so on until some terminating condition is reached. The anamorphism is the function that generates the list of A, B, C, etc. You can think of the anamorphism as unfolding the initial value into a sequence. The above layman's description can be stated more formally in category theory: the anamorphism of a coinductive type denotes the assignment of a coalgebra to its unique morphism to the final coalgebra of an endofunctor. These objects are used in functional programming as '' unfolds''. The categorical dual (aka opposite) of the anamorphism is the catamorphism. Anamorphisms in functional programming In functional programming, an anamorphism is a generalization of the concept of '' unfolds'' on coinductive lists. Formally, anamo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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'' of lists to arbitrary algebraic data types, which can be described as initial algebras. The dual concept is that of anamorphism that generalize ''unfolds''. A hylomorphism is the composition of an anamorphism followed by a catamorphism. Definition Consider an initial F-algebra (A, in) for some endofunctor F of some category into itself. Here in is a morphism from FA to A. Since it is initial, we know that whenever (X, f) is another F-algebra, i.e. a morphism f from FX to X, there is a unique homomorphism h from (A, in) to (X, f). By the definition of the category of F-algebra, this h corresponds to a morphism from A to X, conventionally also denoted h, such that h \circ in = f \circ Fh. In the context of F-algebra, the uniquely speci ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 recursion over an inductive data type, an apomorphism models primitive corecursion over a coinductive data type. Origins The term "apomorphism" was introduced in ''Functional Programming with Apomorphisms (Corecursion)''. See also * Morphism * Morphisms of F-algebras ** From an initial algebra to an algebra: Catamorphism ** From a coalgebra to a final coalgebra: Anamorphism ** An anamorphism followed by an catamorphism: Hylomorphism Hylomorphism is a philosophical doctrine developed by the Ancient Greek philosopher Aristotle, which conceives every physical entity or being ('' ousia'') as a compound of matter (potency) and immaterial form (act), with the generic form as imm ... ** Extension of the idea of catamorphisms: Paramorphism Ref ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 keeps it too”, as exemplified by the factorial function. Its categorical dual is the apomorphism. It is a more convenient version of catamorphism in that it gives the combining step function immediate access not only to the result value recursively computed from each recursive subobject, but the original subobject itself as well. Example Haskell implementation, for lists: cata :: (a -> b -> b) -> b -> -> b para :: (a -> ( b) -> b) -> b -> -> b ana :: (b -> (a, b)) -> b -> apo :: (b -> (a, Either b)) -> b -> cata f b (a:as) = f a (cata f b as) cata _ b [] = b para f b (a:as) = f a (as, para f b as) para _ b [] = b ana u b = case u b of (a, b') -> a : ana u b' apo u b = case u b of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Initial Algebra
In mathematics, an initial algebra is an initial object in the Category (mathematics), category of F-algebra, -algebras for a given endofunctor . This initiality provides a general framework for mathematical induction, induction and recursion. Examples Functor Consider the endofunctor , i.e. sending to , where is a one-point (Singleton (mathematics), singleton) Set (mathematics), set, a terminal object in the category. An algebra for this endofunctor is a set (called the ''carrier'' of the algebra) together with a Function (mathematics), function . Defining such a function amounts to defining a point and a function . Define : \begin \operatorname \colon 1 &\longrightarrow\mathbf \\ * &\longmapsto 0 \end and : \begin \operatorname\colon \mathbf&\longrightarrow\mathbf \\ n &\longmapsto n + 1. \end Then the set of natural numbers together with the function is an initial -algebra. The initiality (the universal property for this case) is not hard to establish; ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hylomorphism (computer Science)
In computer science, and in particular functional programming, a hylomorphism is a Recursion (computer science), recursive function, corresponding to the function composition, composition of an anamorphism (which first builds a set of results; also known as 'unfolding') followed by a catamorphism (which then fold (higher-order function), folds 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 an example of deforestation (computer science), deforestation, 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 arity, unary function g : A \rightarrow B \times A defining the list of elements in B by repeated ap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Corecursion
In computer science, corecursion is a type of operation that is Dual (category theory), dual to recursion (computer science), recursion. Whereas recursion works analysis, analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is ''Generative recursion#Structural versus generative recursion, generative recursion'', which may lack a definite "direction" inherent in corecursion and recursion. Where recursion allows programs to operate on arbitrarily complex data, so long as they can be reduced to simple data (base cases), corecursion allows programs to produce arbitrarily co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Coinduction
In computer science, coinduction is a technique for defining and proving properties of systems of concurrent interacting objects. Coinduction is the mathematical dual to structural induction. Coinductively defined data types are known as codata and are typically infinite data structures, such as streams. As a definition or specification, coinduction describes how an object may be "observed", "broken down" or "destructed" into simpler objects. As a proof technique, it may be used to show that an equation is satisfied by all possible implementations of such a specification. To generate and manipulate codata, one typically uses corecursive functions, in conjunction with lazy evaluation. Informally, rather than defining a function by pattern-matching on each of the inductive constructors, one defines each of the "destructors" or "observers" over the function result. In programming, co-logic programming (co-LP for brevity) "is a natural generalization of logic programming and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Category Theory
Category theory is a general theory of mathematical structures and their relations. It was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Category theory is used in most areas of mathematics. In particular, many constructions of new mathematical objects from previous ones that appear similarly in several contexts are conveniently expressed and unified in terms of categories. Examples include quotient space (other), quotient spaces, direct products, completion, and duality (mathematics), duality. Many areas of computer science also rely on category theory, such as functional programming and Semantics (computer science), semantics. A category (mathematics), category is formed by two sorts of mathematical object, objects: the object (category theory), objects of the category, and the morphisms, which relate two objects called the ''source'' and the ''target'' of the morphism. Metapho ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zip (higher-order Function)
Zip, Zips or ZIP may refer to: Common uses * ZIP Code, USPS postal code * Zipper or zip, clothing fastener Science and technology Computing * ZIP (file format), a compressed archive file format whose typical file extension is ** zip, a command-line program from Info-ZIP * Zipping (computer science), or zip, reorganizing lists of lists * Zip drive, a removable disk storage system * Zone Information Protocol, AppleTalk protocol * Zip Chip, Apple II accelerators by Zip Technologies * .zip (top-level domain), an Internet top-level domain operated by Google Registry Other science and technology * Zip tone, in telephony * Zig-zag in-line package, electronic packaging * Zip fuel, a type of jet fuel * Zip tie, a cable fastener * Zrt- and Irt-like proteins, or Zips, zinc transporters Arts, entertainment and media * Zip (game), a children's game * Zip (roller coaster), at Oaks Amusement Park, Oregon, US * Zip, a band formed by Pete Shelley * ''Zip Comics'', 1940-1944 * ZIP FM, a radio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
F-algebra
In mathematics, specifically in category theory, ''F''-algebras generalize the notion of algebraic structure. Rewriting the algebraic laws in terms of morphisms eliminates all references to quantified elements from the axioms, and these algebraic laws may then be glued together in terms of a single functor ''F'', the ''Signature (logic), signature''. ''F''-algebras can also be used to represent data structures used in Mathematical programming, programming, such as List (computing), lists and Tree (data structure), trees. The main related concepts are Initial and terminal objects, initial ''F''-algebras which may serve to encapsulate the induction principle, and the Dual (category theory), dual construction F-coalgebra, ''F''-coalgebras. Definition If C is a Category (mathematics), category, and F : C \rightarrow C is an endofunctor of C, then an F-algebra is a tuple (A, \alpha), where A is an Object (category theory), object of C and \alpha is a C-morphism F(A) \rightarrow A. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Morphism
In mathematics, a morphism is a concept of category theory that generalizes structure-preserving maps such as homomorphism between algebraic structures, functions from a set to another set, and continuous functions between topological spaces. Although many examples of morphisms are structure-preserving maps, morphisms need not to be maps, but they can be composed in a way that is similar to function composition. Morphisms and objects are constituents of a category. Morphisms, also called ''maps'' or ''arrows'', relate two objects called the ''source'' and the ''target'' of the morphism. There is a partial operation, called ''composition'', on the morphisms of a category that is defined if the target of the first morphism equals the source of the second morphism. The composition of morphisms behaves like function composition ( associativity of composition when it is defined, and existence of an identity morphism for every object). Morphisms and categories recur in much of co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
