# understanding merge heap applying tree fold for heap sort

Please help me in understanding the below code. I understood how

``````map heapify
``````

works with output

`````` map heapify [34,25,28]
[Node 34 [],Node 25 [],Node 28 []]
``````

Now how shall i understand this expression step by step.

``````merge_heaps = treefold merge_heap Nil
``````

tried this by executing merge_heap individually.

``````merge_heap Nil . map heapify [34,25,28]
``````

error

``````<interactive>:13:18: error:
* Couldn't match expected type `a -> Heap a1'
with actual type `[Heap Integer]'
``````

How the left folded tree structure is being interpreted to make max heap. struck. How shall i proceed further to make sense step by step.

How to map my understanding of heap sort in imperative languages something of sort from wikipedia in functional sense. How the unbalanced tree fold structure is being heap sorted.

``````-- treefold (*) z [a,b,c,d,e,f] = (((a*b)*(c*d))*(e*f))
treefold f zero [] = zero
treefold f zero [x] = x
treefold f zero (a:b:l) = treefold f zero (f a b : pairfold l)
where
pairfold (x:y:rest) = f x y : pairfold rest
pairfold l = l -- here l will have fewer than 2 elements

data Heap a = Nil | Node a [Heap a] deriving Show
heapify x = Node x []

heapsort :: Ord a => [a] -> [a]
heapsort = flatten_heap . merge_heaps . map heapify
where
merge_heaps :: Ord a => [Heap a] -> Heap a
merge_heaps = treefold merge_heap Nil

flatten_heap Nil = []
flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps)

merge_heap :: Ord a => []
merge_heap heap Nil = heap
merge_heap node_a@(Node a heaps_a) node_b@(Node b heaps_b)
|  a < b = Node a (node_b: heaps_a)
| otherwise = Node b (node_a: heaps_b)
``````

## 1 answer

• answered 2018-01-17 05:50

The specific error you're encountering,

``````<interactive>:13:18: error:
* Couldn't match expected type `a -> Heap a1'
with actual type `[Heap Integer]'
``````

is because your test expression `merge_heap Nil . map heapify [34,25,28]` is an incorrect expansion of (part of) the defintion of `heapsort` by haskell's syntax.

You want to apply the function `merge_heaps . map heapify` to `[34,25,28]`. You can't do that by just concatenating the strings. In Haskell, function application by whitespace always has higher precedence than any binary operator.

Your code is being parsed as `merge_heaps . (map heapify [34,25,28])`, which is a type error because the parenthesized subexpression isn't a function. You want something like `(merge_heaps . map heapify) [34,25,28]` or `merge_heaps (map heapify [34,25,28])` or even `merge_heaps . map heapify \$ [34,25,28]`. Maybe not the last one for now. It can be confusing when you're still learning syntax and types.

I think `merge_heaps (map heapify [34,25,28])` is easily the simplest - it removes all operators. Stick with that for the moment.