Lately I have had many works to do at university, therefore I’m sorry for the non regularity of my post’s.

By the way, I also liked to announce that this is my first conscientious post at Planet Haskell.

## Why Catamorphisms and Point-Free

Catamorphisms is the way that we can explain in one function how recursive patterns works in some data type.

Here I will use Point-Free notation because what matters here is to show the data flow and the composition of functions.

Point-Free style is used to think in data flow terms, and very useful to program verification, applying formalism to our code.

In point-free style of programming programs are expressed as combinations of simpler functions. This notation is known as write functions without their arguments. Pointwise is the normal form how we write a function.

Couple of examples of point-free notation:

1)

sum = foldr (+) 0 -- point-free sum l = foldr (+) 0 l -- pointwise

2)

f = (*10).(+2) -- point-free f n = (n+2)*10 -- pointwise

## Clarifications

First of all to define a function, for example , I say:

or

or

I will assume that you are familiarized with infix notation, , , and composition function.

## Types

In Haskell we have this definition for lists:

data [a] = [] | a : [a]

Let’s create the same, but more convenient. Consider the following isomorphic type for lists:

data List a = Empty | Node(a,List a) deriving Show

To represent we wrote .

As you can see, to construct a we have two options, or . Formally we represent the constructor as . And we use to say that our two possibilities are or . We could see as a the following function:

Node :: (a,List a) -> List a

So typologically we have . We use to define that two things occurs in parallel, like tuples do, so we can redefine it:

Now we can say that is isomorphic to .

This is something to say that and keep the same information without any change or any loss.

## Catamorphisms as composition of functions

Let , , , be Inductive data types (sets) and , , functions.

We will write using the composition of , , functions. That way we are breaking our problem in small ones. So, in the end we will have the following definition for :

The function that we want is , and that function is over so we have:

cata :: (D -> C) -> List a -> C

Type is . Maybe this isn’t clear yet, let’s start with function

### out

The function is responsible to create the isomorphism between and , so the code could be something like this:

outList :: List a -> Either () (a,List a) outList Empty = Left () outList (Node t) = Right t

In Haskell we represent the type as , as and as .

So, type is .

### function

The function is also known as *gen*, here is where we said the step that pattern do. Imagine that we want to insert all the values of into :

-- pointwise g :: Either () (a,[a]) -> [a] g (Left()) = [] g (Right(a,h)) = a:h -- pointfree g = either (const []) (uncurry (:))

We represent as .

Now we can be more specific with our graphic:

## rec

Here we have to get a function that transform into . That function, general rec, will be:

recg f g h = f -|- (g >< g) x = ((f . fst) x , (g . snd) x)

With that function we can say exactly what to do with type , , and in domain of .

So we want something like this:

rec g = recG id id g

like that we said that will be the same in the counter domain of . Now we need a function that receive a and give us a …

Yes, that function is ! So, the final graphic became:

## cata

Finally we gonna to define the function :

cata g = outList . rec (cata g) . g

where is our *gen* function,

g = either (const []) (uncurry (:))

And our objective:

List2HaskellList = cata $ either (const []) (uncurry (:))

## More catamorphisms

Imagine we have the following data type:

data NList a where Leaf :: a -> NList a NNode :: a -> [NList a] -> NList a

, , and became:

out (Leaf a) = Left a out (NNode a l) = Right (a,l)

Using the previous definitions of and

rec f = id -|- (id >< map f)

cata g = g . rec (cata g) . out

Imagging that has type:

g :: Either a (a,[[a]]) -> [a]

And the graphic for this cata became:

## Conclusion

I’ve talked about cata’s without any formalism, the idea was to explain to someone who didn’t know.

I will talk more about catamorphisms and how to calculate programs with them.

In the future I will like to talk about anamorphisms too. And Later on I will talk about point-free over non recursive functions.

alpheccar(19:34:18) :Cool post ! I like these kind of tutorials even if I already know the topic. That kind of tutorial was very useful to me when I started learning Haskell one year ago.

I think that without blogs I would not have been able to understand Haskell.

Nooc(12:14:01) :The definition of “recg f g h” shadows the f and g in both the (-|-) and (><) definitions. This makes for a much more difficult to read tutorial.

also, spelling: “madders” should be “matters”

ulisses(22:24:23) :@alpheccar

thank you

@Nooc

this is the same as:

geko(21:25:54) :Brutal!

Drinkable Chicken » Catamorphisms in 60 seconds(04:44:03) :[…] up in some blog posts (often Haskell-related). Sounds fancy, and when I try to look it up, I run into stuff that is probably really deep, but looks like gobbledygook to me. (Likely because my […]

Ulisses Costa Blog » Blog Archive » Point-free over non recursive functions - I(17:27:44) :[…] Like I promise I will talk about point-free over non recursive functions. Point-free style is used to demonstrate propriety over programs easily than pointwise. Because we didn’t have variables in functions, we can compose a lot of small functions with each other using some combinators. Those combinators have some rules associate with them that tell us when to use some combinator.Also because I think that’s the easy way to learn point-free programming style. I will talk about that style over non recursive functions. […]

Hylomorphisms in Haskell « Ulisses Costa Blog(03:47:55) :[…] in Haskell 9 04 2009 If you miss something in this post, I suggest you to start in Catamorphisms and […]

More Hylomorphisms in Haskell « Ulisses Costa Blog(19:41:09) :[…] in Haskell 9 04 2009 If you lost yourself in this post, I advise you to start in catamorphisms, then anamorphisms and then […]

筆記與流年 » 網路書簽 » links for 2009-04-12(17:05:56) :[…] Catamorphisms in Haskell « Ulisses Costa Blog Catamorphisms is the way that we can explain in one function how recursive patterns works in some data type. (tags: haskell blog cs) […]