Anamorphisms in Haskell

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:

, or .

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.

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:

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:

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:

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:

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.

About these ads

Actions

Information

6 responses

9 04 2009
Hylomorphisms in Haskell « Ulisses Costa Blog

[...] 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
Michele A

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

9 04 2009
Ulisses Costa

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

9 04 2009
More Hylomorphisms in Haskell « Ulisses Costa Blog

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

10 04 2009
Top Posts « WordPress.com

[...] 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
筆記與流年 » 網路書簽 » links for 2009-04-12

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Follow

Get every new post delivered to your Inbox.

Join 185 other followers

%d bloggers like this: