Lambda the Ultimate

Fortunately, most Slashdot readers will not regard this as an obstacle.

My favorite feature of LtU is that it's not Slashdot, no matter how hard it tries to foment language wars.

The present topic inspired these lucid Slashdot remarks:

Nice to see some actual content on Slashdot!

I am now a graduate student. I love comp-sci for what it actually is....Why am I replying to a troll??? Oh well, I feel better now.

actually, the responses have been pretty positive - a few people who've also read the book agreed, which was nice.

i was worried someone here would point out some big error in what i wrote, but really it's so vague and general that i think i'm pretty safe. not sure that's a good thing.

It's a must read if you want to master FP.

I can't find it anywhere, so I guess I was just dreaming it up. Oh, the heat..

Incidentally, Slashdot comments are actually quite good if you use the right heuristics:

Threshold: 3
Funny:    -2
Small comment penalty: 100 bytes, -1
Long comment bonus:    300 bytes, +1

since you cannot index into a mutable array (well, you could, but mutable arrays themselves are a no-no) you have to implement them using tree-like structures (to get O(logn) updates) and these are described in detail. the point of ex 10.11, if i understand it correctly, is that you use the hash as the initial index, rather than the key itself.

what more would you want the book to say? (i'm not being rude - thinking about that question helped me see why they're treated as they are).

ps i haven't looked at the thesis text (or, at least, not for a long time), but i don't think it's identical to the book. it would be an odd thesis if it was! but maybe much of the difference is in the presentation - the "meat" could be the same.

These days, however, randomized treaps as my balanced tree of choice. It's so simple you can understand what's going on just from the code, without even drawing pictures!

The notes in the title comments to the source code explain the more efficient insertion and deletion operations. The version of the code in the Scheme Untergrund library is more polished:
http://savannah.nongnu.org/cgi-bin/viewcvs/sunterlib/sunterlib/scsh/treaps/

"Bottom line: Which binary search tree is best for your application? Probably the balanced tree for which you have the best implementation readily available... Which flavor of balanced tree is probably not as important as how good the programmer was who coded it."
p178 The Algorithm Design Manual

> Treaps in Java

Treaps sound interesting, but I have a hard time reading an article that tries to compare treaps to hashtables - that's apples and oranges. I would have had more respect for the author if they had tried to compare treaps with say, red-black trees.

The article is old, (written in 97), so arguments that it uses for using a treap over Java's standard collections are out of date. I wouldn't recommend this to someone without the caveat that its mostly useful for decribing what a treap is - not why you would use one.