understanding merge heap applying tree fold for heap sort

Question

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)

Answer 1

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.