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

Cart

XML Editor - Download a Free Trial >

See What's New >

Buy Now >

[Home] [By Thread] [By Date] [Recent Entries]

Subject: Re: Cheaper to prepend or append an item to a sequence?
From: Michael Kay <mike@xxxxxxxxxxxx>
Date: Tue, 22 Feb 2011 14:32:33 +0000

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

Current Thread

RE: Cheaper to prepend or append an item to a sequence?, (continued)
- Costello, Roger L. - 22 Feb 2011 13:50:21 -0000
  - Michael Kay - 22 Feb 2011 14:25:13 -0000
    - Dimitre Novatchev - 22 Feb 2011 14:36:42 -0000
- Dimitre Novatchev - 22 Feb 2011 13:59:29 -0000
  - Michael Kay - 22 Feb 2011 14:32:43 -0000 <=
    - Dimitre Novatchev - 22 Feb 2011 14:41:14 -0000
    - Вячеслав Седов - 22 Feb 2011 19:26:47 -0000
    - Abel Braaksma - 22 Feb 2011 19:45:01 -0000
    - Вячеслав Седов - 22 Feb 2011 19:51:51 -0000

<- Previous	Index	Next ->
Re: Cheaper to prepend or app, Dimitre Novatchev	Thread	Re: Cheaper to prepend or app, Dimitre Novatchev
Re: Cheaper to prepend or app, Andrew Welch	Date	Re: RE: Cheaper to prepend or, Dimitre Novatchev
	Month

XML Editor - Download a 15 Day Free Trial Now >

See What's New in Stylus Studio >

Buy Stylus Studio - XML Editor - Now >