>IMO the nice thing about Erlang and Elixir is their foundation of representing data is rock solid. Because data is fully immutable, you get a lot of nice things "for free" (no shared state, reliable serialisation, etc). [...] >In contrast with languages like C++ and Java where things are shakey from the ground up.

Yes, immutable does provide some guarantees for "free" to prevent some types of bugs but offering it also has "costs". It's a tradeoff.

Mutating in place is useful for highest performance. E.g. C/C++, assembler language "MOV" instruction, etc. That's why performance critical loops in high-speed stock trading, video games, machine learning backpropagation, etc all depend on mutating variables in place.

That is a good justification for why Erlang BEAM itself is written in C Language with loops that mutate variables everywhere. E.g.: https://github.com/erlang/otp/blob/master/erts/emulator/beam...

There's no need to re-write BEAM in an immutable language.

Mutable data helps performance but it also has "costs" with unwanted bugs from data races in multi-threaded programs, etc. Mutable design has tradeoffs like immutable has tradeoffs.

One can "optimize" immutable data structures to reduce the performance penalty with behind-the-scenes data-sharing, etc. (Oft-cited book: https://www.amazon.com/Purely-Functional-Data-Structures-Oka...)

But those optimizations will still not match the absolute highest ceiling of performance with C/C++/asm mutation if the fastest speed with the least amount of cpu is what you need.

> A data structure cannot be functional.

I think the author is using the term "purely functional data structure" to mean a data structure that lends itself to an implementation in a purely functional language [1,2].

[1] https://en.wikipedia.org/wiki/Purely_functional_data_structu...

[2] https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

Yup. Purely Functional Data Structures (thesis as linked, book: https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) is awesome. I especially found some of the tree-based recursive algorithms eye-opening (once you spend the time to wrap your head around them).

IMHO required reading if you're doing any heavy FP work.

The canonical text discussing how this is achieved refers to data structures optimized for immutability as "purely functional data structures". [1] These type of data structures are the default for Clojure as well, and there are a number of blog posts and presentations discussing their implementation. [2] [3]

It's a reasonably complicated topic, but the basic idea is that since the data structures are immutable, much of their structure can be shared between versions with few changes. Most of these data structures end up using a Tree of some sort. Performance characteristics can be influenced to an extent by using bucketing to control the width/height of the tree.

[1] : Purely Functional Data Structures (Amazon: https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo

Going back to the basics to solidify my foundation, one each quarter. Good Practice makes one a better engineer!

Digital Electronics using [1] Operating Systems using [2] Functional Data Structures using [3] Graphics Algorithms [4]

Any recommendations for these subjects sincerely appreciated. Thanks.

[1] https://www.amazon.com/Digital-Design-Computer-Architecture-... [2] https://www.amazon.com/Modern-Operating-Systems-Andrew-Tanen... [3] https://www.amazon.com/Purely-Functional-Structures-Chris-Ok... [4] https://www.amazon.com/Graphics-Visualization-Principles-Alg...

The more you practice, the more you can, the more you want to, the more you enjoy it, the less it tires you.” ― Robert A. Heinlein, The Cat Who Walks Through Walls

Well, when you pass a variable around, it doesn't and cannot change. This means that different threads can't get in eachothers' way anymore, for instance, but also that you can't make a big chunk of mistakes at all.

They also have serious disadvantages : they can't be memory managed in the traditional way (since they tend to reuse other instances' memory in complex ways), and thus require a GC (refcounting can work, but ...). They are VERY allocation intensive, and they are worse than most non-persistent data structures. Assuming an O(1) allocator they can match non-persistent data structures in O-ness (ie. when making an invalid assumption that is quite popular in academia. In practice memory allocation is O(1) for small values, then O(n^2) once you get close to the system's memory capacity (scanning for holes in a long list) but don't go over it, and then O(oh fuck it let's just reboot this bloody BOAT ANCHOR) when crossing that line).

Clojure is famous for having good persistent data structures. Rich Hickey went touring academia touting the benefits of immutable/persistent/functional data structures : https://www.youtube.com/watch?v=dGVqrGmwOAw&feature=youtu.be...

There's also a famous book: https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

Generally you build the new list using the tail of the old list (which is unchanged), your inserted value, and each of the values in front inserted onto that. So, immutability is preserved. Any existing references will not see their values changed. And the new references will share some memory with the old ones (how much depends on where in the list the value was inserted).

You can learn more in Okasaki's great book: http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

This book is more or less the definitive book on functional persistent data structures. More about how to design and reason about them, then a collection book.

http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

I'm curious if anyone who has read (or is familiar with the data structures described in) Purely Functional Data Structures[0] can weigh in on how this persistent vector compares to say, the real time deque which is described to have worst case runtime of O(1) for cons/head/tail/snoc/last/init (along with plenty of other structures which have similar amortized time guarantees, etc.) Do these structures not have practical performance characteristics, or is there another reason a O(log) solution was chosen? Like the other poster mentioned here, its a bit upsetting having read something that rigorously analyzes worst time behavior to have an article hand wave away log32 as "effectively constant time". Especially because amortization is even trickier to consider with persistent data structures since you have to deal with the fact that you may have many operations taking place on your worst case node (several pushes on your edge case base vector, etc). Perhaps these tries actually account for that very elegantly, but I certainly don't know enough to intuit it from what I've seen here.

0. http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

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

For those of you who aren't familiar with the author's other works, it's worth taking a peek at his other books.

I can whole heatedly recommend Pearls of Functional Algorithm Design http://www.amazon.com/Pearls-Functional-Algorithm-Design-Ric...

It's a good cross between two other excellent books:

- Jon Bentley's Programming Pearls http://www.amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/...

and

- Chris Okasaki's Purely Function Data Structures http://www.amazon.com/Purely-Functional-Structures-Chris-Oka....

If you haven't read all three, its well worth your while to do so!

And of course if you are going down the rabbit hole of reading Perls of Functional Algorithm Design then you need to read the "how to read Pearls of Functional Algorithm design" as well.

http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird...

Of course it is obligatory to mention the classic: Okasaki's "Purely Functional Datastructures" book.

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

> Lots of Lisps have been backwards-incompatible with previous Lisps. Scheme, Common Lisp, Emacs Lisp, and even MACLISP and LISP 1.5 were all significantly backwards-incompatible with their predecessors.

Right. That's what I'm saying. Clojure does not care to be backwards compatible with Lisp.

> Your taxonomy of immutability and persistence is interesting

That's not mine.

Clojure took its base data structures from Haskell and modern ML.

Not Lisp.

See:

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

http://en.wikipedia.org/wiki/Persistent_data_structure

The book comes with examples in ML and Haskell.

http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

Immutability means that if you're "modifying" the structure you must actually be "making a new copy with a small change". Structural sharing means that usually only the small change itself gets new allocation, but it's still more pointer-chasing than a continuous memory map.

Lots of algorithms don't work with this kind of copying semantics, but you have all of Purely Functional Data Structures [1] to help.

[1] http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...