Hi Dave, When dealing with enumerables you have basically the choice between arrays and linked lists (well there are more kinds like comprehension/streams/etc... but it's out of scope). Building a linked list is super fast (prepending is O(1) so building a list of n elements is O(n)). Building a list with arrays, if you embrace immutability (you should!), is O(n) as you need to copy the entire array each time ; therefore it's quadratic complexity when building a list of n elements.
Moreover they are easy to write and fit the recursivity (mapping, folding) design which is held very dear in functional programmers heart :) If you need to constantly append things at the end of your linked list, you might to ask yourself the question : "but do I need to prepend too or is appending the only thing I want to do?". If yes, just switch the datastructure to a queue instead. The only reason you would want to handle arrays would be if you need random access data (maps). Otherwise, it's better to stick with linked lists. That is why functional programming language gives you both datastructures ready to use (linked lists and maps). Max On 16 June 2016 at 19:43, 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/CAOPKHetevK4%2BK_wMB_C96VZNOtxfm7tUZxY80%3Dt17_ZBg5m3Dg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
