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.

, replacing that by the proper notation we have:

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 , what we are trying to say is that the intermediate structure of our combination of catamorphism and anamorphism is that data type . 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 .

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

My strategy here is to do all the work in the anamorphism, so, I need a function with type:

, or in Haskell

That function is :

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 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 , it process all the list finding the elements that satisfy the condition , 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 to :

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 , 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:

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 h g = cataBTree h . anaBTree g

And our function 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.

More Hylomorphisms in Haskell « Ulisses Costa Blog(19:41:15) :[…] 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. […]

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