|
Unfold (higher-order Function)
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, anamorphisms ... [...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] |
Erik Meijer (computer Scientist)
Erik Meijer (born 18 April 1963, Curaçao) is a Dutch computer scientist, entrepreneur, and tie-dye enthusiast. From 2000 to early 2013 he was a software architect for Microsoft where he headed the ''Cloud Programmability Team''. He then founded Applied Duality Inc. in 2013. Before that, he was an associate professor at Utrecht University. Since 2015 he has been a Director of Engineering at Facebook. He received his Ph.D. from Nijmegen University in 1992. Meijer's research has included the areas of functional programming (particularly Haskell) compiler implementation, parsing, programming language design, XML, and foreign function interfaces. His work at Microsoft included C#, Visual Basic, LINQ, Volta, and the reactive programming framework ( Reactive Extensions) for the .NET Framework. In 2009, he was the recipient of the Microsoft ''Outstanding Technical Leadership'' Award and in 2007 the Outstanding Technical Achievement Award as a member of the C# team. Meijer lived in ... [...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] |
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] |
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] |
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] |
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''. ''F''-algebras can also be used to represent data structures used in programming, such as lists and trees. The main related concepts are initial ''F''-algebras which may serve to encapsulate the induction principle, and the dual construction ''F''-coalgebras. Definition If C is a 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 of C and \alpha is a C- morphism F(A) \rightarrow A. The object A is called the ''carrier'' of the algebra. When it is permissible from context, algebras are often referred to by their carrier only instead of the tuple. A homomorphism from an F-al ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms are functions; in linear algebra, linear transformations; in group theory, group homomorphisms; in topology, continuous functions, and so on. In category theory, ''morphism'' is a broadly similar idea: the mathematical objects involved need not be sets, and the relationships between them may be something other than maps, although the morphisms between the objects of a given category have to behave similarly to maps in that they have to admit an associative operation similar to function composition. A morphism in category theory is an abstraction of a homomorphism. The study of morphisms and of the structures (called "objects") over which they are defined is central to category theory. Much of the terminology of morphisms, as well as the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" and () meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German meaning "similar" to meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925). Homomorphisms of vector spaces are also called linear maps, and their study is the subject of linear algebra. The concept of homomorphism has been generalized, under the name of morphism, to many other structures that either do not have an underlying set, or are not algebraic. This generalization is the starting point of category theory. A homomorphism may also be an isomorphism, an endomorphism, an automorphism, etc. (see below). Each of th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Category (mathematics)
In mathematics, a category (sometimes called an abstract category to distinguish it from a concrete category) is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose objects are sets and whose arrows are functions. '' Category theory'' is a branch of mathematics that seeks to generalize all of mathematics in terms of categories, independent of what their objects and arrows represent. Virtually every branch of modern mathematics can be described in terms of categories, and doing so often reveals deep insights and similarities between seemingly different areas of mathematics. As such, category theory provides an alternative foundation for mathematics to set theory and other proposed axiomatic foundations. In general, the objects and arrows may be abstract entities of any kind, and the n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
F-coalgebra
In mathematics, specifically in category theory, an F-coalgebra is a structure defined according to a functor F, with specific properties as defined below. For both algebras and coalgebras, a functor is a convenient and general way of organizing a signature. This has applications in computer science: examples of coalgebras include lazy, infinite data structures, such as streams, and also transition systems. F-coalgebras are dual to F-algebras. Just as the class of all algebras for a given signature and equational theory form a variety, so does the class of all F-coalgebras satisfying a given equational theory form a covariety, where the signature is given by F. Definition Let :F : \mathcal\longrightarrow \mathcal be an endofunctor on a category \mathcal. An F-coalgebra is an object A of \mathcal together with a morphism :\alpha : A \longrightarrow FA of \mathcal, usually written as (A, \alpha). An F-coalgebra homomorphism from (A, \alpha) to another F-coalgebra (B, \ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zip (higher-order Function)
In computer science, zipping is a function which maps a tuple of sequences into a sequence of tuples. This name zip derives from the action of a zipper in that it interleaves two formerly disjoint sequences. The inverse function is ''unzip''. Example Given the three words ''cat'', ''fish'' and ''be'' where , ''cat'', is 3, , ''fish'', is 4 and , ''be'', is 2. Let \ell denote the length of the longest word which is ''fish''; \ell = 4. The zip of ''cat'', ''fish'', ''be'' is then 4 tuples of elements: : (c,f,b)(a,i,e)(t,s,\#)(\#,h,\#) where ''#'' is a symbol not in the original alphabet. In Haskell this truncates to the shortest sequence \underline, where \underline = 2: zip3 "cat" "fish" "be" -- 'c','f','b'),('a','i','e') Definition Let Σ be an alphabet, # a symbol not in Σ. Let ''x''1''x''2... ''x'', ''x'', , ''y''1''y''2... ''y'', ''y'', , ''z''1''z''2... ''z'', ''z'', , ... be ''n'' words (i.e. finite sequences) of elements of Σ. Let \ell denote ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
