5 ms·

What's new in purely functional data structures since Okasaki? (2010)

75 points by profquail 13y ago

MaxGabriel 13y ago
For people who've read it, do you have a review of Okasaki's book? Also, what background should someone have before reading it (eg should you be able to read it after reading Learn You a Haskell? Should you already be familiar with the imperative equivalents?)
- how_gauche 13y ago
  It's the best book about data structures in functional programming, as relevant today as when it was published almost fifteen (gasp) years ago. You can get a flavor of the book by reading Okasaki's PhD thesis: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf The book is essentially a fleshed-out version of this thesis.
  - hamidr 13y ago
    Why there's no updated book out there (in the cold!) ?
    - cmarschner 13y ago
      See here why not: http://okasaki.blogspot.de/2008/02/ten-years-of-purely-functional-data.html?m=1 http://okasaki.blogspot.de/2008/02/ten-years-of-purely-funct...
      - keithpeter 13y ago
        "That changed one day during a walk in the snow." The paragraph that follows this phrase in the OA is straight out of The psychology of invention in the mathematical field by Jacques Hadamard.
- spacemanaki 13y ago
  Short answer: I don't think LYAH would be entirely sufficient background, and I think familiarity with imperative equivalents is a prerequisite, but along with some other background. Long version: I stumbled a bit when trying to read this book, because I'm not super comfortable with the formal techniques for analyzing algorithms. I'm not talking about the kind of fluffy-tech-company-interview-"knows what big Oh is and can estimate it roughly on a whiteboard" ability but actually something much more concrete and formal, the kind taught in an undergrad algorithms class or in CLRS. I've taken those classes, I have CLRS on my shelf and have read some of it, but it's been a long time and it's not at my fingertips. There are exercises in the book ("prove that this data structure has this amortized performance", "prove that it does if you change this one thing", etc...) that challenged me quite a bit, and I ended up putting it down after a while thinking I would revisit it after refreshing my fundamentals. The ML code is easy enough to follow if you know Haskell, but since the point is often to understand the subtlety of the performance characteristics of the data structures and algorithms, just reading and playing with the code wasn't enough for me. After all you can trivially implement functional data structures naively just by copying everything on every operation. Frankly, Rich Hickey's videos on Clojure's data structures have done a lot more for me in terms of understanding how functional data structures work, even though they are much less formal in presentation. To be clear: I think Okasaki's book is probably a very good book and an important work, but am not so sure it is crucial for the working functional programmer to internalize all the mathematical details. Anyway, YMMV. Check out his thesis and see what you think before buying it.
- dllthomas 13y ago
  It's outstanding. My favorite bit is the section on building data structures with various characteristics inspired by obscure number systems (zeroless binary numbers, skew binary numbers...). I'd recommend some experience with complexity analysis (though "ages ago in school" is probably fine). I found most of the SML examples to be reasonably transparent, though I did some OCaml ages ago and have been working with Haskell more recently. He uses laziness heavily, but it's explicit. Knowing your way around a few imperative data structures is almost certainly worthwhile; I'm not positive it's strictly necessary.
ot 13y ago
Note that this thread has been submitted many times to HN, but it never generated generate many comments: https://www.hnsearch.com/search#request/submissions&q=what's+new+okasaki&start=0 https://www.hnsearch.com/search#request/submissions&q=what's...
- skybrian 13y ago
  I think posting one algorithm you really like and explaining why works better than a laundry list.
kazagistar 13y ago
Out of curiosity, how to purely functional data structures compare with classic mutable data structures in terms of real hardware performance? From what I hear, they are useful if you are into functional purity, and sometimes if you are doing certain parallel programming tasks, but suffer significant overhead outside that domain, but I would like to hear of any specific evidence people have in either direction.
- chipsy 13y ago
  The biggest benefit of a purely functional data structure for performance is the same as functional programming in general - they capture the problem in a way that is easier for a compiler to reason about and rewrite to hardware-optimized forms; a computation problem addressed in functional style is going to have fewer ordering dependencies, and (depending on the language) a potentially richer, more expressive type system enabling more aggressive optimizations. Functional code happens to be particularly amenable to parallel optimization, so it's one of the go-to examples of what can be done. In a practical benchmarking scenario like gcc vs. GHC on the benchmarks game[0], gcc is still going to win most of the time. This is mainly a reflection of where the bulk of effort in compiler technology has gone, though, not a definitive "a purely functional data structure is going to be slower" statement. You're leaning a lot more on your compiler when trying to make functional languages run fast, and the biggest benefits of compiler optimizers are going to appear in the overall performance of applications, not benchmarks of an individual data structure. That said, there are also plenty of examples where a mutable structure just wins and nothing with equivalent performance is likely to appear in the functional world anytime soon. If you want to get into the details of that you have to look at each category of data structure case-by-case. [0] http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=gcc&lang2=ghc&data=u64q http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?t...
- evincarofautumn 13y ago
  If I may make a sweeping overgeneralisation and phrase it poorly, immutable data structures tend to be logarithmically worse (esp. in terms of allocations) than mutable structures. But if your language or runtime can prove that a reference is unique, then that overhead can be eliminated because the runtime can simply mutate with no one the wiser. And these languages tend to use GCs in which allocations are cheap, besides the fact that sharing saves you on copying. There are many factors at play. Source: professional Haskell and C++ programmer extraordinaire.
Aqueous 13y ago
Even as a rabid user of Scala and sometimes Erlang, it strikes me that "exciting purely functional data structures" may be an oxymoron.
moomin 13y ago
The importance of the Phil Bagwell/Rich Hickey* vector can't be understated. AFAIK, pretty much all standard immutable lists provided by platforms use this work. *Bagwell designed the tries as a mutable data structure. Hickey saw how to apply that to a workable immutable list implementation.

75 points by profquail 13y ago

For people who've read it, do you have a review of Okasaki's book? Also, what background should someone have before reading it (eg should you be able to read it after reading Learn You a Haskell? Should you already be familiar with the imperative equivalents?)

how_gauche 13y ago
It's the best book about data structures in functional programming, as relevant today as when it was published almost fifteen (gasp) years ago. You can get a flavor of the book by reading Okasaki's PhD thesis: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf The book is essentially a fleshed-out version of this thesis.
- hamidr 13y ago
  Why there's no updated book out there (in the cold!) ?
  - cmarschner 13y ago
    See here why not: http://okasaki.blogspot.de/2008/02/ten-years-of-purely-functional-data.html?m=1 http://okasaki.blogspot.de/2008/02/ten-years-of-purely-funct...
    - keithpeter 13y ago
      "That changed one day during a walk in the snow." The paragraph that follows this phrase in the OA is straight out of The psychology of invention in the mathematical field by Jacques Hadamard.
spacemanaki 13y ago
Short answer: I don't think LYAH would be entirely sufficient background, and I think familiarity with imperative equivalents is a prerequisite, but along with some other background. Long version: I stumbled a bit when trying to read this book, because I'm not super comfortable with the formal techniques for analyzing algorithms. I'm not talking about the kind of fluffy-tech-company-interview-"knows what big Oh is and can estimate it roughly on a whiteboard" ability but actually something much more concrete and formal, the kind taught in an undergrad algorithms class or in CLRS. I've taken those classes, I have CLRS on my shelf and have read some of it, but it's been a long time and it's not at my fingertips. There are exercises in the book ("prove that this data structure has this amortized performance", "prove that it does if you change this one thing", etc...) that challenged me quite a bit, and I ended up putting it down after a while thinking I would revisit it after refreshing my fundamentals. The ML code is easy enough to follow if you know Haskell, but since the point is often to understand the subtlety of the performance characteristics of the data structures and algorithms, just reading and playing with the code wasn't enough for me. After all you can trivially implement functional data structures naively just by copying everything on every operation. Frankly, Rich Hickey's videos on Clojure's data structures have done a lot more for me in terms of understanding how functional data structures work, even though they are much less formal in presentation. To be clear: I think Okasaki's book is probably a very good book and an important work, but am not so sure it is crucial for the working functional programmer to internalize all the mathematical details. Anyway, YMMV. Check out his thesis and see what you think before buying it.
dllthomas 13y ago
It's outstanding. My favorite bit is the section on building data structures with various characteristics inspired by obscure number systems (zeroless binary numbers, skew binary numbers...). I'd recommend some experience with complexity analysis (though "ages ago in school" is probably fine). I found most of the SML examples to be reasonably transparent, though I did some OCaml ages ago and have been working with Haskell more recently. He uses laziness heavily, but it's explicit. Knowing your way around a few imperative data structures is almost certainly worthwhile; I'm not positive it's strictly necessary.

ot 13y ago

Note that this thread has been submitted many times to HN, but it never generated generate many comments: https://www.hnsearch.com/search#request/submissions&q=what's+new+okasaki&start=0 https://www.hnsearch.com/search#request/submissions&q=what's...

skybrian 13y ago
I think posting one algorithm you really like and explaining why works better than a laundry list.

kazagistar 13y ago

Out of curiosity, how to purely functional data structures compare with classic mutable data structures in terms of real hardware performance? From what I hear, they are useful if you are into functional purity, and sometimes if you are doing certain parallel programming tasks, but suffer significant overhead outside that domain, but I would like to hear of any specific evidence people have in either direction.

chipsy 13y ago
The biggest benefit of a purely functional data structure for performance is the same as functional programming in general - they capture the problem in a way that is easier for a compiler to reason about and rewrite to hardware-optimized forms; a computation problem addressed in functional style is going to have fewer ordering dependencies, and (depending on the language) a potentially richer, more expressive type system enabling more aggressive optimizations. Functional code happens to be particularly amenable to parallel optimization, so it's one of the go-to examples of what can be done. In a practical benchmarking scenario like gcc vs. GHC on the benchmarks game[0], gcc is still going to win most of the time. This is mainly a reflection of where the bulk of effort in compiler technology has gone, though, not a definitive "a purely functional data structure is going to be slower" statement. You're leaning a lot more on your compiler when trying to make functional languages run fast, and the biggest benefits of compiler optimizers are going to appear in the overall performance of applications, not benchmarks of an individual data structure. That said, there are also plenty of examples where a mutable structure just wins and nothing with equivalent performance is likely to appear in the functional world anytime soon. If you want to get into the details of that you have to look at each category of data structure case-by-case. [0] http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=gcc&lang2=ghc&data=u64q http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?t...
evincarofautumn 13y ago
If I may make a sweeping overgeneralisation and phrase it poorly, immutable data structures tend to be logarithmically worse (esp. in terms of allocations) than mutable structures. But if your language or runtime can prove that a reference is unique, then that overhead can be eliminated because the runtime can simply mutate with no one the wiser. And these languages tend to use GCs in which allocations are cheap, besides the fact that sharing saves you on copying. There are many factors at play. Source: professional Haskell and C++ programmer extraordinaire.

Aqueous 13y ago

Even as a rabid user of Scala and sometimes Erlang, it strikes me that "exciting purely functional data structures" may be an oxymoron.

moomin 13y ago

The importance of the Phil Bagwell/Rich Hickey* vector can't be understated. AFAIK, pretty much all standard immutable lists provided by platforms use this work. *Bagwell designed the tries as a mutable data structure. Hickey saw how to apply that to a workable immutable list implementation.