[Haskell-cafe] appending an element to a list

[Lanny Ripple]

My $0.02 is to say

  -- O(1)
  longList ++ [5]

Yay.  I've got a thunk.  Oh wait, I need to access the '5'?  No
different than doing so for

  -- O(n)
  until ((==5) . head) [l,o,n,g,L,i,s,t,5]

It's not the (++) that's O(n).  It's the list traversal.  I can
further beat this pedantic point to death by pointing out there is
no difference between

  longList ++ [5]

and

  longList ++ (repeat 5)

Getting to the first 5 is still O(n).

  Cheers,
  -ljr


Tillmann Rendel 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 
Lanny Ripple <lanny at cisco.com>
ScmDB / Cisco Systems, Inc.