Ten Years of Purely Functional Data Structures (2008) | Hacker News Reader

Ten Years of Purely Functional Data Structures (2008)

okasaki.blogspot.ru

170 pointsColinWright24 comments

it mentions me! my one claim to fame... here's the review http://developers.slashdot.org/story/04/02/19/2257203/purely...

I wonder what other interesting books are out there that just need someone to review them on slashdot.

These ideas are one of the foundations of the Clojure language. Rich Hickey mentions in one of his talks that this book got him quite excited. You can see reference to it in Rich Hickey's Clojure bookshelf on Amazon http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH

I took his PLT class at Columbia and TA-ed the class later. Best professor I ever had. I believe he is now at West Point where students won't whine when he hurts their brains.

Would like to see the book re-done with Haskell as the base (rather than appendix) because that language is more "purely functional" and seems to finally have the legs it needed back in 2008.

His thesis is quite useful:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Some questions. Background: I'm coming to the whole world of functional programming via Ruby (via C).

Doesn't Clojure have purely functional (immutable) data structures? Whenever this area is talked about I always hear Clojure mentioned. Do other functional languages have libraries (standard or otherwise) of these? Are these data structures implemented in Clojure itself?

I kind of see Ruby like a hybrid functional language. Could Ruby be used to implement the data structures in this book, or would that be like a square peg in a round hole? Didn't Ruby recently get official lazy evaluation?

Hum, so many questions, so little Google :(

Yes, Clojure does have many purely functional data structures built in to its core. I don't know the precise implementations, or if they're written in Clojure or Java, but I believe they're based on the work of Phil Bagwell.

Every functional language implementation I know of has many of these data structures available as a library somewhere.

You certainly could implement these data structures in Ruby, though it's likely they wouldn't mesh as well as in a more functional language.

This Stackexchange answer has links to many papers if you're interested in more:

http://cstheory.stackexchange.com/questions/1539/whats-new-i...

Clojure was also the first mainstream (non-PF) language to implement Okasaki's as first class data structures.

I know Scala quickly followed suit, since I remember Odersky bragging in a meetup that he went out of his way to find the scientists that improved on Okasaki's work and based Scala's data structures on their work instead.

Sure you can do however, since Ruby allows destructive updates, why not use one of the established/traditional imperative data structures and then apply techniques to make them "persistent" (i.e. immutable in the functional programming sense as is also used by Okasaki and of course not using the trivial technique of copying the whole thing). Such techniques are e.g. presented in CLRS if I remember correctly.

It is not that Okasaki was the first one to implement any functional data structure. People have been doing this before and also in purely functional languages such as Haskell, ML, or Opal). He was the first to give a very nice overview, showed some new designs and even more important, showed a way for time complexity analysis (in a lazy evaluation context).

And it is this last part of the thesis that many people overlook: the importance of lazy evaluation (and thus the implied fundamental optimizations/evaluations performed by the compiler/runtime) for most of the presented data structures (i.e. everything with an amortized time complexity). Simply implementing Queues as presented in the thesis and not having a lazy language will lead to a very different time complexity than is proven there, because lazy semantics is vital for the given complexity analysis.

This is also the reason, why e.g. Clojure (or Opal from the early 90s, [1]) use other data structures to ensure functional (i.e. persistent) semantics in an eager/strict evaluation model.

[1] 1994, http://projects.uebb.tu-berlin.de/opal/trac/raw-attachment/w...

Rich Hickey says during talks that Clojure's persistent data structures are based on this book and inspired by the Haskell implementation. The book is in Hickey's recommended reading list. Language designers should pursue the books in that list; it's a good one.

http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH

The main Clojure ('JClojure') implementation has these written in Java but Clojurescript has a pure Clojure implementation and there are Clojure-in-Clojure projects that do the same. The Java versions are still slightly faster on the JVM, unless things have changed.

Clojure does not require you to program in pure functional style like Haskell. You can even write Clojure code with no immutable data structures and always use the Java paradigm data structures instead, though I do not recommend it. The support for mixing both paradigms and also transactional memory are part of the defining flexibility of Clojure. It's not a bondage and discipline affair; Clojure has a strong aesthetic but you can code however you want when you need to.

I think Scala has similar data structures, also.

> I kind of see Ruby like a hybrid functional language.

Functions aren't even first class in Ruby (though it does have closures). I certainly wouldn't describe it as a hybrid functional language.

I'd refrain from saying "functions aren't first class in ruby", unless you qualify the assertion.

E.g. you could mean "you can't call functions by just adding () at the end", or "the block syntax only allows passing one function", but these are both just syntax differences.

On the other hand, you can create standalone functions, pass them around, introspect them, invoke them, call methods on them and compose them, which is more or less what you can do with integers in python (we can agree integers are first class objects in python, I think)

So there may be reason for saying they are "not first class", but you should expand on it.

You're right, I should have backed up that assertion.

The reason I say that functions aren't first class is that if you create a function:

    def factorial(n)
      if n > 0
        n * factorial(n - 1)
      else
        1
      end
    end

You can't pass it into another function without creating an object for it. ie, using Kernel.method(:factorial). It's the same with blocks, they aren't first class, in order to construct values, you have to construct objects that holds them.

So? I can easily write

    >> Y   = ->(&x) { ->(f) { f[f] }[ ->(g) { x[ ->(*n) { g[g][*n] } ] } ] }
    >> fac = Y.call {|this| -> (n) { n > 0 ? n * this[n - 1] : 1 } }
    >> fac[5]
    => 120

You can argue that Ruby doesn't lend itself towards higher-order functional programming, but I asserting that Ruby isn't a function language isn't a tenable position.

Do you deny that factorial, as I implemented it, is a function? Do you deny that I can't pass factorial into another function without creating an object to hold it? It doesn't matter what else is true. These facts alone mean that ruby's function's aren't first class.

Common Lisp is in the same category as a FP-ish language but still mostly used in a mutable OO fashion. We have a library called FSET written in CL to add persistent data structures and convenient syntax for them to the language. I don't know how powerful ruby meta-programming is, but I imagine it isn't as easy to do(like add a syntax for persistent maps that is as convenient as the built in one). Not to mention that ruby has a reputation for much worse performance than CL, so you'll likely have to use FFI and write most of it in C.

As for clojure, I think they are all implemented in java, but I haven't been following clojure development in two years, so maybe with protocols they moved them(or could) to clojure? I don't know.

Great book. Although I'd like to see an "open source" version when you can get all the code snippets expressed in the language of your choice. When I read the book I wanted Haskell, but now I think I'd like to see it in F# or maybe even C#.

It does have the Haskell versions in the appendix.

Besides, depending on your perspective, both SML and Haskell are basically functional pseudocode.

There was something missing from the Haskell stuff, but I can't recall the details -- it's been almost 10 years ago since I read it.

But when I am reading a data structures/algorithms book, I don't want to have to deal with code (SML in this case) that I'm not super familiar with. Little things get in the way. With modern software, and the ability to dynamically swap out content, it seems a pity that we don't better tailor content to the reader.

Brilliant. I can donate $100 to get it updated and as a PDF.

What is this referring to? I see nothing obvious that mentions a donation or PDF.

I'm offering to donate $100 to the author if he would like to update the book as he mentions in his story, and I'd like to get the book as a PDF instead of on paper because of the code samples and searching.

This is my personal gift to him because I value his ideas and I hope to learn more. This may also inspire other people here to offer to donate, which will be great if it happens.

$100 here as well.

(2008)

Reply on news.ycombinator.com