Catamorphisms in Haskell

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.

Defining grupe

Grupe é na verdade uma simples palavra que serve para definir uma quantidade abismal de situações.

Quando estudava no Porto creio que cheguei usar algumas vezes este magnifico termo, mas foi em Braga quando conheci o geko que dei o merecido valor à palavra. O geko não é um grupes, mas é das pessoas que conheço que mais mestria tem ao pronunciar esta palavra.

Para mostrar que fui aldrabado por alguém (X) posso dizer que fui “engrupado por X”. Como é fácil de ver posso ainda caracterizar a pessoa X como um “grupista” ou “um grupes” ou ainda “engrupador”.

No meio disto tudo se ainda continuar a acreditar nos grupes do X posso-me considerar um papa-grupes.

Um grupista pode ainda ser aquele gajo que fala ininterruptamente durante uma boa meia hora e que só depois de deixarmos de ter contacto visual com o mesmo é que nos apercebemos que espremendo o que este esteve a dizer nada ou pouquíssimo se aproveita. Fica-se com aquela sensação que se fossemos nós a explicar tomaríamos no máximo 2 minutos, eliminando assim os grupes.

Se quisermos desarmar um engrupador enquanto engrupa basta para isso atirar ao ar a palavra “grupe” para que este se pare imediatamente.

É fácil de ver que a palavra grupe usada com astúcia pode ser uma arma da retórica.

Quem estiver a pensar em comprar casa.