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

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 ofheapsort
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]
ormerge_heaps (map heapify [34,25,28])
or evenmerge_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.