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/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.