Assembling lists start-to-end

[D. Tweed]

On Sat, 21 Jun 2003, Wolfgang Jeltsch wrote:

> On Saturday, 2003-06-21, 14:38, CEST, Mark Carroll wrote:
> > I am assembling a list from start to end. I can add elements to the end with
> > "previous ++ [current]" or I can add them with "current : previous" and
> > reverse it when I'm done. Or, maybe I should use some other data structure.
> > (I don't know the length in advance.) Any thoughts?
[snip]
> adding with "current : previous" and finally reversing the list seems good 
> since the whole process takes linear time whereas adding to the end with 
> "previous ++ [current]" would take quadratic time.

Another thing to consider is whether the list is both likely to be very,
very long & you will be processing the list in a way in which groups of
items at the top of the list are dealt with in small groups, so that lazy
evaluation would make it desirable not to have to fully construct the list
before processing any of it (and potentially removed, thus reducing memory
& hence requiring less garbage collecting). In this case, it _may_ be
better to build it up in a lazy-evaluation friendly way using functions
f,g,... of the form

f args=current:g args'
 where (current,args')=....

However, it may (a) not be possible to build it up that way and
(b) depending on the size of the datastructures in args, this approach may
make memory usage worse by requiring these big structures to be kept for
longer whereas if the list were built all at once it could be garbage
collected much quicker.

Just a random thought basically saying `it sometimes of depends what
you're going to do with the list'

___cheers,_dave_________________________________________________________
www.cs.bris.ac.uk/~tweed/  |  `It's no good going home to practise
email:tweed@cs.bris.ac.uk  |   a Special Outdoor Song which Has To Be
work tel:(0117) 954-5250   |   Sung In The Snow' -- Winnie the Pooh