8 04 2009

First I would like to introduce the notation that I use here. The pointfree notation is good to see a program (functions) data flow and as composition of functions, combination of functions, if you prefer. This style is characterized by not using variables in declaration of functions. Haskell allow us to implement that notation natively. The dual of the pointfree notation is the pointwise one.

A simple example of a function in pointwise style:

f n = (n+2)*10 -- pointwise


The dual in pointfree would be:

f = (*10) . (+2) -- pointfree


## Clarifications

First of all to define a function, for example $f$, i can say:

$\xymatrix {\mathbb{N} \ar[r]^{f} & \mathbb{R}}$, $\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, $either$, and composition $(\circ)$ functions.

## Types

For this post I need to explain the data type we will going to use. In Haskell we define it by:

data Tree a = Node a [Tree a]


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

data Tree a = Node (a, [Tree a])

We could see $Node$ as a the following function:

Node :: (a, [Tree a]) -> Tree a


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

Now we can say that $(Tree~a)$ is isomorphic to $(a \times~[Tree~a])$.
This is something to say that $(Tree~a)$ and $(a \times~[Tree~a])$ keep the same information without any change. We represent that formally as: $(Tree~a) \cong~(a \times~[Tree~a])$.

## Anamorphisms

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

$\xymatrix@!=10pc{A \ar[r]^{h} \ar[d]^{ana(h)_{Tree}} & B \ar[d]^{rec_{Tree}} \\C & D\ar[l]^{in_{Tree}}\\}$

$ana(h_{Tree})$ is the anamorphism of $h$ if the diagram commute.

We use the notation $rec_{Tree}$ to say that function $rec$ in not generic, but only works for data $Tree$. The same happens with $in$ and $ana$. We will write $ana(h)_{Tree}$ using the composition of $in$, $ana$ and $rec$ functions. That way we are breaking our problem in small ones. So, in the end we will have the following definition for $ana(h)_{Tree}$:

$ana(h)_{Tree} = in_{Tree} \circ rec_{Tree} \circ h$

The function that we want is $ana(h)$, and that function is over $(Tree~a)$ so we have:

ana :: (A -> B) -> A -> Tree c

Type $C$ is $(Tree~c)$. Maybe this isn’t clear yet, let’s start with function $in$

### function in

The function $in_{Tree}$ is responsible to create the isomorphism between $(Tree~a)$ and $(a \times~[Tree~a])$, so the code could be something like this:

inTree :: Tree a -> (a, [Tree a])
inTree    = Node


In Haskell we represent the type $(\times)$ as $(,)$. So, type $D$ is $(a \times~[Tree~a])$. So by now, we already know the following unifications $C \sim Tree~c$ and $D \sim c \times~[Tree~c]$. So now our graphic is:
$\xymatrix@!=10pc{A \ar[r]^{h} \ar[d]^{ana(h)_{Tree}} & B \ar[d]^{rec_{Tree}} \\Tree~c & c \times~[Tree~c]\ar[l]^{in_{Tree}}\\}$

### function $h$

The function $h$ is also known as *gen*, here is where we said the step that pattern do. This is the only function we need to take care, if this function is good, our problem is solved. Now image that our problem is:

Suppose that the pair of positive integers (v, p) denotes the number of red balls (v) and black (p) that is inside a bag, the balls which are taking randomly, successively, until the bag is empty.

This is the point-wise version of the function we want to convert to pointfree using anamorphisms. This function represent as a tree, all possible states of the bag over these experiences.

state :: (Int,Int) -> Tree (Int,Int)
state(0,0) = Node (0,0) []
state(v,0) = Node (v,0) [state(v-1,0)]
state(0,p) = Node (0,p) [state(0,p-1)]
state(v,p) = Node (v,p) [state(v-1,p),state(v,p-1)]


If we want that “latex state\$ became an anamorphism, we have to say that our type $A$ unify ($\sim$) with $Int \times~Int$, and $Tree~c$ became more restrict, and unify with $Tree (Int \times~Int)$. A consequence of changing the co-domain of $in_{Tree}$ is changing the domain of it to $(Int \times~Int) \times~[Tree (Int \times~Int)]$. We represent $ana(h)$ as $[( h )]$. Now we can be more specific with our graphic:

$\xymatrix@!=14pc{Int \times~Int \ar[r]^{h} \ar[d]^{[(h)]_{Tree}} & B \ar[d]^{rec_{Tree}} \\Tree~(Int \times~Int) & (Int \times~Int) \times~[Tree~(Int \times~Int)]\ar[l]^{in_{Tree}}\\}$

### function rec

Here we have to get a function $rec$ that co-domain is $(Int \times~Int) \times~[Tree~(Int \times~Int)]$. Probably the best is to pass the first part of the tuple (part with type $(Int \times~Int)$) and the rest (part with type $[Tree~(Int \times~Int)]$) is just a $map$ of the function $[(h)]_{Tree}$. So, now our graphic is:

$\xymatrix@!=14pc{Int \times~Int \ar[r]^{h} \ar[d]^{[(h)]_{Tree}} & (Int \times~Int) \times~[(Int \times~Int)] \ar[d]^{rec_{Tree}} \\Tree~(Int \times~Int) & (Int \times~Int) \times~[Tree~(Int \times~Int)]\ar[l]^{in_{Tree}}\\}$

As you can see, the second part of the co-domain of $h$ is the type of function $map~[(h)]_{Tree}$:

$map~[(h)]_{Tree}~:~[(Int \times~Int)] \rightarrow~[Tree(Int \times~Int)]$

So our final graphic became:

$\xymatrix@!=14pc{Int \times~Int \ar[r]^{h} \ar[d]^{[(h)]_{Tree}} & (Int \times~Int) \times~[(Int \times~Int)] \ar[d]^{id \times~map~[(h)]_{Tree}} \\Tree~(Int \times~Int) & (Int \times~Int) \times~[Tree~(Int \times~Int)]\ar[l]^{in_{Tree}}\\}$

Now, we just have to define the function $h$ and apply them to our anamorphism of $Tree$.

h :: (Int, Int) -> ( (Int, Int), [ (Int, Int) ] )
h(0,0) = ( (0,0), [] )
h(v,0) = ( (v,0), [ (v-1,0) ] )
h(0,p) = ( (0,p) [ (0,p-1) ] )
h(v,p) = ( (v,p), [ (v-1,p), (v,p-1) ] )


And this is it! Now we can say that:
$state \equiv~ana_{Tree}$ where $ana(h)_{Tree} = in_{Tree} \circ~id~><~map~ana(h)_{Tree} \circ h$

## Outroduction

Here is all the code you need to run this example in Haskell:

module AnamorphismExample where

infix 5 ><

i1 = Left
i2 = Right
p1 = fst
p2 = snd

data Tree a = Node (a, [Tree a]) deriving Show

split :: (a -> b) -> (a -> c) -> a -> (b,c)
split f g x = (f x, g x)

(><) :: (a -> b) -> (c -> d) -> (a,c) -> (b,d)
f >< g = split (f . p1) (g . p2)

inTree :: (a, [Tree a]) -> Tree a
inTree = Node

anaTree h = inTree . (id >< map (anaTree h)) . h

-- our function
h_gen :: (Int, Int) -> ( (Int, Int), [ (Int, Int) ] )
h_gen(0,0) = ( (0,0), [] )
h_gen(v,0) = ( (v,0), [ (v-1,0) ] )
h_gen(0,p) = ( (0,p) , [ (0,p-1) ] )
h_gen(v,p) = ( (v,p), [ (v-1,p), (v,p-1) ] )

state = anaTree h_gen

Pass a year since I promised this post. The next will be on hylomorphisms I promise not take too that much.

### 6 responses

9 04 2009

[...] Hylomorphisms in Haskell 9 04 2009 If you miss something in this post, I suggest you to start in Catamorphisms and Anamorphisms. [...]

9 04 2009

Can your repost the code? Looks like the html ate it.

9 04 2009

Done! In fact the WordPress don’t like “<“, don’t know why…

9 04 2009

[...] 9 04 2009 If you lost yourself in this post, I advise you to start in catamorphisms, then anamorphisms and then [...]

10 04 2009

[...] Anamorphisms in Haskell First I would like to introduce the notation that I use here. The pointfree notation is good to see a program [...] [...]

12 04 2009

[...] Anamorphisms in Haskell « Ulisses Costa Blog (tags: haskell mathematics programming research anamorphism) [...]