Your friends comment

First of all, it is definitely not correct what your friend is stating. Okasaki’s book has had a major influence on data structures in several languages.

Influence

First of all, I think that we can categorize “influence” as one of either:

• Direct influence: Some programming language is implementing some of the data structures that are described.
• Indirect influence: The data structures in a language are built using techniques described in the book, but might not be the actual data structures that are described.

In both cases, people can use the described data structures or a similar one, without actually having read his book directly. But when it comes to functional data structures, most people tend to read Okasaki’s book.

Okasaki’s influence on Scala

The Scala standard library offer both mutable and immutable collections. Obviously, only the immutable ones could be derived from Okasaki’s work, so let us take a look at those:

• List: A normal cons list (singly linked list). This concept has been widely known forever (almost) and generally widely used in almost all functional languages.
• Stack: Just another abstraction put onto the list above. Nothing particularly Okasaki’ish here.
• Queue: Scala’s immutable queue is a “naive” implementation using using two lists. Although described in Okasaki’s book, this queue structure was not something that was novel when the book came out. The problems with this data structure is that is that it can be potentially slow in a persistent setting, which Okasaki improves upon in his book – but it seems Scala has stuck with this implementation due to simplicity and raw speed.
• Stream: A lazy memoized list. This is described in Okasaki’s book, but is not something that was novel at the time.
• TreeSet/TreeMap: An immutable red/black-tree. Again, this is described in Okasaki’s book, but was widely known before that as well.
• HashSet/HashMap/Vector: All are based on Phil Bagwell’s Hash Array Mapped Tries. The vectors are similar to what you find in Clojure. Although tries are briefly described by Okasaki, they were known before, and this data structure is quite far from anything else described in there.
• ListSet/ListMap/BitSet: Not described in Okasaki’s book, as far as I remember.

As you can see, most of the data structures used precede Okasaki’s book – and in that respect it does not fall under either the category direct or indirect influence as such.

Nevertheless, it would be naive to think that Okasaki’s book hasn’t influenced Scala at all. Okasaki’s description of immutable red/black-trees is more a less the go-to guide for implementing these functionally. Purely Functional Data Structures really gathers a lot of material that would otherwise only be found in various research papers – so what I would really assume, would be that the book probably helped the developers into making the decisions that best fit the language.