[Haskell-cafe] appending an element to a list

Lanny Ripple lanny at cisco.com
Fri May 30 13:58:17 EDT 2008

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]


  longList ++ (repeat 5)

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


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.

More information about the Haskell-Cafe mailing list