9 04 2009

If you miss something in this post, I suggest you to start in Catamorphisms and Anamorphisms.

A Hylomorphism is just the composition of one catamorphism and then one anamorphism.
$hylo~f~h~=~cata~f~\circ~ana~h$, replacing that by the proper notation we have: $[|f,h|]~=~(|f|)~\circ~[(h)]$

In this post I will use the structure of a binary tree:

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


I will use the tuples to don’t have to write uncurry’s. As I will show you, when we say that we are making a hylomorphism on a particular data type $T$, what we are trying to say is that the intermediate structure of our combination of catamorphism and anamorphism is that data type $T$. This is the structure throw our morphism will communicate with each other.

## Anamorphism

So, here I will solve the Quicksort algorithm with a hylomorphism over $BTree$.

The intermediate structure being a $BTree$ doesn’t mean that my function will receive $BTree$. My $qSort$ function works over lists. So the first thing to do, is draw the respective anamorphism from $[a]$ to $BTree~a$:

$\xymatrix@!=4.7cm {[a] \ar[r]^h \ar[d]^{[(h)]} & 1 + a \times~[a] \times~[a] \ar[d]^{id + id \times~[(h)] \times~[(h)]}\\BTree~a & 1 + a \times~BTree~a \times~BTree~a \ar[l]^{in} \\}$

My strategy here is to do all the work in the anamorphism, so, I need a function $h$ with type:
$h : [a] \rightarrow 1 + a \times [a] \times [a]$, or in Haskell $h :: [a] \rightarrow Either () (a, ([a], [a]))$

That function is $qsep$:

qsep :: [a] -> Either () (a, ([a], [a]))
qsep []    = Left ()
qsep (h:t) = Right (h,(s,l))
where (s,l) = part (<h) t

part:: (a -> Bool) -> [a] -> ([a], [a])
part p []                = ([],[])
part p (h:t) | p h       = let (s,l) = part p t in (h:s,l)
| otherwise = let (s,l) = part p t in (s,h:l)


This code is very simple, in $qsep$ I chose a pivotal element (first one), and filter the bigger to one side, and the other ones to the other, just like the algorithm. The function that do all that job is $part$, it process all the list finding the elements that satisfy the condition $p$, to put them in the left side of the tuple, and the others into the right side.

This function by it self don’t do almost anything, it is only a simple part of the algorithm.

## Catamorphism

Next step is to see the diagram for catamorphisms from $BTree~a$ to $[a]$:

$\xymatrix@!=4.7cm {BTree~a \ar[d]^{(|f|)} \ar[r]^{out} & 1 + a \times~BTree~a \times~BTree~a \ar[d]^{id + id \times~(|f|) \times~(|f|)}\\[a] & 1 + a \times~[a] \times~[a] \ar[l]^{f}\\}$

As I said before, the heavy duty is on the side of the anamorphism, so here, the catamorphism will be very very simple. In fact it is.

inord :: Either a (a, ([a], [a])) -> [a]
inord = either (const []) join
where join(x,(l,r))=l++[x]++r


That right! The only thing that the catamorphism do is a inorder passage over the structures $a + a \times [a] \times [a]$, which is very simple, as as shown by the code.

## Hylomorphism

The first thing is to draw the diagram, now for the hylomorphism, the composition of the cata with the ana:

$\xymatrix@!=2.7cm {[a] \ar@/_{1.8cm}/[dd]^{[|f,h|]} \ar[rr]^{h} \ar[d]^{[(h)]} & & 1 + a \times~[a] \times~[a] \ar[d]^{id + id \times~[(h)] \times~[(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]^{id + id \times~(|f|) \times~(|f|)}\\[a] & & 1 + a \times~[a] \times~[a] \ar[ll]^{f}\\}$

Once having made the two most important parts of the function (the ana and cata), the hylo is very simple to do. You just have to make a function $hyloBTree$:

hyloBTree h g = cataBTree h . anaBTree g


And our function $qSort$ bacame:

qSort :: Ord a => [a] -> [a]
qSort = hyloBTree inord qsep


And that’s it, now I’m going to show you the all code that you need to put all the things together and working.

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

If you need more explanations feel free to contact me.

### 2 responses

9 04 2009

[…] 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. […]

12 04 2009

[…] Hylomorphisms in Haskell « Ulisses Costa Blog A Hylomorphism is just the composition of one catamorphism and then one anamorphism. (tags: haskell functional mathematics programming research) […]