Re: [xsl] Cheaper to prepend or append an item to a sequence?

[Michael Kay <mike@xxxxxxxxxxxx>]

On 22/02/2011 13:58, Dimitre Novatchev wrote:
> The accepted term in most functional programming languages is "a list".
>
> A list is a functional data structure (immutable). Appending to a list
> causes the whole list to be copied and is O(N). Prepending a list is
> making just the "next pointer" of an item point to the list -- an O(1)
> operation.

Even with a forward-chained list, you can implement append without 
copying if you choose, at least for the first append operation to a 
given list (which 9 times out of 10 will be the only append operation).

Michael Kay
Saxonica