Jason (jcreed) wrote,

Today had many meetings.

PLClub was about a Hinze and Paterson paper on "Finger Trees". I had just read a functional pearl by Hinze on "1-2 Brother Trees" and am presently seeing if Okazaki's implementation of Leftist Heaps admits a metric-preserving implementation (answer: probably not, unfortunately) Summary: oh no I'm covered in treeeeees.

I think plain old binary heaps work, though. I just can't find or invent a functional implementation that is cute enough for my tastes... to much grubbing around with natural numbers when you should be able to store all the relevant information in the nodes to maintain the complete binary tree invariant. I can do it for insertions, but not both insertions and deletions.

NoBot we discussed Andreas's "crazy idea" a bit. I am still skeptical that it's fundamentally different enough to work, but we'll see. I don't know of any bounds that refute anything like it possibly working, so I'm holding my tongue for now.

Chatted with Mike Hicks about the PL angle on the DP stuff.
Tags: work

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded