Anamorphisms in Haskell

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 , i can say:

, or .

I will assume that you are familiarized with infix notation, , and composition 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 :

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

We could see as a the following function:

Node :: (a, [Tree a]) -> Tree 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. We represent that formally as: .

Anamorphisms

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

is the anamorphism of if the diagram commute.

We use the notation to say that function in not generic, but only works for data . The same happens with and . We will write using the composition of , and 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:

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

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

function in

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

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

In Haskell we represent the type as . So, type is . So by now, we already know the following unifications and . So now our graphic is:

function

The function 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 unify () with , and became more restrict, and unify with . A consequence of changing the co-domain of is changing the domain of it to . We represent as . Now we can be more specific with our graphic:

function rec

Here we have to get a function that co-domain is . Probably the best is to pass the first part of the tuple (part with type ) and the rest (part with type ) is just a of the function . So, now our graphic is:

As you can see, the second part of the co-domain of is the type of function :

So our final graphic became:

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

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

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.