|
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 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, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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, anamorph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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). Fusion of these two recursive computations into a single recursive pattern then avoids building the intermediate data structure. This is an example of 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 unary function g : A \rightarrow B \times A defining the list of elements in B by repeated application (''"unfolding"''), and a predicate p : A \rightarrow \text providing the terminating condition. The catamorph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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, anamorph ... [...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] |
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 declarative programming paradigm in which function definitions are Tree (data structure), trees of Expression (computer science), expressions that map Value (computer science), values to other values, rather than a sequence of Imperative programming, imperative Statement (computer science), statements which update the State (computer science), running state of the program. In functional programming, functions are treated as first-class citizens, meaning that they can be bound to names (including local Identifier (computer languages), identifiers), passed as Parameter (computer programming), arguments, and Return value, returned from other functions, just as any other data type can. This allows programs to be written in a Declarative programming, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 declarative programming paradigm in which function definitions are Tree (data structure), trees of Expression (computer science), expressions that map Value (computer science), values to other values, rather than a sequence of Imperative programming, imperative Statement (computer science), statements which update the State (computer science), running state of the program. In functional programming, functions are treated as first-class citizens, meaning that they can be bound to names (including local Identifier (computer languages), identifiers), passed as Parameter (computer programming), arguments, and Return value, returned from other functions, just as any other data type can. This allows programs to be written in a Declarative programming, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fold (higher-order Function)
In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way. Folds are in a sense dual to unfolds, which take a ''seed'' value and apply a function corecursively to decide how to progressively construct a corecursive data structure, whereas a fold recursively breaks that structure down, replacing it with the results of applying a combining function at each node on its terminal values and the recursive results (catamorphism, versus anamorphism o ... [...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 (also hylemorphism) is a philosophical theory developed by Aristotle, which conceives every physical entity or being (''ousia'') as a compound of matter (potency) and immaterial form (act), with the generic form as immanently real ... ** Extension of the idea of catamorphisms: Paramorphism R ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Category Theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, category theory is used in almost all areas of mathematics, and in some areas of computer science. 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 spaces, direct products, completion, and duality. A category is formed by two sorts of objects: the objects of the category, and the morphisms, which relate two objects called the ''source'' and the ''target'' of the morphism. One often says that a morphism is an ''arrow'' that ''maps'' its source to its target. Morphisms can be ''composed'' if the target of the first morphism equals the source of the second one, and morphism compos ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Grant Malcolm
Grant or Grants may refer to: Places *Grant County (other) Australia * Grant, Queensland, a locality in the Barcaldine Region, Queensland, Australia United Kingdom *Castle Grant United States *Grant, Alabama *Grant, Inyo County, California *Grant, Colorado *Grant-Valkaria, Florida *Grant, Iowa *Grant, Michigan *Grant, Minnesota *Grant, Nebraska *Grant, Ohio, an unincorporated community *Grant, Washington *Grant, Wisconsin (other) (six towns) *Grant City, Indiana *Grant City, Missouri *Grant City, Staten Island *Grant Lake (other), several lakes *Grant Park, Illinois *Grant Park (Chicago) *Grant Town, West Virginia *Grant Township (other) (100 townships in 12 states) *Grant Village in Yellowstone National Park *Grants, New Mexico *Grants Pass, Oregon *U.S. Grant Bridge over Ohio River and Scioto River *General Grant National Memorial aka Grant's Tomb India *Jolly Grant Airport Dehradun, Uttarakhand Canada *Rural Municipality of Grant No. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Recursion Schemes
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 mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references ("crock recursion") can occur. Formal definitions In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties: * A simple ''base case'' (or cases) — a terminating scenario that does not use recursion to produce an answer * A ''recursive step'' — a set of rules that reduces all successive cases toward the base case. For example, the following is a recursive definition of a person's ''ancestor''. One's ances ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Category Theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, category theory is used in almost all areas of mathematics, and in some areas of computer science. 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 spaces, direct products, completion, and duality. A category is formed by two sorts of objects: the objects of the category, and the morphisms, which relate two objects called the ''source'' and the ''target'' of the morphism. One often says that a morphism is an ''arrow'' that ''maps'' its source to its target. Morphisms can be ''composed'' if the target of the first morphism equals the source of the second one, and morphism compos ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
