Yep, you got it. If I were to be pedantic (and even then I'll probably miss something) I might call it a: Persistent Immutable Singly Linked List of Cons Cells
Persistent is how we can make immutability practical. Data structures when "updated" to a new copy, still share as much memory as possible with the old one. For example: a = [1, 2, 3] b = [0 | a] The 1, 2 and 3 elements in memory are shared with both a and b. b simply has a new cons cell at the head of the list with a pointer to the 1 cell. a retains its pointer to the 1 cell and has no knowledge of the 0 cell. If instead you did: a = [1, 2, 3] b = a ++ [4] b has to receive a new copy of the 1, 2 and 3 cons cells, plus the new 4 cell. Otherwise, a could traverse its list and find the 4 element at the end, violating immutability. Similar types of things are done with maps using a lower level data structure called a "trie". The clojure community has done some good writeups lately of persistent in-memory data structures, plus there are wikipedia pages if you want to search for more details. -Greg Vaughn PS. On the FP "can of worms" comment -- yes I can imagine a strictly defined FP to be about manipulating mutable data structures with higher order functions. However, you gain referential transparency with immutable data structures which are a foundation for concurrent benefits of FP, therefore practically when someone says "FP" they typically imply immutability as well as functions as first class. > On Jun 16, 2016, at 12:43 PM, Dave Aronson <[email protected]> > wrote: > > On Thu, Jun 16, 2016 at 12:59 PM, Greg Vaughn <[email protected]> wrote: > >> In functional programming a "list" is a specific data structure, >> much more constrained than the vernacular use of the word "list". >> It inherently has this O(n) behavior for appending. > > Can you please enlighten me on this, both the FP definition of a list, > and why (unless the definition makes it obvious) that makes it > inherently O(n) to append? I tried Googling it but came up with very > few things that looked relevant, among the lists of FP languages. :-) > I will now proceed to guess: > > From what I can tell (without peeking under the hood) Erlang's (and > thus Elixir's) lists seem to be implemented in recursive terms, as > either an empty list, or an element prepended onto a list (which may > be empty)... and the system keeps track of *each* of those lists > individually. This makes sense as why, as I've seen in some > tutorials, [1, 2, 3] is simply shorthand for [1 | [2 | [3 | []]]]. > Both are 1, prepended onto the list that consists of (2, prepended > onto the lists that consists of (3 prepended onto a list that consists > of (empty))). So, to append 4, it would need to reach down through > the layers (that's what makes it O(n)), to get to the empty list, and > replace that with 4 prepended onto a (new) list that consists of > (empty). Or rather, since things are immutable, create a new empty > list, prepend 4 to that, prepend 3 to *that* new list, and so on... > which would be O(n) even if the actual appending were instantaneous. > Whether LISP works similarly, I frankly forget, having barely touched > it since school, more years ago than I care to admit. ;-) > > Anyway, is that at least close to why? It seems to me that the > "keeping track of each layer" part is an implementation detail, and > the immutability is... well, necessary for *pure* FP as I grok it > (which admittedly isn't very well, having done mostly imperative or > OO), but not necessarily all practical FP. (...he says, realizing > he's probably opening a very big can of religiously flaming worms....) > > -- > Dave Aronson, consulting software developer of Codosaur.us, > PullRequestRoulette.com, Blog.Codosaur.us, and Dare2XL.com. > > -- > You received this message because you are subscribed to the Google Groups > "elixir-lang-talk" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/elixir-lang-talk/CAHxKQij_qCAhY-Eg7TXmgk9yLzbwTqQjT%3DaaxWr9amMA3mWgaQ%40mail.gmail.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/8BCA5E6A-C928-482E-982A-4C9BCAEE4ED5%40gmail.com. For more options, visit https://groups.google.com/d/optout.
