[Haskell-cafe] appending an element to a list

[Abhay Parvate]

On Thu, May 29, 2008 at 11:48 PM, Tillmann Rendel <rendel at daimi.au.dk>
wrote:

>
>
> Adrian Neumann wrote:
>
>> Hello,
>>
>> I was wondering how expensive appending something to a list really is. Say
>> I write
>>
>> I'd say "longList ++ [5]" stays unevaluated until I consumed the whole
>> list and then appending should go in O(1). Similarly when concatenating two
>> lists.
>>
>> Is that true, or am I missing something?
>>
>
> I think that is true and you are missing something: You have to push the
> call to ++ through the whole longList while consuming it wholy one element
> at a time! So when longList has n elements, you have (n+1) calls of ++, each
> returning after O(1) steps. The first n calls return a list with the ++
> pushed down, and the last returns [5]. Summed together, that makes O(n)
> actual calls of ++ for one written by the programmer.
>
>  Tillmann
>

In other words, if you look at the prototype of ++ given in the prelude, it
generates a new list with first (length longList) elements same as those of
longList, followed by the second list. So when you are accessing elements of
(longList ++ s), you are actually accessing the elements of this newly
generated list, which are generated as and when you access them, so that by
the time you reach the first element of s, you have generated (length
longList) elements of the result of ++.



> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080530/fd7b191f/attachment-0001.htm