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:

$\xymatrix {\mathbb{N} \ar[r]^{f} & \mathbb{R}}$ or
$\xymatrix {\mathbb{R} & \mathbb{N}\ar[l]^{f}}$ or
$\xymatrix {\mathbb{N} \ar[d]^{f} \\ \mathbb{R}}$

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.

$\xymatrix@!=4pc{A \ar[r]^{out_{List}} \ar[d]^{cata(g)_{List}} & B \ar[d]^{rec_{List}} \\C & D\ar[l]^{g}\\}$

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:

$\xymatrix@!=10pc{List~a \ar[r]^{out_{List}} \ar[d]^{(| g |)_{List}} & 1 + (a \times~ List~a) \ar[d]^{rec_{List}} \\[a] & 1 + (a \times~ [a])\ar[l]^{g}\\}$

## 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:

$\xymatrix@!=10pc{List~a \ar[r]^{out_{List}} \ar[d]^{(| g |)_{List}} & 1 + (a \times~List~a) \ar[d]^{id + id \times (| g |)_{List}} \\[a] & 1 + (a \times~[a])\ar[l]^{g}\\}$

## 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: $\xymatrix@!=6pc{NList~a \ar[r]^{out_{NList}} \ar[d]^{(| g |)_{NList}} & a + (a \times~[NList~a]) \ar[d]^{id + id \times map~(| g |)_{NList}} \\[a] & a + (a \times~[[a]])\ar[l]^{g}\\}$ ## 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. ## foldr the magic function 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] Haskell List’s! 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… ## Parsing de expressões 30 09 2007 Vamos criar uma função que pega numa String, que tem representado ma expressão matemática, e passa para um determinado tipo de dados (Exp o). A String que iremos passar á função para que seja processada será qualquer coisa do género: "((1>=a) || (4==x))" e até "(2 -( ((1+3) * (4-x)) / 45))" Comecemos então pelo inicio; {-# OPTIONS -fglasgow-exts #-} module ParserExp where import Char Escolhemos o nosso tipo de dados para representar, primeiro, os operadores: data Ops = Add | Mul | Sim | Sub | Div | OR_ | AND_ | NOT_ | GE_ | GT_ | LE_ | LT_ | EQ_ | NE_ deriving Eq Acabamos de definir 14 operadores matemáticos; Adição, Multiplicação, Simétrico, Subtracção, Divisão, ou lógico, e lógico, negação, maior que, menor que, maior ou igual a, menor ou igual a, igual e diferente. Passemos agora por definir as nossas expressões como uma árvore n-ária: data Exp o = Const Int | Var String | Op o [Exp o] Agora podemos ver que o tipo de dados escolhido encaixa perfeitamente no que pretendemos, vejamos: "((1>=a) || (4==x))" pode ser representado comoOp OR_ [Op GE_ [Const 1, Var "a"], Op EQ_ [Const 4, Var "x"]] Temos que criar uma classe para sabermos a aridade de cada operador: class Opt o where arity :: o -> Int instance Opt Ops where arity Add = 2 arity Mul = 2 arity Sim = 1 arity Sub = 2 arity Div = 2 arity OR_ = 2 arity AND_ = 2 arity NOT_ = 1 arity GE_ = 2 arity GT_ = 2 arity LE_ = 2 arity LT_ = 2 arity EQ_ = 2 arity NE_ = 2 De seguida fazemos as instancias de Show para os nossos tipos de dados, ficamos assim com: instance Show Ops where show Add = "+" show Mul = "*" show Sim = "Sim" show Sub = "-" show Div = "/" show OR_ = "||" show AND_ = "&&" show NOT_ = "!" show GE_ = ">=" show GT_ = ">" show LE_ = "<=" show LT_ = " Show (Exp o) where show (Const n) = show n show (Var s) = s show (Op o l) | arity o == 2 = "(" ++ (show$ head l) ++ show o ++ (show $last l) ++ ")" | arity o == 1 = "(" ++ show o ++ (show$ head l) ++ ")"

Bom… vamos finalmente ao que nos interessa relamente, o nosso Parser!

data ReadS a = String -> [(a,String)]

Ou seja, é fácil perceber que este tipo terá que ser a assinatura da nossa função, pois só desta forma conseguimos processar uma String, originando (sempre!) uma lista de tuplos em que a primeira parte do tuplo tem o nosso tipo desejado (árvore n-ária) e a segunda parte tem o resto da String que ainda não foi processada:

De lembrar que o nosso tipo de dados é (Exp Ops) e não apenas Exp.
Sendo assim temos:

[((leOp "~" [a]),p4) |  ("(",p1)  <- lex s,
("~",p2) <- lex p1,
(")",p4)  <- lex p3] ++
[((leOp op [a,b]),p5) | ("(",p1)  <- lex s,
(op,p3)  <- lex p2,
op == "+"  || op == "*"  || op == "/"  ||
op == "-"  || op == "||" || op == "&&" ||
op == "==" || op == "!=" || op == "=" || op == "!"  || op == ">"  ||
op == "<",
(")",p5) <- lex p4 ] ++
[((Const ((read a)::Int)),sx) | (a,sx) <- lex s, all isDigit a] ++
[((Var a),sx)                 | (a,sx)  [Exp Ops] -> Exp Ops
leOp o = Op (read o::Ops)

Acreditem que o nosso parser resume-se a estas 21 linhas (com indentação exagerada).

Aqui temos que dar os créditos ás listas por compreensão e depois á função lex que vem no Prelude. É incrível o poder desta função.
Aconselho a verem mais sobre esta função.

E finalmente temos a instancia de Read para Exp Ops:

Apartir de agora sempre que quisermos fazer parsing a uma expressão utilizamos:

parsing :: String -> Exp Ops

Ao usar a função parsing asseguramo-nos de que iremos receber sempre uma Exp Ops que é o desejado.

Este parser é bastante simples e como tal não faz reconhecimento de erros ou más formações na String recebida.

É tudo!

código aqui

## Ficheiros com comentários

29 09 2007

No inicio em que andava a programar em Haskell, a fazer o smsRecroder (uma aplicação muito lame para gravar sms’s), recordo-me de ter precisado desesperadamente de uma função