undefined | Better HN

0 pointszogrodea2y ago0 comments

I'm not sure what you mean by "necessarily must be persistent" here, but (under my interpretation which means only persistent implementations of this data structure are possible) that's not true.

The IntMap paper by Chris Okasaki acknowledges that the data structure is not a new one (it's a PATRICIA tree), but one that was around 30 years old at the date his paper was published and deserved to be better known. The functional/persistent implementation is what's novel about Okasaki's paper.

Edit: The data structure this submission is about looks like great work! Excited to see it and will probably attempt my own ports of it to other languages.

0 comments

kccqzy2y ago

Sorry I wasn't clear. What I meant is that an idiomatic Haskell data structure needs to be persistent: an insertion needs to produce a new version of the data structure with the inserted element while keeping the original. So almost all Haskell data structures need to satisfy this requirement otherwise using it is a lot of PITA, even though the ST monad makes mutations fairly easy. However the original submission is not persistent, and so they aren't comparable.

zogrodeaOP2y ago

Oh, that makes sense and I agree. Appreciate the clarification!

j / k navigate · click thread line to collapse