Weight-Biased Leftist Heaps: advantages of top-down version of merge?

Question

I am self-studying Okasaki's Purely Functional Data Structures, now on exercise 3.4, which asks to reason about and implement a weight-biased leftist heap. This is my basic implementation:

(* 3.4 (b) *)
functor WeightBiasedLeftistHeap (Element : Ordered) : Heap =
struct
  structure Elem = Element

  datatype Heap = E | T of int * Elem.T * Heap * Heap

  fun size E = 0
    | size (T (s, _, _, _)) = s
  fun makeT (x, a, b) =
    let
      val sizet = size a + size b + 1
    in
      if size a >= size b then T (sizet, x, a, b)
      else T (sizet, x, b, a)
    end

  val empty = E
  fun isEmpty E = true | isEmpty _ = false

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (_, x, a1, b1), h2 as T (_, y, a2, b2)) =
      if Elem.leq (x, y) then makeT (x, a1, merge (b1, h2))
      else makeT (y, a2, merge (h1, b2))
  fun insert (x, h) = merge (T (1, x, E, E), h)

  fun findMin E = raise Empty
    | findMin (T (_, x, a, b)) = x
  fun deleteMin E = raise Empty
    | deleteMin (T (_, x, a, b)) = merge (a, b)
end

Now, in 3.4 (c) & (d), it asks:

Currently, merge operates in two passes: a top-down pass consisting of calls to merge, and a bottom-up pass consisting of calls to the helper function, makeT. Modify merge to operate in a single, top-down pass. What advantages would the top-down version of merge have in a lazy environment? In a concurrent environment?

I changed the merge function by simply inlining makeT, but I fail to see any advantages, so I think I haven't grasped the spirit of these parts of the exercise. What am I missing?

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
      let
        val st = s1 + s2
        val (v, a, b) =
          if Elem.leq (x, y) then (x, a1, merge (b1, h2))
          else (y, a2, merge (h1, b2))
        in
          if size a >= size b then T (st, v, a, b)
          else T (st, v, b, a)
        end

---

I think I've figured out one point with regards to lazy evaluation. If I don't use the recursive merge to calculate the size, then the recursive call won't need to be evaluated until the child is needed:

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
      let
    val st = s1 + s2
        val (v, ma, mb1, mb2) =
        if Elem.leq (x, y) then (x, a1, b1, h2)
        else (y, a2, h1, b2)
      in
        if size ma >= size mb1 + size mb2
        then T (st, v, ma, merge (mb1, mb2))
        else T (st, v, merge (mb1, mb2), ma)
      end

Is that all? I am not sure about concurrency though.

Answer 1

I think you've essentially got it as far as the lazy evaluation goes -- it's not very helpful to use lazy evaluation if you are going to have to end up traversing the whole data structure to find out anything every time you do a merge...

As to the concurrency, I expect the issue is that if, while one thread is evaluating the merge, another comes along and wants to look something up, it will not be able to get anything useful done at least until the first thread completes the merge. (And it might even take longer than that.)

Answer 2

It doesn’t any benefit to WMERGE-3-4C function in a lazy environment. It still does all the work that the original down-up merge did. It pretty sure it would not be any easier for the language system to memorize.. No benefit to WMERGE-3-4C functions in a concurrent environment. Each call to WMERGE-3-4C does all its work before passing the buck to another instance of WMERGE-3-4C. In fact, if we eliminated the recursion by hand, WMERGE-3-4C could be implemented as a single loop that does all the work while accumulating a stack, then a second loop that does the REDUCE work on the stack. The first loop would not be naturally parallizable, though maybe the REDUCE could operate by calling the function on pairs, in parallel, until only one element remained in the list.