4 ms·

Functional data structures are another beast altogether. Okasaki's book is the only one I have on the topic. Any other suggestions?

by rxm 10y ago

meetapoorvgupta 10y ago
CMU uses this for their Parallel Algorithm Design course: http://www.parallel-algorithms-book.com/ http://www.parallel-algorithms-book.com/ It's still a work-in-progress though.
- z1mm32m4n 10y ago
  It's a "work in progress" in the sense that the professors aren't quite completely satisfied with it. It's still very readable, which is even more impressive when you consider the complexity of the topics being covered. If you're interested, I'd recommend at least glancing at the 15-210 schedule[1] so you can see the order that the chapters are covered in the class. [1]: http://www.cs.cmu.edu/afs/cs/academic/class/15210-s16/www/schedule.html http://www.cs.cmu.edu/afs/cs/academic/class/15210-s16/www/sc...
posterboy 10y ago
No, none. That was the only publication on (necessarily) functional datastructures in the past 100 years. Maybe Turing and Church, but that's really it. Turing was especially explicit about keeping state (the notation) explicit. Do you mean recommendations? I have none, but SICP, which you probably know. I liked the first chapter so far. Also, see wiki (https://en.wikipedia.org/wiki/Purely_functional#External_links https://en.wikipedia.org/wiki/Purely_functional#External_lin...), and citations and similar articles for Osaki on google scholar. Personaly, I find the underlying theory about logics more interesting to begin with. ML was a script language for proof automation, in the bigger picture. To hijack your thread: Seeing that OOP should be possible without side-effects, I find the distinction arbitrary. The basic structures are lists. Objects are often implemented with tables.
scriptdevil 10y ago
As a person who is finally getting time to read papers in this field, I came across a Stack Overflow post [1] about newer functional data structures recently when looking for papers to put on my kindle for a long trip. The top answer to it has a tonne of links. Tangentially related, but I am currently reading Pearls of Functional Algorithm Design [2] - It is fascinatingly well written (though it isn't strictly about data structures only). I plan to read Fun of Programming [3] next which has a chapter on binary heap trees by Okasaki but the rest of the topics aren't quite about data structures. [1] http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki http://cstheory.stackexchange.com/questions/1539/whats-new-i... [2] http://www.amazon.in/Pearls-Functional-Algorithm-Design-Richard/dp/0521513383 http://www.amazon.in/Pearls-Functional-Algorithm-Design-Rich... [3] https://www.cs.ox.ac.uk/publications/books/fop/ https://www.cs.ox.ac.uk/publications/books/fop/
- rxm 10y ago
  Thank you. These, and the other answers, are great links. The Pearls book seems the right thing to get you thinking functionally.

Functional data structures are another beast altogether. Okasaki's book is the only one I have on the topic. Any other suggestions?

by rxm 10y ago

Functional data structures are another beast altogether. Okasaki's book is the only one I have on the topic. Any other suggestions?

meetapoorvgupta 10y ago

CMU uses this for their Parallel Algorithm Design course: http://www.parallel-algorithms-book.com/ http://www.parallel-algorithms-book.com/ It's still a work-in-progress though.

z1mm32m4n 10y ago
It's a "work in progress" in the sense that the professors aren't quite completely satisfied with it. It's still very readable, which is even more impressive when you consider the complexity of the topics being covered. If you're interested, I'd recommend at least glancing at the 15-210 schedule[1] so you can see the order that the chapters are covered in the class. [1]: http://www.cs.cmu.edu/afs/cs/academic/class/15210-s16/www/schedule.html http://www.cs.cmu.edu/afs/cs/academic/class/15210-s16/www/sc...

posterboy 10y ago

No, none. That was the only publication on (necessarily) functional datastructures in the past 100 years. Maybe Turing and Church, but that's really it. Turing was especially explicit about keeping state (the notation) explicit. Do you mean recommendations? I have none, but SICP, which you probably know. I liked the first chapter so far. Also, see wiki (https://en.wikipedia.org/wiki/Purely_functional#External_links https://en.wikipedia.org/wiki/Purely_functional#External_lin...), and citations and similar articles for Osaki on google scholar. Personaly, I find the underlying theory about logics more interesting to begin with. ML was a script language for proof automation, in the bigger picture. To hijack your thread: Seeing that OOP should be possible without side-effects, I find the distinction arbitrary. The basic structures are lists. Objects are often implemented with tables.

scriptdevil 10y ago

As a person who is finally getting time to read papers in this field, I came across a Stack Overflow post [1] about newer functional data structures recently when looking for papers to put on my kindle for a long trip. The top answer to it has a tonne of links. Tangentially related, but I am currently reading Pearls of Functional Algorithm Design [2] - It is fascinatingly well written (though it isn't strictly about data structures only). I plan to read Fun of Programming [3] next which has a chapter on binary heap trees by Okasaki but the rest of the topics aren't quite about data structures. [1] http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki http://cstheory.stackexchange.com/questions/1539/whats-new-i... [2] http://www.amazon.in/Pearls-Functional-Algorithm-Design-Richard/dp/0521513383 http://www.amazon.in/Pearls-Functional-Algorithm-Design-Rich... [3] https://www.cs.ox.ac.uk/publications/books/fop/ https://www.cs.ox.ac.uk/publications/books/fop/

rxm 10y ago
Thank you. These, and the other answers, are great links. The Pearls book seems the right thing to get you thinking functionally.