News for hackers. Stuff that matters.
Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by Xichekolas on Tuesday March 16, 2010 @03:46AM (#1195250)
If you haven't read Okasaki's dissertation:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

I'd highly recommend it. It's hard to find a dissertation that reads like a novel, but he somehow managed to accomplish such a feat.

Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by alexkay on Tuesday March 16, 2010 @06:38AM (#1195402)

  It's hard to find a dissertation that reads like a novel
That's why he turned it into a book: http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...
Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by Xichekolas on Tuesday March 16, 2010 @02:14PM (#1196396)
Good point. Judging from the table of contents, he added a chapter up front on various types of trees, tacked on Haskell source in the appendix, and mushed all the conclusions together.

But I'm a poor grad student, so I'll read the free dissertation over the $75 book. ;)

Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by leif on Tuesday March 16, 2010 @01:50AM (#1195139)
This is probably the best explanation of Red-Black trees, even outside of a functional setting.

There is an implementation that is pretty faithful to Okasaki's paper here: http://www.cs.kent.ac.uk/people/staff/smk/redblack/Untyped.h... . I used as a reference once because it also implements delete.

In the same directory, Kahrs develops other versions with stronger constraints coming from the type system, but I never got far enough in to Haskell back then to understand them.

Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by kapuzineralex on Tuesday March 16, 2010 @03:35AM (#1195239)
I find it particularly interesting that he breaks down the number of neccessary cases to only 4 compared to the standard explanation found everywhere else.
Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by eru on Tuesday March 16, 2010 @07:06AM (#1195426)
Yes, that's the power of purity. On the syntax side, or-patterns express those remaining four cases very succinctly.
Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by fadmmatt on Tuesday March 16, 2010 @01:16AM (#1195082)
In case anyone needs them, I wrote up Okasaki red-black trees for Scala:

http://matt.might.net/articles/implementation-of-immutable-p...

Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by kapuzineralex on Tuesday March 16, 2010 @03:34AM (#1195238)
Well, thanks, I was just about to take Okasaki's paper and see what an implementation in Scala would look like.
Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by thirdstation on Tuesday March 16, 2010 @10:58AM (#1195808)
I took his Programming Languages and Translators class when he was at Columbia. It was, hands-down, the best class I've ever taken. His enthusiasm for the subject was evident. The aspect about the class I liked best, and which I try to emulate, it that he rarely ever directly answered a question. He would, with incredible patience, ask you questions in-turn to help lead you to the solution or definition. I always found that impressive from a graduate-level professor.

I think I still have his ML implementation of Red-Black trees he gave the class.

Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by rogermugs on Tuesday March 16, 2010 @08:22AM (#1195515)
bst were the first time i went "holy crap. i love complex problem solving"