Catamorphism: Difference between revisions
Rescuing 1 sources and tagging 0 as dead. #IABot (v1.5beta) |
AaronNGray (talk | contribs) m →External links: Fixed link Catamorphisms by Edward Kmett |
||
Line 155: | Line 155: | ||
== External links == |
== External links == |
||
* [http://www.haskell.org/haskellwiki/Catamorphisms Catamorphisms] at HaskellWiki |
* [http://www.haskell.org/haskellwiki/Catamorphisms Catamorphisms] at HaskellWiki |
||
* [ |
* [https://www.schoolofhaskell.com/user/edwardk/recursion-schemes/catamorphisms Catamorphisms] by Edward Kmett |
||
* Catamorphisms in [[F Sharp (programming language)|F#]] (Part [http://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/ 1], [http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/ 2], [http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/ 3], [http://lorgonblog.wordpress.com/2008/05/24/catamorphisms-part-four/ 4], [http://lorgonblog.wordpress.com/2008/05/31/catamorphisms-part-five/ 5], [http://lorgonblog.wordpress.com/2008/06/02/catamorphisms-part-six/ 6], [http://lorgonblog.wordpress.com/2008/06/07/catamorphisms-part-seven/ 7]) by Brian McNamara |
* Catamorphisms in [[F Sharp (programming language)|F#]] (Part [http://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/ 1], [http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/ 2], [http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/ 3], [http://lorgonblog.wordpress.com/2008/05/24/catamorphisms-part-four/ 4], [http://lorgonblog.wordpress.com/2008/05/31/catamorphisms-part-five/ 5], [http://lorgonblog.wordpress.com/2008/06/02/catamorphisms-part-six/ 6], [http://lorgonblog.wordpress.com/2008/06/07/catamorphisms-part-seven/ 7]) by Brian McNamara |
||
* [http://ulissesaraujo.wordpress.com/2007/12/19/catamorphisms-in-haskell/ Catamorphisms in Haskell] |
* [http://ulissesaraujo.wordpress.com/2007/12/19/catamorphisms-in-haskell/ Catamorphisms in Haskell] |
Revision as of 13:32, 19 October 2017
In category theory, the concept of catamorphism (from the 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-algebras, this h corresponds to a morphism from A to X, conventionally also denoted h, such that . In the context of F-algebras, the uniquely specified morphism from the initial object is denoted by cata f and hence characterized by the following relationship:
Terminology and history
Another notation found in the literature is . The open brackets used are known as banana brackets, after which catamorphisms are sometimes referred to as bananas, as mentioned in Meijer 1991 . One of the first publications to introduce the notion of a catamorphism in the context of programming was the paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by Erik Meijer et al.,[1] which was in the context of the Squiggol formalism. The general categorical definition was given by Grant Malcolm. [2][3]
Examples
We give a series of examples, and then a more global approach to catamorphisms, in the Haskell programming language.
Iteration
Iteration-step prescriptions lead to natural numbers as initial object.
Consider the functor fmaybe
mapping a data type b
to a data type fmaybe b
, which contains a copy of each term from b
as well as one additional term Nothing
(in Haskell, this is what Maybe
does). This can be encoded using one term and one function. So let an instance of a StepAlgebra also include a function from fmaybe b
to b
, which maps Nothing
to a fixed term nil
of b
, and where the actions on the copied terms will be called next
.
type StepAlgebra b = (b, b->b) -- the algebras, which we encode as pairs (nil, next)
data Nat = Zero | Succ Nat -- which is the initial algebra for the functor described above
foldSteps :: StepAlgebra b -> (Nat -> b) -- the catamorphisms map from Nat to b
foldSteps (nil, next) Zero = nil
foldSteps (nil, next) (Succ nat) = next $ foldSteps (nil, next) nat
As a silly example, consider the algebra on strings encoded as ("go!", \s -> "wait.. " ++ s)
, for which Nothing
is mapped to "go!"
and otherwise "wait.. "
is prepended. As (Succ . Succ . Succ . Succ $ Zero)
denotes the number four in Nat
, the following will evaluate to "wait.. wait.. wait.. wait.. go!": foldSteps ("go!", \s -> "wait.. " ++ s) (Succ . Succ . Succ . Succ $ Zero)
. We can easily change the code to a more useful operation, say repeated operation of an algebraic operation on numbers, just by changing the F-algebra (nil, next)
, which is passed to foldSteps
List fold
For a fixed type a
, consider the functor mapping types b
to the product type of those two types. We moreover also add a term Nil
to this resulting type. An f-algebra shall now map Nil
to some special term nil
of b
or "merge" a pair (any other term of the constructed type) into a term of b
. This merging of a a pair can be encoded as a function of type a -> b -> b
.
type ContainerAlgebra a b = (b, a -> b -> b) -- f-algebra encoded as (nil, merge)
data List a = Nil | Cons a (List a) -- which turns out to be the initial algbera
foldrList :: ContainerAlgebra a b -> (List a -> b) -- catamorphisms map from (List a) to b
foldrList (nil, merge) Nil = nil
foldrList (nil, merge) (Cons x xs) = merge x $ foldrList (nil, merge) xs
As an example, consider the algebra on numbers types encoded as (3, \x-> \y-> x*y)
, for which the number from a
acts on the number from b
by plain multiplication. Then the following will evaluate to 3.000.000: foldrList (3, \x-> \y-> x*y) (Cons 10 $ Cons 100 $ Cons 1000 Nil)
Tree fold
For a fixed type a
, consider the functor mapping types b
to a type that contains a copy of each term of a
as well as all pairs of b
's (terms of the product type of two instances of the type b
). An algebra consists of a function to b
, which either acts on an a
term or two b
terms. This merging of a pair can be encoded as two functions of type a -> b
resp. b -> b -> b
.
type TreeAlgebra a b = (a -> b, b -> b -> b) -- the "two cases" function is encoded as (f, g)
data Tree a = Leaf a | Branch (Tree a) (Tree a) -- which turns out to be the initial algebra
foldTree :: TreeAlgebra a b -> (Tree a -> b) -- catamorphisms map from (Tree a) to b
foldTree (f, g) (Leaf x) = f x
foldTree (f, g) (Branch left right) = g (foldTree (f, g) left) (foldTree (f, g) right)
treeDepth :: TreeAlgebra a Integer -- an f-algebra to numbers, which works for any input type
treeDepth = (const 1, \i j -> 1 + max i j)
treeSum :: (Num a) => TreeAlgebra a a -- an f-algebra, which works for any number type
treeSum = (id, (+))
General case
Deeper category theoretical studies of initial algebras reveal that the F-algebra obtained from applying the functor to its own initial algebra is isomorphic to it.
Strong type systems enable us to abstractly specify the initial algebra of a functor f
as its fixed point a = f a. The recursively defined catamorphisms can now be coded in single line, where the case analysis (like in the different examples above) is encapsulated by the fmap. Since the domain of the latter are objects in the image of f
, the evaluation of the catamorphisms jumps back and forth between a
and f a
.
type Algebra f a = f a -> a -- the generic f-algebras
newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us the initial algebra for the functor f
cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions
Now again the first example, but now via passing the Maybe functor to Fix. Repeated application of the Maybe functor generates a chain of types, which, however, can be united by the isomorphism from the fixed point theorem. We introduce the term zero
, which arises from Maybes's Nothing
and identify a successor function with repeated application of the Just
. This way the natural numbers arise.
type Nat = Fix Maybe
zero :: Nat
zero = Iso Nothing -- every 'Maybe a' has a term Nothing, and Iso maps it into a
successor :: Nat -> Nat
successor = Iso . Just -- Just maps a to 'Maybe a' and Iso maps back to a new term
pleaseWait :: Algebra Maybe String -- again the silly f-algebra example from above
pleaseWait (Just string) = "wait.. " ++ string
pleaseWait Nothing = "go!"
Again, the following will evaluate to "wait.. wait.. wait.. wait.. go!": cata pleaseWait (successor.successor.successor.successor $ zero)
And now again the tree example. For this we must provide the tree container data type so that we can set up the fmap
(we didn't have to do it for the Maybe
functor, as it's part of the standard prelude).
data Tcon a b = TconL a | TconR b b
instance Functor (Tcon a) where
fmap f (TconL x) = TconL x
fmap f (TconR y z) = TconR (f y) (f z)
type Tree a = Fix (Tcon a) -- the initial algebra
end :: a -> Tree a
end = Iso . TconL
meet :: Tree a -> Tree a -> Tree a
meet l r = Iso $ TconR l r
treeDepth :: Algebra (Tcon a) Integer -- again, the treeDepth f-algebra example
treeDepth (TconL x) = 1
treeDepth (TconR y z) = 1 + max y z
The following will evaluate to 4: cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))
See also
References
- ^ Meijer, Erik; Fokkinga, Maarten; Paterson, Ross (1991). Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (PDF). Conference on Functional Programming Languages and Computer Architecture (FPCA). Springer. pp. 124–144. CiteSeerX 10.1.1.41.125. ISBN 3-540-54396-1.
- ^ Malcolm, Grant Reynold (1990), Algebraic Data Types and Program Transformation (PDF) (Ph.D. Thesis), University of Groningen, archived from the original (PDF) on 2015-06-10
{{citation}}
: Unknown parameter|deadurl=
ignored (|url-status=
suggested) (help). - ^ Malcolm, Grant (1990), "Data structures and program transformation", Science of Computer Programming, vol. 14, no. 2–3, pp. 255–279, doi:10.1016/0167-6423(90)90023-7.
Further reading
- Ki Yung Ahn; Sheard, Tim (2011). "A hierarchy of mendler style recursion combinators: taming inductive datatypes with negative occurrences". Proceedings of the 16th ACM SIGPLAN international conference on Functional programming. ICFP '11.
{{cite conference}}
: Unknown parameter|booktitle=
ignored (|book-title=
suggested) (help)
External links
- Catamorphisms at HaskellWiki
- Catamorphisms by Edward Kmett
- Catamorphisms in F# (Part 1, 2, 3, 4, 5, 6, 7) by Brian McNamara
- Catamorphisms in Haskell