More Hylomorphisms in Haskell

9 04 2009

If you lost yourself in this post, I advise you to start in catamorphisms, then anamorphisms and then hylomorphisms.

Like I said before (in those posts) when you write an hylomorphism over a particular data type, that means just that the intermediate structure is that data type.

In fact that data will never be stored into that intermediate type C or D. Because we glue the ana and cata together into a single recursive pattern. A and E could be some data type your function need. With this post I will try to show you more hylomorphisms over some different data types to show you the power of this field.

Leaf Tree’s

The data type that we going to discuss here is the LTree. In Haskell we can represent LTree as:

data LTree a = Leaf a | Fork (LTree a, LTree a)

Is just like a binary tree, but the information is just in the leaf’s. Even more: a leaf tree is a tree that only have leaf’s, no information on the nodes. This is an example of a leaf tree:

To represent all the hylomorphisms over Ltree we draw the following diagram:

The example I’m going to give is making the fibonacci function using a hylomorphism over this data type. If you remember the method I used before, I’m going to start by the anamorphism [(h)]. Before that I’m going to specify the strategy to define factorial. I’m going to use the diagram’s again, remember that type 1 is equivalent to Haskell ( ):

As you can see I’m going to use Ltree~1 as my intermediate structure, and I’ve already define the names of my gen functions add to the catamorphism and fibd to the anamorphism. The strategy I prefer, is do all the hard work in the anamorphism, so here the gen fibd for the anamorphism is:

fibd n | n < 2     = i1   ()
       | otherwise = i2   (n-1,n-2)

This function combined with the anamorphism, going to generate leaf tree’s with n leaf’s, being n the result of that fib.

Then we just have to write the gen add for the catamorphism. This function (combined with the catamorphism) counts the number of leafs that a leaf tree have.

add = either (const 1) plus
    where plus = uncurry (+)

The final function, the fibonacci function is the hylomorphism of those two defined before:

fib =  hyloLTree add fibd

Here is all the auxiliary functions you need to run this example:

inLTree = either Leaf Fork

outLTree :: LTree a -> Either a (LTree a,LTree a)
outLTree (Leaf a)     = i1   a
outLTree (Fork (t1,t2)) = i2    (t1,t2)

cataLTree a = a . (recLTree (cataLTree a)) . outLTree

anaLTree f = inLTree . (recLTree (anaLTree f) ) . f

hyloLTree a c = cataLTree a . anaLTree c

baseLTree g f = g -|- (f >< f)

recLTree f = baseLTree id f

Lists

The lists that I’m going to talk here, are the Haskell lists, wired into the compiler, but is a definition exist, it will be:

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

So, our diagram to represent the hylomorphism over this data type is:

The function I’m going to define as a hylomorphism is the factorial function. So, we know that our domain and co-domain is Integers, so now we can make a more specific diagram to represent our solution:

As you can see I’m going to use [Integer] to represent my intermediate data, and I’ve already define the names of my gen functions mul to the catamorphism and nats to the anamorphism. Another time, that I do all the work with the anamorphism, letting the catamorphism with little things to do (just multiply). I’m start to show you the catamorphism first:

mul = either (const 1) mul'
    where mul' = uncurry (*)

As you can see the only thing it does is multiply all the elements of a list, and multiply by 1 when reach the [] empty list.

In the other side, the anamorphism is generating a list of all the elements, starting in n (the element we want to calculate the factorial) until 1.

nats = (id -|- (split succ id)) . outNat

And finally we combine this together with our hylo, that defines the factorial function:

fac = hylo mul nats

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

inl = either (const []) (uncurry (:))

out []    = i1 ()
out (a:x) = i2(a,x)

cata g   = g . rec (cata g) . out   

ana h    = inl . (rec (ana h) ) . h

hylo g h = cata g . ana h

rec f    = id -|- id >< f

Binary Tree’s

Here, I’m going to show you the hanoi problem solved with one hylomorphism, first let’s take a look at the Btree structure:

data BTree a = Empty | Node(a, (BTree a, BTree a))

So, our generic diagram representing one hylomorphism over BTree is:

There is a well-known inductive solution to the problem given by the pseudocode below. In this solution we make use of the fact that the given problem is symmetrical with respect to all three poles. Thus it is undesirable to name the individual poles. Instead we visualize the poles as being arranged in a circle; the problem is to move the tower of disks from one pole to the next pole in a specified direction around the circle. The code defines H_n.d to be a sequence of pairs (k, d) where n is the number of disks, k is a disk number and d are directions. Disks are numbered from 0 onwards, disk 0 being the smallest. Directions are boolean values, true representing a clockwise movement and false an anti-clockwise movement. The pair (k, d) means move the disk numbered k from its current position in the direction d.

excerpt from R. Backhouse, M. Fokkinga / Information Processing Letters 77 (2001) 71–76

So, here, I will have a diagram like that, b type stands for Bool and i type for Integer:

I’m going to show all the solution here, because the description of the problem is in this quote, and in the paper:

hanoi = hyloBTree f h

f = either (const []) join
    where join(x,(l,r))=l++[x]++r

h(d,0) = Left ()
h(d,n+1) = Right ((n,d),((not d,n),(not d,n)))

And here it is, all the code you need to run this example:

inBTree :: Either () (b,(BTree b,BTree b)) -> BTree b
inBTree = either (const Empty) Node

outBTree :: BTree a -> Either () (a,(BTree a,BTree a))
outBTree Empty              = Left ()
outBTree (Node (a,(t1,t2))) = Right(a,(t1,t2))

baseBTree f g = id -|- (f >< g))

cataBTree g = g . (recBTree (cataBTree g)) . outBTree

anaBTree g = inBTree . (recBTree (anaBTree g) ) . g

hyloBTree h g = cataBTree h . anaBTree g

recBTree f = baseBTree id f

Outroduction

Maybe in the future I will talk more about that subject.





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.





Disk catalogue

23 02 2007

Bom… infelizmente não tenho tido muito tempo para dedicar ao haskell como pretendia, mas já á uns meses que tinha ideia de fazer um programa que guardasse toda a informação contida em vários CD’s e DVD’s afim de fazer uma base de dados dos mesmos e mais tarde facilitar-me nas pesquisas do “tal ficheiro que já nao me lembro onde está…”.

Confesso que a cadeira de MP1 lecionada pelo Professor José Nuno Oliveira me ajudou em muito para a idealização deste projecto…

Todo o código referente ao projecto pode ser encontrado no meu site do Centro de Apoio Open Source do CeSIUM








Follow

Get every new post delivered to your Inbox.

Join 185 other followers