Purely Functional Data Structures : Red Black Trees in Qi | Hacker News Reader

Purely Functional Data Structures : Red Black Trees in Qi

jng.imagine27.com

54 pointsjgrant2711 comments

I wish they would stop calling those data structures functional. Just call them immutable. It's the other way around. Functional languages use immutable data structures. One can use those "functional"data structures with any programming paradigma (not sure how to use them in Prolog though).

With prolog you can have tree(Left,Value,Right) and such.

http://everything2.com/title/Binary+search+trees+in+Prolog#W...

Calling them "persistent data structures" is probably more useful.

Prolog has "difference lists", which are (currently) pretty unique to Prolog. Its special case of variables that can be mutated, but only once, has interesting implications.

I agree, persistent data structures is the better term.

Okasaki called them that because he was implementing data structures in pure functional languages, so in that context it was reasonable. But in imperative languages, you're right, calling them "purely functional" is meaningless.

I ported Chris Okasaki's red-black trees to JavaScript a little while ago: https://github.com/fitzgen/pfds-js/blob/master/red-black-tre...

I think this illustrates how well pattern matching works for certain types of code. For the balance function, 7 lines of Qi becomes 45 lines of javascript. And I even think those 7 lines are easier to read.

Agreed. I think it would become quite a bit simpler if this weren't persistent and you could just move some references around. But yes, it is very verbose.

An interesting post, though the Redditor inside me barks "repost" at the pattern matching. Yes, pattern matching is nice, and it certainly shines when you do things like red-black trees; on the other hand, I'd more rather see a description, or paper, or something, on Qi's type system and where I'd use the Turing-equivalent features. And I'm not even a type geek. Or a summary of the new license, but, well, that might be too much to ask.

Just for fun I translated this to F#, https://gist.github.com/1056026

I'm not going to put any performance statistics up, though if someone has enough free time to compare the two, it'd be interesting to see the result.

I wonder if Qi can express GADTs to allow proof of balance properties, as in this Haskell example:

https://github.com/yairchu/red-black-tree/blob/master/RedBla...

Reply on news.ycombinator.com