Alex Rivera | Logout

F# PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Asked 2011-06-13T16:17:58.313
12

I'm working on Okasaki's Purely Functional Data Structures and trying to build F# implementations of things. I'm also going through the exercises listed in the book (some are pretty challenging). Well I'm stuck on exercise 3.4 which calls for modifying the merge function of the WeightBiasedLeftistHeap such that it executes in a single pass as opposed to the original 2 pass implementation.

I haven't been able to figure out how to do this yet and was hoping for some suggestions. There was another post here on SO where a guy does it in SML by pretty much inlining the makeT function. I started out going this route (in the commented section 3.4 First Try. But abandoned that approach because I thought that this really wasn't executing in a single pass (it still goes 'till reaching a leaf then unwinds and rebuilds the tree). Am I wrong in interpreting that as still being a two pass merge?

Here is a link to my complete implementation of WeightBiasedLeftistHeap.

Here are my failed attempts to do this in F#:

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

module WeightBiasedLeftistHeap =
    exception EmptyException

    let weight h =
        match h with
        | E -> 0
        | T(w, _,_,_) -> w

    let makeT x a b =
        let weightA = weight a
        let weightB = weight b
        if weightA >= weightB then
            T(weightA + weightB + 1, x, a, b)
        else
            T(weightA + weightB + 1, x, b, a)

    // excercise 3.4 first try
    //    let rec merge3_4 l r =
    //        match l,r with
    //        | l,E -> l
    //        | E,r -> r
    //        | T(_, lx
data-structures f# functional-programming purely-functional tailrecursion-modulo-cons
Edit
Report

1 Answer

2

I'm not exactly sure if I understood the question correctly, but here is my attempt - currently, the merge operation performs a recursive call to merge (that's the first pass) and when it reaches the end of the heap (first two cases in match), it returns the newly constructed heap back to the caller and calls makeT a couple of times (that's the second pass).

I don't think that simply inlining mMakeT is what we're asked to do (if yes, just add inline to makeT and that's done without making code less readable :-)).

What can be done, though, is to modify the merge function to use continuation-passing-style where the "rest of the work" is passed as a function to the recursive call (so there is not pending work on the stack to be done after the first pass completes). This can be done like this:

let rec merge' l r cont =
    match l,r with
    | l,E -> cont l // Return result by calling  the continuation
    | E,r -> cont r // (same here)
    | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
        if lx <= rx then
            // Perform recursive call and give it 'makeT' as a continuation
            merge' lb rh (makeT lx la)
        else
            // (same here)
            merge' lh rb (makeT rx ra)

// Using 'id' as a continuation, we just return the 
// resulting heap after it is constructed
let merge l r = merge' l r id

I'm not fully convinced this is the right answer - it performs just a single pass, but the aggregated work (in the continuation) means that the pass is two-times longer. However, I don't see a way to making this simpler, so it may be the right answer...

answered 2011-06-13T19:39:16.143

Your Answer