How do you deal with performance problems? I mean to add an element to a list you need to create a copy of the list and then add the new element, all in order to remain functional. Isn't that very expensive?
You only have to copy if your array is implemented as a simple linear sequence of memory addresses. More advanced implementations don't have to copy everything. E.g., Clojure's vectors (its array equivalent) are effectively O(1) for the common array operations that are O(1) on naive arrays, like indexing and insertion. But Clojure vectors are still purely functional. (The actual time for some of those ops is O(log32(n)), but log32(1,000,000) = 4, so it's effectively O(1).)
The term for this is "persistent data structures", usually implemented via trees, where replacing an object in a vector is implemented by building a new tree, reusing all of the old nodes except the ones that appear in the path from the root to the replaced node. That's why Clojure's Vector is log32; it's a 32 b-tree. (I'm writing this from memory and have little Clojure experience, but I'm pretty sure I have it right.)
For people who are interested in these things, I'd highly recommend Chris Okasaki's thesis/book on the topic.
I was not familiar at all with this stuff when I read through it the first time, so it was a tad mind-bending and I probably understood ~10% of it, but it was certainly educational.
Purely functional data structures are more efficient than the naive "just copy everything" approach. You can do anything that's possible in a stateful imperative setting with at most a logarithmic slowdown.
Let's say the entries of the original list and the new one point to the same objects, still for a list of a thousand entries you need to copy all the link entries to add one on top of it. What am I missing?
If you are working in an immutable context, meaning that you are building immutable data structures to contain immutable values, there are many useful structures that you can use.
For instance, the "single linked list" or simply "list" has constant-time push and pop operations. Here such a list of 3 elements (NIL is a special value that says "no more list")
L = (((v1, (v2, (v3, NIL)))
To add v0 in front, you just create a new "cell" that reuses the old list (which remains valid by itself) as the "tail" of the new list:
L2 = (v0, L)
L2 = (v0, (((v1, (v2, (v3, NIL))))
Depending on your requirements, there are more complicated and smarter data structures that can make the operations you care about either constant, or at most logarithmic.
I did scheme assignments as part of the programming language course back in the early nineties - but then I was wondering why the runtime environment had so many GC pauses (it was some A* search assignment, if I remember correctly) also it wasn't quite fast by any standards
* GC: it probably had a very simple algorithm, rather than a fancy generational GC
* Data structures: it wouldn't support modern functional structures like HAMT
* Compilation: you probably used an interpreter, rather than compiling the code to bytecode or native code
...and of course, the algorithm itself. It may not have been designed for functional data structures, or you may not even have implemented it in a functional style in the first place (Scheme supports mutation).
It's a Scheme-to-C compiler (plus interpreter / repl / script runner.) The Scheme code is transformed into continuation passing style (CPS) and then translated into C function calls that never return, but call other functions instead, forever. Therefore the C stack can only grow, never shrink, and is used as a natural "nursery" or first generation of allocation. When it eventually overflows, the garbage collector is invoked, which scans the stack for "live" values and moves them into the permanent generation (on the heap) and resets the stack; after which, execution resumes.
It's the most ingenious way I've ever seen to turn not just Scheme, but any language with automatic allocation into fully standard C code. I think there's only one non-portable function written in assembly, the garbage collector that runs when the C stack overflows. That's a small price to pay to have a compiler that can piggyback on any existing C compiler, for virtually any platform. (It's not even entirely in assembly. IIRC, it uses some kind of setjmp / longjmp sorcery.)
Moreover, the generated C code is fully tail-recursive and call/cc comes for free, so you can use first-class continuations in complex ways, without any performance penalty. It has hygienic macros and all the advanced stuff you expect from a modern Scheme. And of course you can link to any C library, use standard C APIs from Scheme and have your code compiled to optimized machine code.
If only Scheme was not a dynamically typed language... but that's a rant for a different time.
If you just want to insert an element at the beginning of the list you can use the original list as the tail of the new list. It's immutable, so it's not going to change under you.
If you want to insert stuff randomly, you wouldn't use lists to get the best results in a functional setting. You might use something like finger trees instead.
You would want a persistent data structure, such as persistent HAMT (as in clojure, scala and others) for associative map or a tree of subvectors for an appendable ordered list. These allow most of the structure to be shared between typical mutated versions and allow value semantics as a bonus.
