5 ms·
Purely Functional Data Structures : Red Black Trees in Qi
- Uchikoma 15y agoI 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).
- william42 15y agoWith prolog you can have tree(Left,Value,Right) and such. http://everything2.com/title/Binary+search+trees+in+Prolog#William42 http://everything2.com/title/Binary+search+trees+in+Prolog#W...
- silentbicycle 15y agoCalling 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.
- Uchikoma 15y agoI agree, persistent data structures is the better term.
- me2i81 15y agoOkasaki 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.
- mnemonik 15y agoI ported Chris Okasaki's red-black trees to JavaScript a little while ago: https://github.com/fitzgen/pfds-js/blob/master/red-black-trees.js https://github.com/fitzgen/pfds-js/blob/master/red-black-tre...
- bajsejohannes 15y agoI 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.
- mnemonik 15y agoAgreed. 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.
- pavpanchekha 15y agoAn 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.
- Peaker 15y agoI 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/RedBlackTree.hs https://github.com/yairchu/red-black-tree/blob/master/RedBla...
- neoGeneva 15y agoJust for fun I translated this to F#, https://gist.github.com/1056026 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.