> The pure functional way to append something to a list is to return a completely new copy of the list with the new element at the end, leaving the original list unchanged. Actual functional languages are implemented in ways that make this not as disastrous as it sounds,
I'm curious : how do they manage to not make it (performance) disastrous ? Anyone could please forward me some functional-newbie-level examples ?
The short answer is that with a singly-linked list, you can easily add items to one end (conceptually, typically the front end.) Then if other code has references to the older parts of the list, they’re still valid.
A great explanation of this is in “Practical Common Lisp”:
But then there are cache locality issues, etc. Algorithmic runtime performance in practice rarely matches the basic big-O analysis taught in CS classes.
Case in point: for small cardinality data in practice it’s often (or at least occasionally) faster to use a linear time search algorithm on a fixed length array than to put it, say, in a tree, map, etc. that is big-O “better”.
I'm curious : how do they manage to not make it (performance) disastrous ? Anyone could please forward me some functional-newbie-level examples ?