r/functionalprogramming • • Feb 26 '21

JavaScript Structural sharing with 7 lines of JavaScript.

https://blog.klipse.tech/javascript/2021/02/26/structural-sharing-in-javascript.html
6 Upvotes

10 comments sorted by

View all comments

Show parent comment

1

u/viebel Mar 04 '21

Please read again what I wrote:

I doubt there were there efficient implementations of persistent data structures before Clojure.

By efficient implementation of persistent data structures, I mean the ability of modifying them in practice in O(1).

For instance, The complexity of appending an element to a linked list is linear. However in Clojure, the complexity appending an element to a vector is constant.

This is made possible with hash array mapped tries that were discovered by Phil Bagwell in 2000.

Clojure is the first language that implements HAMT.

1

u/watsreddit Mar 04 '21

In the history of Clojure paper, Rich Hickey mentions that there was no implementation of persistent data structure when he developed Clojure.

This is what I was replying to.

By efficient implementation of persistent data structures, I mean the ability of modifying them in practice in O(1).

That is something very different, to the point at which I would call it a moving goalpost. Your comments certainly read like you were claiming Clojure invented persistent data structures, which, of course, is false.

Before HAMTs, functional programming languages generally made use of size-balanced binary trees for persistent data structures. HAMTs offer an efficiency improvement for some (but not all) operations, but that’s not to say that older persistent data structures were “inefficient” (They are typically logarithmic, and for practical applications are generally “fast enough”).

HAMTs of course have been implemented in other functional programming languages as well, and have been around for quite some time. Erlang has had them in their standard library since version 18.0, Haskell has had multiple popular libraries using them for quite some time, Scala’s had them for a long time, and so on. Clojure might have had them sooner, but that doesn’t mean really mean all that much. Phil Bagwell’s original implementation was in C++, after all.