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.

$\xymatrix@!=2.7cm {A \ar@/_{1.8cm}/[dd]^{[|f,h|]} \ar[rr]^{h} \ar[d]^{[(h)]} & & B \ar[d]^{rec_{[(h)]}}\\C \ar[d]^{(|f|)} \ar@/^{1cm}/[rr]^{out} & \cong & D \ar@/^{1cm}/[ll]^{in} \ar[d]^{rec_{(|f|)}}\\E & & F \ar[ll]^{f}\\}$

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:
$\xymatrix@!=1cm {& & \bullet \ar@/^/[ld] \ar@/^/[rd] &\\& \bullet \ar@/^/[ld] \ar@/^/[rd] & & DATA\\DATA & & \bullet \ar@/^/[ld] \ar@/^/[rd]& \\& DATA & & DATA\\}$

To represent all the hylomorphisms over $Ltree$ we draw the following diagram:
$\xymatrix@!=2.7cm {A \ar@/_{1.8cm}/[dd]^{[|f,h|]} \ar[rr]^{h} \ar[d]^{[(h)]} & & B \ar[d]^{rec_{[(h)]}}\\Ltree~a \ar[d]^{(|f|)} \ar@/^{1cm}/[rr]^{out} & \cong & a + Ltree~a \times Ltree~a \ar@/^{1cm}/[ll]^{in} \ar[d]^{rec_{(|f|)}}\\E & & F \ar[ll]^{f}\\}$

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 $( )$:

$\xymatrix@!=2.7cm {Integer \ar@/_{2.2cm}/[dd]^{[|add,fibd|]} \ar[rr]^{fibd} \ar[d]^{[(fibd)]} & & 1 + Integer \times Integer \ar[d]^{id + [(fibd)] \times [(fibd)]}\\Ltree~1 \ar[d]^{(|add|)} \ar@/^{1cm}/[rr]^{out} & \cong & 1 + Ltree~1 \times Ltree~1 \ar@/^{1cm}/[ll]^{in} \ar[d]^{1 + (|add|) \times (|add|)}\\Integer & & \ + Integer \times Integer \ar[ll]^{add}\\}$

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:
$\xymatrix@!=2.7cm {A \ar@/_{1.8cm}/[dd]^{[|f,h|]} \ar[rr]^{h} \ar[d]^{[(h)]} & & B \ar[d]^{rec_{[(h)]}}\\[C] \ar[d]^{(|f|)} \ar@/^{1cm}/[rr]^{out} & \cong & 1 + C \times [C] \ar@/^{1cm}/[ll]^{in} \ar[d]^{rec_{(|f|)}}\\E & & F \ar[ll]^{f}\\}$

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:

$\xymatrix@!=2.5cm {Integer \ar@/_{2.1cm}/[dd]^{[|mul,nats|]} \ar[rr]^{nats} \ar[d]^{[(nats)]} & & 1 + Integer \times Integer \ar[d]^{1 + [(nats)] \times [(nats)]}\\[Integer] \ar[d]^{(|mul|)} \ar@/^{1cm}/[rr]^{out} & \cong & 1 + Integer \times [Integer] \ar@/^{1cm}/[ll]^{in} \ar[d]^{1 + (|mul|) \times (|mul|)}\\Integer & & 1 + Integer \times Integer \ar[ll]^{mul}\\}$

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:
$\xymatrix@!=2.7cm {A \ar@/_{1.8cm}/[dd]^{[|f,h|]} \ar[rr]^{h} \ar[d]^{[(h)]} & & B \ar[d]^{rec_{[(h)]}}\\BTree~a \ar[d]^{(|f|)} \ar@/^{1cm}/[rr]^{out} & \cong & 1 + a \times~BTree~a \times~BTree~a \ar@/^{1cm}/[ll]^{in} \ar[d]^{rec_{(|f|)}}\\E & & F \ar[ll]^{f}\\}$

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 speciﬁed direction around the circle. The code deﬁnes $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$:
$\xymatrix@!=2.8cm {b \times i \ar@/_{1.8cm}/[dd]^{[|f,h|]} \ar[rr]^{h} \ar[d]^{[(h)]} & & 1 + (b \times i) \times~[b \times i] \times~[b \times i] \ar[d]^{id + id \times~[(h)] \times~[(h)]}\\BTree~(i \times b) \ar[d]^{(|f|)} \ar@/^{1cm}/[rr]^{out} & \cong & 1 + (i \times b) \times~BTree~(i \times b) \times~BTree~(i \times b) \ar@/^{1cm}/[ll]^{in} \ar[d]^{id + id \times~(|f|) \times~(|f|)}\\[i \times b] & & 1 + (i \times b) \times~[i \times b] \times~[a] \ar[ll]^{f}\\}$

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.

### 3 responses

10 10 2009

To a beginner this sounds intringuing, since simple groups are very natural objects to define, whereas vertex algebras seem more convoluted. ,

18 05 2012

For the factorial example, the following Haskell functions are not defined in your example nor in the Standard Prelude:

outNat, i1, i2, split, (-|-), (> c against inferred type (Either b1 b1 -> b2, b2)’

Is there an infixity declaration necessary to make these work?

17 10 2012

Yes Douglas there are a infix declaration for (-|-) and (><):

 infix 5 >< infix 4 -|- 

These functions have the following definitions:
 f >< g = split (f . fst) (g . snd)

 

f -|- g = either (i1 . f) (i2 . g) 

And the definition of ‘outNat’, ‘i1′, ‘i2′ and ‘split’ functions are:

 outNat 0 = Left () outNat n = Right (n-1)

 i1 = Left i2 = Right 

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

Best.