website statistics Purely Functional Data Structures - PDF Books Online
Hot Best Seller

Purely Functional Data Structures

Availability: Ready to download

Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to de Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to develop their own functional data structures. The author includes both classical data structures, such as red-black trees and binomial queues, and a host of new data structures developed exclusively for functional languages. All source code is given in Standard ML and Haskell, and most of the programs are easily adaptable to other functional languages. This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study.


Compare

Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to de Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to develop their own functional data structures. The author includes both classical data structures, such as red-black trees and binomial queues, and a host of new data structures developed exclusively for functional languages. All source code is given in Standard ML and Haskell, and most of the programs are easily adaptable to other functional languages. This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study.

30 review for Purely Functional Data Structures

  1. 4 out of 5

    Rose Smith

    This book was EXACTLY what I expected it to be.

  2. 4 out of 5

    Ettore Pasquini

    This book is mainly for computer scientists, not so much for engineers. The emphasis is first and foremost on theory and it didn't provide enough practicality for me. The choice of language for this book -- Standard ML -- is in line with the above: Standard ML is used in research but not as much in the industry as other languages like Haskell, Erlang, Clojure, Scala. How many people are you reaching with this choice? True, there is Haskell source code at the end of the book, and sure I can think This book is mainly for computer scientists, not so much for engineers. The emphasis is first and foremost on theory and it didn't provide enough practicality for me. The choice of language for this book -- Standard ML -- is in line with the above: Standard ML is used in research but not as much in the industry as other languages like Haskell, Erlang, Clojure, Scala. How many people are you reaching with this choice? True, there is Haskell source code at the end of the book, and sure I can think of the reason why SML was chosen (being defined formally in a very concise way, leaving out implementation details, etc) but still, I can’t shake the feeling that this choice is somewhat elitist and limiting. Plus SML is not even a pure functional language! The other problem I have with this book is that the “purely functional” part of the title doesn’t come out as clearly as I wanted to. Could be it’s just me since I mainly code in OO languages, but after the first 3 chapters there’s a lot of data/state manipulation which resonated more as imperative than functional to me. (After all SML has some imperative features.) The initial chapters instead spent time bringing this out, and those are the ones I enjoyed the most. I did take away something though: - the explanation of persistence vs performance was cool. At first this was confusing because what they refer to as persistence I call immutability. So, persistence requires that (e.g.) when joining 2 lists into one, the original lists need to be unchanged even if the joining operation should be performant. This requires copying the original lists but in practice only parts of the lists need to be copied. Very cool. - There’s a good run-through data structures I never once used professionally (binomial heaps, leftists heaps, red black trees, splay trees, …) so it was nice to read about them. - The explanation of amortization: for some collections where we need to perform some kind of processing on each item, we may not care if one item takes O(log n) or even O(n) as long as the overall computation is still O(n). - After studying the persistence + memoization + lazy evaluation + amortization theory it applied it to a queue implemented as 2 lists (front and rear), rotating its elements to amortize the cost of each insert/delete/etc operation to O(1). I didn’t have the time to dive deep into this but it’s something it’d be cool to do one day... If they ever translate this book to Erlang or some other purely functional language!

  3. 4 out of 5

    Debasish Ghosh

    It's a must read for practitioners of functional programming. Okasaki is the Alan Kay of functional programming (as Daniel Spiewak says). It's a must read for practitioners of functional programming. Okasaki is the Alan Kay of functional programming (as Daniel Spiewak says).

  4. 4 out of 5

    Barış Meriç

    It's "the book" on the functional data structures. It's "the book" on the functional data structures.

  5. 5 out of 5

    Eric

    Phew, one of those books that you really get only as much as you put into. Worth it, but prepare to work :-) (I'm afraid i was far lazier than I should have been) Phew, one of those books that you really get only as much as you put into. Worth it, but prepare to work :-) (I'm afraid i was far lazier than I should have been)

  6. 5 out of 5

    Marc Udoff

    This book is a little much for someone who doesn't write code in StandardML or Haskell or a pure functional language. If you do code in these languages his examples and code and style is very clear. Otherwise, even if you work in a language that supports functions as a first class citizen (e.g. JavaScript), you can sort of grasp what he is saying, but you won't feel like you are learning that much. I would not recommend this to anyone as a way to learn about FP, without already understanding Sta This book is a little much for someone who doesn't write code in StandardML or Haskell or a pure functional language. If you do code in these languages his examples and code and style is very clear. Otherwise, even if you work in a language that supports functions as a first class citizen (e.g. JavaScript), you can sort of grasp what he is saying, but you won't feel like you are learning that much. I would not recommend this to anyone as a way to learn about FP, without already understanding StandardML.

  7. 4 out of 5

    Junsong Li

    It's great to see persistent data structure simplifies its implementation, but I don't really see the context of the second half of this book. (Sign. I don't have applications for them...so I am not motivated to explore related problems) It's great to see persistent data structure simplifies its implementation, but I don't really see the context of the second half of this book. (Sign. I don't have applications for them...so I am not motivated to explore related problems)

  8. 5 out of 5

    Andrew

    Fascinating book on a topic not covered by anything else.

  9. 5 out of 5

    Samuel

    Raw functional elegance and performance. Is quite hard to swallow, but pretty good mental exercise

  10. 4 out of 5

    Matthias

    A very academic text, dense with complex ideas and tedious to work through; I don't think it ever took me as long to make it through a mere 180 pages. I started to skim most of the code listings and proofs half way through the book and the author definitely lost me several times with his sparse descriptions of complex but often genius ideas. Which is really why I think it was worth the effort to untangle this mess: even if you only get the gist of some of the topics covered in this book, they're A very academic text, dense with complex ideas and tedious to work through; I don't think it ever took me as long to make it through a mere 180 pages. I started to skim most of the code listings and proofs half way through the book and the author definitely lost me several times with his sparse descriptions of complex but often genius ideas. Which is really why I think it was worth the effort to untangle this mess: even if you only get the gist of some of the topics covered in this book, they're really mind bending at times. There are some remarkably cool ideas here, such as the (somewhat Gödelian) approach to implementing data structures using isomorphisms with binary number systems. Overall, however, I don't think I got a lot out of this book, certainly not anything I can see me apply to my daily programming routine.

  11. 5 out of 5

    Alejandro D-P

    A must for any functional developer.

  12. 5 out of 5

    Al Matthews

    Thesis available as PDF. The print copy contains the ML code translated into Haskell. I'm on record as saying that the Haskell is incompletely implemented, but by now I imagine I'm wrong. Thesis available as PDF. The print copy contains the ML code translated into Haskell. I'm on record as saying that the Haskell is incompletely implemented, but by now I imagine I'm wrong.

  13. 4 out of 5

    Franck Chauvel

    This book explains how to build purely functional data structure, that is, persistent structures that are not directly modified but rather copied and rebuild. Chris explains how to use lazy evaluation and other advanced functional techniques in order to reconcile functional programming and efficiency. First, the book does not read exactly like a novel. It is dense and technical and tackles difficult question. Hopefully the chapters are self contained and one can worked them separately. Every chap This book explains how to build purely functional data structure, that is, persistent structures that are not directly modified but rather copied and rebuild. Chris explains how to use lazy evaluation and other advanced functional techniques in order to reconcile functional programming and efficiency. First, the book does not read exactly like a novel. It is dense and technical and tackles difficult question. Hopefully the chapters are self contained and one can worked them separately. Every chapters requires more work and time than I was willing to spend. Still, I found the topic too narrow. Functional programming remains a niche and I believe most programmers seldom develop their own data structure, but reuse tried and tested modules—as good professionals. This book will please the curious and the mathematically oriented, but will be less useful for the regular/professional practitioners, I believe.

  14. 5 out of 5

    Ushan

    What data structures would you use in a purely functional programming language? A list is okay: all of the operations it supports, which is to say car, cdr and cons, are non-destructive and execute in O(1) time. A stack is just a list, and a queue can be modeled by two lists; we get from one and put onto the other; when the first list gets empty, we reverse the second list and make it the first; the amortized time complexity is still O(1). When we update an unbalanced binary tree, we need to rec What data structures would you use in a purely functional programming language? A list is okay: all of the operations it supports, which is to say car, cdr and cons, are non-destructive and execute in O(1) time. A stack is just a list, and a queue can be modeled by two lists; we get from one and put onto the other; when the first list gets empty, we reverse the second list and make it the first; the amortized time complexity is still O(1). When we update an unbalanced binary tree, we need to recreate all the nodes from the root to the updated node, but do not have to touch any other nodes; if there is a balancing condition, things get more complicated. There is a natural correspondence between numeral systems and data structures: unary corresponds to a list, binary corresponds to a binary tree, and there is a special numeral system called skew binary, which corresponds to a list of binary trees with nice time complexity properties.

  15. 5 out of 5

    Daniel Lyons

    This book is for FP what Design Patterns is for OOP. Read through Chapter 3 and functional purity and persistence will become clear. I consider the rest of the book optional advanced reading. Highly recommended.

  16. 4 out of 5

    Shreyashraj

  17. 4 out of 5

    Eroteme Thinks

  18. 5 out of 5

    Nikodemus Siivola

  19. 4 out of 5

    Dmytro Sirenko

  20. 4 out of 5

    Ashutosh Kumar

  21. 4 out of 5

    Xiaolin

  22. 5 out of 5

    Abdulfattah Alharby

  23. 5 out of 5

    Anupriya

  24. 5 out of 5

    Pete Poulos

  25. 5 out of 5

    Hasta

  26. 5 out of 5

    Piyush Katariya

  27. 5 out of 5

    Scott

  28. 5 out of 5

    Burgess Wong

  29. 4 out of 5

    Prashant

  30. 5 out of 5

    Dmitry Zuikov

Add a review

Your email address will not be published. Required fields are marked *

Loading...
We use cookies to give you the best online experience. By using our website you agree to our use of cookies in accordance with our cookie policy.