[erlang-questions] How to keep adding items to a data structure

[Richard A. O'Keefe]

On 25/04/16 9:24 AM, Donald Steven wrote:
> Thanks Oliver, I appreciate your note. I understand that a list can 
> contain different elements, as you've indicated.  That's wonderful! 
> And I have that book on order.  What I'm so frustrated by is, 
> apparently, in order to extend a list by adding new musical events, 
> that I have to keep creating new lists, like:
>
> List1 = [musical-event],
> List2 = List1 ++ [new-musical-event],
> List3 = List2 ++ [new-musical-event],
> List4 = List3 ++ [new-musical-event],
> etc.
>
> all the way to perhaps a few thousand.  This is primitive and absurd
That *IS* an absurd way to do it, but it's not primitive.
The *primitive* way to do it is

     List0 = [],
     List1 = [new_musical_event() | List0],
     ...
     List1000 = [new_musical_event() | List999],

which gives you the list in 1000...1 order.  That is as efficient a way
to build a list as you could possibly hope for: each step is O(1) in time
and space.

If you really really need the list in the opposite order,
you might be able to generate the elements in the reverse order,
or you might simply use lists:reverse/1 to reverse the result,
which takes O(n) time and space.

This is the same for Lisp, Scheme, Erlang, SML, CAML, F#, Clean, and
Haskell:  *don't* append things one at a time at the "slow" end of a
list.

The preferred method is something like
     lists:map(fun (I) -> compute element I end, lists:seq(1, 1000))
or
     [compute element I || I <- lists:seq(1, 1000)]


An alternative would be to use the 'array' module which gives you
extensible arrays implemented as some sort of tree, where fetching,
storing, and extending take logarithmic time.  But generating a list
in the "easy" direction is space- and time- efficient.