Hylomorphisms in Haskell

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.


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:

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.


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

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.


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

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


If you need more explanations feel free to contact me.




2 responses

9 04 2009
More Hylomorphisms in Haskell « Ulisses Costa Blog

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

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

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: