catamorphism

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\; \backslash circ\; in\; =\; f\; \backslash circ\; Fh$. In the context of $F$-algebra, the uniquely specified morphism from the initial object is denoted by $\backslash mathrm\{cata\}\backslash \; f$ and hence characterized by the following relationship:

• $h\; =\; \backslash mathrm\{cata\}\backslash \; f$
• $h\; \backslash circ\; in\; =\; f\; \backslash circ\; Fh$

Another notation found in the literature is $(\backslash !|f|\backslash !)$. The open brackets used are known as banana brackets, after which catamorphisms are sometimes referred to as bananas, as mentioned in Erik Meijer et al.{{Citation|last1=Meijer|first1=Erik|title=Functional programming with bananas, lenses, envelopes and barbed wire|date=1991|url=https://link.springer.com/10.1007/3540543961_7|work=Functional Programming Languages and Computer Architecture|volume=523|pages=124–144|editor-last=Hughes|editor-first=John|publisher=Springer Berlin Heidelberg|language=en|doi=10.1007/3540543961_7|isbn=978-3-540-54396-1|access-date=2020-05-07|last2=Fokkinga|first2=Maarten|last3=Paterson|first3=Ross|s2cid=11666139 |url-access=subscription}} 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., which was in the context of the Squiggol formalism.

The general categorical definition was given by Grant Malcolm.

{{Citation |last=Malcolm |first=Grant Reynold |year=1990 |title=Algebraic Data Types and Program Transformation |url=http://cgi.csc.liv.ac.uk/~grant/PS/thesis.pdf |type=Ph.D. Thesis |publisher=University of Groningen |url-status=dead |archive-url=https://web.archive.org/web/20150610231842/http://cgi.csc.liv.ac.uk/~grant/PS/thesis.pdf |archive-date=2015-06-10 }}.{{Citation |last=Malcolm |first=Grant |year=1990 |title=Data structures and program transformation |periodical=Science of Computer Programming |volume=14 |issue=2–3 |pages=255–279 |doi=10.1016/0167-6423(90)90023-7|doi-access=free }}.

We give a series of examples, and then a more global approach to catamorphisms, in the Haskell programming language.

Consider the functor Maybe defined in the below Haskell code:

data Maybe a = Nothing | Just a -- Maybe type

class Functor f where -- class for functors

fmap :: (a -> b) -> (f a -> f b) -- action of functor on morphisms

instance Functor Maybe where -- turn Maybe into a functor

fmap g Nothing = Nothing

fmap g (Just x) = Just (g x)

The initial object of the Maybe-Algebra is the set of all objects of natural number type Nat together with the morphism ini defined below:{{cite web | url=https://ncatlab.org/nlab/show/initial+algebra+of+an+endofunctor#NaturalNumbers | title=Initial algebra of an endofunctor in nLab }}{{cite web | url=https://ncatlab.org/nlab/show/natural+number#natural_numbers_objects | title=Natural number in nLab }}

data Nat = Zero | Succ Nat -- natural number type

ini :: Maybe Nat -> Nat -- initial object of Maybe-algebra (with slight abuse of notation)

ini Nothing = Zero

ini (Just n) = Succ n

The cata map can be defined as follows:

cata :: (Maybe b -> b) -> (Nat -> b)

cata g Zero = g (fmap (cata g) Nothing) -- Notice: fmap (cata g) Nothing = g Nothing and Zero = ini(Nothing)

cata g (Succ n) = g (fmap (cata g) (Just n)) -- Notice: fmap (cata g) (Just n) = Just (cata g n) and Succ n = ini(Just n)

As an example consider the following morphism:

g :: Maybe String -> String

g Nothing = "go!"

g (Just str) = "wait..." ++ str

Then cata g ((Succ. Succ . Succ) Zero) will evaluate to "wait... wait... wait... go!".

For a fixed type a consider the functor MaybeProd a defined by the following:

data MaybeProd a b = Nothing | Just (a, b) -- (a,b) is the product type of a and b

class Functor f where -- class for functors

fmap :: (a -> b) -> (f a -> f b) -- action of functor on morphisms

instance Functor (MaybeProd a) where -- turn MaybeProd a into a functor, the functoriality is only in the second type variable

fmap g Nothing = Nothing

fmap g (Just (x,y)) = Just (x, g y)

The initial algebra of MaybeProd a is given by the lists of elements with type a together with the morphism ini defined below:{{cite web | url=https://ncatlab.org/nlab/show/initial+algebra+of+an+endofunctor#more_examples | title=Initial algebra of an endofunctor in nLab }}

data List a = EmptyList | Cons a (List a)

ini :: MaybeProd a (List a) -> List a -- initial algebra of MaybeProd a

ini Nothing = EmptyList

ini (Just (n,l)) = Cons n l

The cata map can be defined by:

cata :: (MaybeProd a b -> b) -> (List a -> b)

cata g EmptyList = g (fmap (cata g) Nothing) -- Note: ini Nothing = EmptyList

cata g (Cons s l) = g (fmap (cata g) (Just (s,l))) -- Note: Cons s l = ini (Just (s,l))

Notice also that cata g (Cons s l) = g (Just (s, cata g l)).

As an example consider the following morphism:

g :: MaybeProd Int Int -> Int

g Nothing = 3

g (Just (x,y)) = x*y

cata g (Cons 10 EmptyList) evaluates to 30. This can be seen by expanding

cata g (Cons 10 EmptyList) = g (Just (10,cata g EmptyList)) = 10*(cata g EmptyList) = 10*(g Nothing) = 10*3.

In the same way it can be shown, that

cata g (Cons 10 (Cons 100 (Cons 1000 EmptyList))) will evaluate to 10*(100*(1000*3)) = 3.000.000.

The cata map is closely related to the right fold (see Fold (higher-order function)) of lists foldrList.

The morphism lift defined by

lift :: (a -> b -> b) -> b -> (MaybeProd a b -> b)

lift g b0 Nothing = b0

lift g b0 (Just (x,y)) = g x y

relates cata to the right fold foldrList of lists via:

foldrList :: (a -> b -> b) -> b-> List a -> b

foldrList fun b0 = cata (lift fun b0)

The definition of cata implies, that foldrList is the right fold and not the left fold.

As an example: foldrList (+) 1 (Cons 10 (Cons 100 (Cons 1000 EmptyList))) will evaluate to 1111 and foldrList (*) 3 (Cons 10 (Cons 100 (Cons 1000 EmptyList)) to 3.000.000.

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, (+))

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 Maybe'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"))

• Morphism
• Morphisms of F-algebras
• From a coalgebra to a final coalgebra: Anamorphism
• An anamorphism followed by an catamorphism: Hylomorphism
• Extension of the idea of catamorphisms: Paramorphism
• Extension of the idea of anamorphisms: Apomorphism

{{reflist|2}}

{{refbegin}}

• {{cite conference | author1 = Ki Yung Ahn | first2 = Tim | last2 = Sheard | year = 2011 | url = http://dl.acm.org/citation.cfm?id=2034807 | title = A hierarchy of mendler style recursion combinators: taming inductive datatypes with negative occurrences | book-title = Proceedings of the 16th ACM SIGPLAN international conference on Functional programming | conference = ICFP '11 }}

{{refend}}

• [https://www.haskell.org/haskellwiki/Catamorphisms Catamorphisms] at HaskellWiki
• [https://www.schoolofhaskell.com/user/edwardk/recursion-schemes/catamorphisms Catamorphisms] by Edward Kmett
• Catamorphisms in F# (Part [http://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/ 1], [https://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/ 2], [https://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/ 3], [https://lorgonblog.wordpress.com/2008/05/24/catamorphisms-part-four/ 4], [https://lorgonblog.wordpress.com/2008/05/31/catamorphisms-part-five/ 5], [https://lorgonblog.wordpress.com/2008/06/02/catamorphisms-part-six/ 6], [https://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]

Category:Category theory

Category:Recursion schemes

Category:Functional programming

Category:Morphisms

Category:Iteration in programming