It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.3K
- Chat 499
- Study Groups 17
- Petri Nets 8
- Epidemiology 3
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 67
- Azimuth Code Project 110
- Statistical methods 3
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

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

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:

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:

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:

Finally, the mergesort becomes:

`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`