David is right: our paper does not make use of any clever implementation of
(++). The one in the standard prelude suffices.
-O
-----Original Message-----
From: D. Tweed <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED] <[EMAIL PROTECTED]>
Date: Friday, January 22, 1999 1:47 PM
Subject: Re: Implementation of list concat and subclass condition
>On Fri, 22 Jan 1999, David Barton wrote:
>
>> Peter M|ller Neergaard writes:
>>
>> 1) The implementation of list concatenation ++. In the Haskell
>> report it is stated that ++ in general is an operator on monads.
>> In the case of lists, ++ works as list concatenation. However,
>> I cannot find any place describing whether the implementation of
>> ++ is supposed to be better than the straight-forward:
>>
>> [] ++ ys = ys
>> (x:xs) ++ ys = x : (xs ++ ys)
>>
>>
>> See Okasaki, "Purely Functional Data Structures" for a discussion on
>> catenable list and queues. But keep in mind that you may not need it;
>> while the running time of this algorithm is O(n), in most contexts you
>> will be accessing the resulting list from the head anyway. This means
>> that the cost of the concatenation can be amortized over the list
>> access, leading to amortized O(1) running time. Even if you don't
>> access the entire list, lazy evaluation means the unaccessed part of
>> the list won't be evaluated. Again, Okasaki gives a good summary of
>> amortized cost in the presence of lazy evaluation, and of methods of
>> proving amortized cost bounds.
>
>With regards to Peter's original motivation for the question though, from
>what I remember about the complexity argument from Bird, de Moor and Jones
>you don't need anything more efficient than the above definition in order
>get the required linear complexity (and the additional criterion that the
>algorithm is `on-line'). Pursuing more efficient implementations too far
>might well be a red herring. (I might be wrong about this of course.)
>
>___cheers,_dave_________________________________________________________
>email: [EMAIL PROTECTED] "I'm guilty of a lot of things but I've
>www.cs.bris.ac.uk/~tweed/pi.htm never violated the law of conservation
>work tel: (0117) 954-5253 of energy!" -- Bart Kosko, Nanotime
>
>
