4 ms·
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
by leif 17y ago
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.hs 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.
- kapuzineralex 17y agoI find it particularly interesting that he breaks down the number of neccessary cases to only 4 compared to the standard explanation found everywhere else.
- eru 17y agoYes, that's the power of purity. On the syntax side, or-patterns express those remaining four cases very succinctly.