19 12 2007

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 $f$, I say:

 or
 or


I will assume that you are familiarized with infix notation, $const$, $either$, $uncurry$ and composition $\circ$ 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 $[1,2,3]$ we wrote $Node(1,Node(2,Node(3,Empty)))$.

As you can see, to construct a $(List a)$ we have two options, $Empty$ or $Node$. Formally we represent the constructor $Empty$ as $1$. And we use $(+)$ to say that our two possibilities are $1$ or $Node$. We could see $Node$ as a the following function:

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

So typologically we have $1 + (a,List~a)$. We use $(\times)$ to define that two things occurs in parallel, like tuples do, so we can redefine it: $1 + (a \times~List~a)$

Now we can say that $(List~a)$ is isomorphic to $(1 + a \times~List~a)$.
This is something to say that $(List~a)$ and $(1 + a \times~List~a)$ keep the same information without any change or any loss.

## Catamorphisms as composition of functions

Let $A$, $B$, $C$, $D$ be Inductive data types (sets) and $out$, $cata$, $rec$ functions.



We will write $cata(g)_{List}$ using the composition of $out$, $cata$, $rec$ functions. That way we are breaking our problem in small ones. So, in the end we will have the following definition for $cata(g)_{List}$:

$cata(g)_{List} = g \circ rec_{List} \circ out_{List}$

The function that we want is $cata(g)$, and that function is over $(List~a)$ so we have:

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

Type $A$ is $(List~a)$. Maybe this isn’t clear yet, let’s start with function $out$

### out

The function $outList$ is responsible to create the isomorphism between $(1 + a \times~List~a)$ and $(List~a)$, 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 $1$ as $()$, $(+)$ as $Either$ and $(\times)$ as $(,)$.

So, type $B$ is $(1 + a \times~List~a)$.

### function $g$

The function $g$ 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 $(List~a)$ into $[a]$:

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

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

We represent $cata(g)$ as $(| g |)$.
Now we can be more specific with our graphic:



## rec

Here we have to get a function $rec$ that transform $1 + (a \times~List~a)$ into $1 + (a \times~[a])$. 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 $1$, $a$, and $List~a$ in domain of $rec$.
So we want something like this:

rec g = recG id id g

like that we said that $(1 + (a \times~\_))$ will be the same in the counter domain $(1 + (a \times~\_))$ of $rec$. Now we need a function that receive a $List~a$ and give us a $[a]$
Yes, that function is $(| g |)$! So, the final graphic became:



## cata

Finally we gonna to define the function $cata(g)$:

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

where $g$ 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

$out$, $rec$, and $cata$ 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 $g$ 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.

20 11 2007

## Recursion

In Haskell we essentially use recursion, this mean defining a function using itself definition.
A recursive function is, for example the factorial:

in haskell we define it like that:

fact 0 = 1
fact n = n * fact (n-1)

As you can see Haskell is authentic mathematic, pure functional language.

My point here is to show you the magic of the function $foldr$ in Haskell, so I will assume that you already know Haskell, and maybe are accustomed to use $foldr$ function.

ok…

## Seeing the magic

The definition of the function $length$ could be something like this:

length [] = 0
length (h:t) = 1 + length t

The definition of the function $sum$ could be something like this:

sum [] = 0
sum (h:t) = h + sum t

And the definition of the function $mult$ could be something like this:

mult [] = 1
mult (h:t) = h * mult t

As you can see in all three definitions we have a pattern and we can generalize it:

functionName [] = stopCase
functionName (h:t) = constant operator (functionName t)

We always need the stopping case of the function!

And the same happens in other functions like $reverse$:

reverse [] = []
reverse (h:t) = reverse t ++ [h]

In this case we have:

functionName [] = stopCase
functionName (h:t) = (functionName t) operator constant

So, we will always use the function applied to the tail of the list!

If we use some of lambda notation we can see one more pattern, the real one:

sum [] = 0
sum (h:t) = (a b -> a + b) h (sum t)

reverse [] = []
reverse (h:t) = (a b -> b ++ [a]) h (reverse t)

Our lambdas functions have arity 2, because those are the parts in which we can see the lists (head + tail).

Now we can generalize even more, considering $function$ have arity 2:

functionName [] = stopCase
functionName (h:t) = function h (functionName t)

well, that’s not right for Haskell. Because it doesn’t know what $function$ represents, that’s because the definition of $functionName$ doesn’t receive that argument. And the same happens with $stopCase$.

functionName function stopCase [] = stopCase
functionName function stopCase (h:t)
= function h (functionName function stopCase t)

Et voilá.

In fact the last definition is the true one for $foldr$. Easy right?

## Functions with foldr’s

Well… Now we can redefine previous functions just with foldr’s:

length l = foldr (a b -> 1 + b) 0 l
sum l = foldr (+) 0 l
mult l = foldr (*) 1 l
reverse l = foldr (a b -> b ++ [a]) [] l

And all the functions over list’s…

and l = foldr (&&) True l
or l = foldr (||) False l

## More magic

Foldr is more magical than this, it is one catamorphism! A Catamorphism over this data type:

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

That means that $foldr$ functions “knows” the recursive pattern over List’s.

Foldr also allows you to use Pointfree notation, witch I like. Formal explanation.

length = foldr (a b -> 1 + b) 0

## More foldr’s

We can also write foldr’s functions to every data type that we create, and “explain” how recursive patterns works for our new data type:

data BTree a where
Empty :: BTree a
Node :: a -> BTree a -> BTree a -> BTree a

foldrBTree :: (a -> b -> b -> b) -> b -> BTree a -> b
foldrBTree op k Empty = k
foldrBTree op k (Node a l r) = op a (foldrBTree op k l) (foldrBTree op k r)

Now if we have a Binary Tree and want to know how many nodes it has, we just have to do this:

countNodes = foldrBTree (\a nodesLeft nodesRight ->a+nodesLeft+nodesRight) 0

If we want to know how many Empty’s our tree has:

countEmpty = foldrBTree (\_ nodesLeft nodesRight -> nodesLeft + nodesRight) 1

and so on…

Fold’s are really a genuine help for your code.
Later on I will talk more about catamorphisms…

27 10 2007

Haskell is so far one of my favorite programming languages, I don’t know if you noticed (lolz). Because it is ease of proof, no side effects, strongly typed, polymorphic, powerful, elegant and so much more.

Yesterday I was searching if there were any report talking about Haskell authors, other than Simon Peyton Jones or Paul Hudak. What I found out much more than I expected. I’ve found the History of Haskell paper. The paper that was published at 3rd History of Programming Language Conference in June 2007.

I start reading immediately, it was fascinating… The paper is a bit long (55 pages in two columns style), but deserves attention. The history is told for those who made History, Simon Peyton Jones, Paul Hudak, John Hughes and Philip Wadler, the main authors.

Haskell principles, ideology, implementations, tools – Haskell world, are in this paper. This document is excellent for those who want to learn Haskell or just know it history.

References: