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
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--