5 ms·

Functional data structures in JavaScript with Mori

92 points by swannodette 13y ago

swannodette 13y ago
One nifty thing not covered here is that Mori also has an extremely efficient O(1) thaw to get a mutable copy of an immutable value and a O(1) freeze to get a persistent value from a mutable data structure (transient). The performance of a transient vector is shockingly close to using a JavaScript array under Google V8 for adding new elements: http://github.com/swannodette/mori#efficient-freezethaw http://github.com/swannodette/mori#efficient-freezethaw
tieTYT 13y ago
This is great. I never understood why underscore/lo-dash doesn't have a `conj` or a `concat`. JavaScript's `push` mutates data which you'd think you'd want to avoid if you're using a functional library like underscore/lo-dash. `concat` makes sense to leave out when you consider that arrays already have a `concat` function. But if that's the reasoning, why did underscore/lo-dash include `size` and `max` and all those other things that already exist?
- jkrems 13y ago
  One thing I never understood about - awful generalization - "real" functional languages is their fascination with terrible naming. What I mean is things like `car`, `cdr`, `conj` - words that are impossible to understand if you don't already know what they mean.
  - zachrose 13y ago
    It's the same with C-like syntaxes, or OOP, or *nix stream commands, or the English language, or the phonetic alphabet. It's all a thick pile of history that has been agreed upon piece by piece.
  - camus2 13y ago
    I guess there was a time where one had to care about the length of the source code. that's why some came up with these abbreviations.
  - lmm 13y ago
    That's only lisp and particularly faithful derivatives (unfortunately including clojure). Haskell uses more natural names - head, tail, last.
    - mjn 13y ago
      Even most Lisps have first/rest as synonyms of car/cdr (dating back to some very old Lisps, and mandated by the Common Lisp standard). They just don't seem to have culturally caught on as idiomatic.
  - tikhonj 13y ago
    That might just be an age thing: older languages seem particularly bad at this. Lisp has its cars and its cdrs, but C is even worse with ioctl, atoi, fputc, strxfrm and so on. Assembly is worse yet, and mixing C with assembly is basically a path to Lovecraftian madness: I really hate the way intrinsics look. Here's a real snippet from StackOverflow: a_i = __mm_load_ps(&A[n*i+k]); b_i = __mm_load_ps(&B[n*k+j]); c_i = __mm_load_ps(&C[n*i+j]); __m128d tmp1 = __mm_mul_ps(a_i,b_i); __m128d tmp2 = __mm_hadd_ps(tmp1,tmp1); __m128d tmp3 = __mm_add_ps(tmp2,tmp3); __mm_store_ps(&C[n*i+j], tmp3) You can also go too far in the other direction: see Java and especially Objective C.
augustl 13y ago
I like that the article calls then "functional data structures". Every time I call them by their real name (persistent data structures), _at least_ one person will get confused and think I'm talking about serialization to disk.
- theothershoe 13y ago
  I consistently see the same problem. That is exactly why I use the word "functional".
  - TheZenPsycho 13y ago
    what's wrong with "immutable" ?
    - augustl 13y ago
      Immutable does not imply persistence/structural sharing, a key aspect of these data structures.
- pmahoney 13y ago
  Is is possible to construct a persistent data structure that is not referentially transparent? I suspect the answer is yes, depending on how you define side effects (example: a persistent array that logs operations). Which would mean "functional" is a more general adjective than "persistent" since it includes both persistence and referential transparency. Wikipedia[1] claims "There also exist persistent data structures which use destructible operations, making them impossible to implement efficiently in purely functional languages" [1] https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
  - augustl 13y ago
    "Persistent" is but a bullet point on Clojure's own explanation of its data strucures, so I suppose we as a community should follow in the official docs' footsteps :) http://clojure.org/data_structures http://clojure.org/data_structures
rdtsc 13y ago
Of course it is obligatory to mention the classic: Okasaki's "Purely Functional Datastructures" book. http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka... Also check out this link for additional data structures worked on since then or simply not included in the book: http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki http://cstheory.stackexchange.com/questions/1539/whats-new-i...
- Arnor 13y ago
  Is this more required reading? Has anyone else's homework load doubled since college?
- swannodette 13y ago
  A minor nit, most of the data structures provided through Mori via ClojureScript are not based heavily on Okasaki's work, rather they are based on Bagwell's paper on mutable Ideal Hash Trees http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf and Rich Hickey's efficient immutable implementations in Java for Clojure
agumonkey 13y ago
IIUC they pulled out clojure's clojurescript projected core structures so you can use it ~pojo ? Recenlty I saw https://github.com/harukizaemon/hamster https://github.com/harukizaemon/hamster , similarly immutable, structure sharing, persistent data structures It's becoming mainstream ...
ds_ 13y ago
Is there a current build anywhere or do I have to build it myself?
- theothershoe 13y ago
  Install the npm package, mori. You can require it in a NodeJS project, or grab the file mori.js from the installed package and drop it in a web browser.

92 points by swannodette 13y ago

One nifty thing not covered here is that Mori also has an extremely efficient O(1) thaw to get a mutable copy of an immutable value and a O(1) freeze to get a persistent value from a mutable data structure (transient). The performance of a transient vector is shockingly close to using a JavaScript array under Google V8 for adding new elements: http://github.com/swannodette/mori#efficient-freezethaw http://github.com/swannodette/mori#efficient-freezethaw

tieTYT 13y ago

This is great. I never understood why underscore/lo-dash doesn't have a `conj` or a `concat`. JavaScript's `push` mutates data which you'd think you'd want to avoid if you're using a functional library like underscore/lo-dash. `concat` makes sense to leave out when you consider that arrays already have a `concat` function. But if that's the reasoning, why did underscore/lo-dash include `size` and `max` and all those other things that already exist?

jkrems 13y ago
One thing I never understood about - awful generalization - "real" functional languages is their fascination with terrible naming. What I mean is things like `car`, `cdr`, `conj` - words that are impossible to understand if you don't already know what they mean.
- zachrose 13y ago
  It's the same with C-like syntaxes, or OOP, or *nix stream commands, or the English language, or the phonetic alphabet. It's all a thick pile of history that has been agreed upon piece by piece.
- camus2 13y ago
  I guess there was a time where one had to care about the length of the source code. that's why some came up with these abbreviations.
- lmm 13y ago
  That's only lisp and particularly faithful derivatives (unfortunately including clojure). Haskell uses more natural names - head, tail, last.
  - mjn 13y ago
    Even most Lisps have first/rest as synonyms of car/cdr (dating back to some very old Lisps, and mandated by the Common Lisp standard). They just don't seem to have culturally caught on as idiomatic.
- tikhonj 13y ago
  That might just be an age thing: older languages seem particularly bad at this. Lisp has its cars and its cdrs, but C is even worse with ioctl, atoi, fputc, strxfrm and so on. Assembly is worse yet, and mixing C with assembly is basically a path to Lovecraftian madness: I really hate the way intrinsics look. Here's a real snippet from StackOverflow: a_i = __mm_load_ps(&A[n*i+k]); b_i = __mm_load_ps(&B[n*k+j]); c_i = __mm_load_ps(&C[n*i+j]); __m128d tmp1 = __mm_mul_ps(a_i,b_i); __m128d tmp2 = __mm_hadd_ps(tmp1,tmp1); __m128d tmp3 = __mm_add_ps(tmp2,tmp3); __mm_store_ps(&C[n*i+j], tmp3) You can also go too far in the other direction: see Java and especially Objective C.

augustl 13y ago

I like that the article calls then "functional data structures". Every time I call them by their real name (persistent data structures), _at least_ one person will get confused and think I'm talking about serialization to disk.

theothershoe 13y ago
I consistently see the same problem. That is exactly why I use the word "functional".
- TheZenPsycho 13y ago
  what's wrong with "immutable" ?
  - augustl 13y ago
    Immutable does not imply persistence/structural sharing, a key aspect of these data structures.
pmahoney 13y ago
Is is possible to construct a persistent data structure that is not referentially transparent? I suspect the answer is yes, depending on how you define side effects (example: a persistent array that logs operations). Which would mean "functional" is a more general adjective than "persistent" since it includes both persistence and referential transparency. Wikipedia[1] claims "There also exist persistent data structures which use destructible operations, making them impossible to implement efficiently in purely functional languages" [1] https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
- augustl 13y ago
  "Persistent" is but a bullet point on Clojure's own explanation of its data strucures, so I suppose we as a community should follow in the official docs' footsteps :) http://clojure.org/data_structures http://clojure.org/data_structures

rdtsc 13y ago

Of course it is obligatory to mention the classic: Okasaki's "Purely Functional Datastructures" book. http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka... Also check out this link for additional data structures worked on since then or simply not included in the book: http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki http://cstheory.stackexchange.com/questions/1539/whats-new-i...

Arnor 13y ago
Is this more required reading? Has anyone else's homework load doubled since college?
swannodette 13y ago
A minor nit, most of the data structures provided through Mori via ClojureScript are not based heavily on Okasaki's work, rather they are based on Bagwell's paper on mutable Ideal Hash Trees http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf and Rich Hickey's efficient immutable implementations in Java for Clojure

agumonkey 13y ago

IIUC they pulled out clojure's clojurescript projected core structures so you can use it ~pojo ? Recenlty I saw https://github.com/harukizaemon/hamster https://github.com/harukizaemon/hamster , similarly immutable, structure sharing, persistent data structures It's becoming mainstream ...

ds_ 13y ago

Is there a current build anywhere or do I have to build it myself?

theothershoe 13y ago
Install the npm package, mori. You can require it in a NodeJS project, or grab the file mori.js from the installed package and drop it in a web browser.