On Thu, Jun 16, 2016 at 1:54 PM, Peter Hamilton <[email protected]> wrote:
> If we wanted to append Z it's a very different story. > > D now needs to point to Z. Since D is immutable, we create D' that points to > Z. > C now needs to point to D'. We create C' to point to D'. And so on. Okay, I think I get it now: it's the immutability not of the list itself (which would also necessitate a copying even if appending were fast), but of the *nodes*, that makes appending slow, because of the mutation needed on the former end propagating all the way back to the head. This reminds me very much of some of the times I've designed linked lists in C, specifically the pat of deciding whether the list-node should contain the data item (e.g., have all the struct fields), or merely point to it (i.e., have only a pointer to the struct or whatever is being listed). Going with the "contain" decision, considering the entire node to be the "element", and making *that* immutable, seems to be what leads to this inefficiency. If there is some Erlang/Elixir equivalent of having the list-node separate from the datum, and considering the list-node simply a hidden implementation detail that could therefore be mutable, then maybe we could get efficient appending. If I grok in fullness, addressing this in the definitions of Elixir would hinge on mutability in Erlang, so that would be another layer we'd need to address. It's turtles all the way down. :-) I'm tempted to try to cobble something together with structs. The pattern matching on function args would probably be rather challenging though.... Thanks! -- 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/CAHxKQijNMNpajJUE9ckf0aP%2BaewHTKmJxaprzuoqiiSV_4PNcw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
