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.
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.
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.
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
If you need more explanations feel free to contact me.