Options

Question 3.4 - Merge Sort

A hylomorphism is the composite of an anamorphism and a catamorphism – the idea is that the anamorphism unfolds a data structure, and the catamorphism refolds it in some convenient way. One application of this idea is to the implementation of sorting algorithms.

In this question, we implement merge sort using a hylomorphism. Here’s the idea: The seed (the carrier of the coalgebra) is the list to be sorted. Use this function

split :: [a] -> ([a], [a])

split (a: b: t) = (a: t1, b: t2)

where

 (t1, t2) = split t

 split l = (l, [])

to split the list into two lists and use them as new seeds. Make sure you know how to deal with empty lists.

The carrier of the algebra is again a list (this time it’s actually a sorted list, but this cannot be reflected in the type). Your partial results are sorted lists. You combine them using this function.

merge :: Ord a => [a] -> [a] -> [a]

merge (a: as) (b: bs) =

if a <= b

then a : merge as (b: bs)

else b : merge (a: as) bs

merge as [] = as

merge [] bs = bs

Make sure your program also works for empty lists (it should return an empty list).

Comments

  • 1.

    The main idea of mergesort is to create smaller and smaller pieces of the input list until it becomes trivial to merge them. Each recursion call can be seen as a branching of a binary tree where the left node gets half of the current list and the right gets the other half.

    The leaves of this tree will contain lists with only one element:

    data TreeF a = Nil | LeafF Int | NodeF a a

    type TreeInt = Fix TreeF

    To build this tree from a list we create a coalgebra by assigning an empty list to Nil (to deal with empty lists), a singleton to a leaf and a list of more than one element to a new node sending half of the list to the left child and half to the righ:

    coalg :: [Int] -> TreeF [Int]

    coalg [] = Nil

    coalg [x] = LeafF x

    coalg xs = NodeF x1 x2

    where (x1,x2) = split xs

    Once we have the Tree, we can create an algebra that returns a sorted list by mapping the Nil node to the empty list, a leaf to a singleton and an inner node to the merge of its left and right children:

    alg :: TreeF [Int] -> [Int]

    alg Nil = []

    alg (LeafF x) = [x]

    alg (NodeF l r) = merge l r

    Finally, the mergesort becomes:

    mergesort = hylo alg coalg

    Comment Source:The main idea of mergesort is to create smaller and smaller pieces of the input list until it becomes trivial to merge them. Each recursion call can be seen as a branching of a binary tree where the left node gets half of the current list and the right gets the other half. The leaves of this tree will contain lists with only one element: > data TreeF a = Nil | LeafF Int | NodeF a a > type TreeInt = Fix TreeF To build this tree from a list we create a coalgebra by assigning an empty list to Nil (to deal with empty lists), a singleton to a leaf and a list of more than one element to a new node sending half of the list to the left child and half to the righ: > coalg :: [Int] -> TreeF [Int] > coalg [] = Nil > coalg [x] = LeafF x > coalg xs = NodeF x1 x2 > where (x1,x2) = split xs Once we have the Tree, we can create an algebra that returns a sorted list by mapping the Nil node to the empty list, a leaf to a singleton and an inner node to the merge of its left and right children: > alg :: TreeF [Int] -> [Int] > alg Nil = [] > alg (LeafF x) = [x] >alg (NodeF l r) = merge l r Finally, the mergesort becomes: > mergesort = hylo alg coalg
Sign In or Register to comment.