[Haskell-cafe] appending an element to a list
lanny at cisco.com
Fri May 30 13:58:17 EDT 2008
My $0.02 is to say
longList ++ 
Yay. I've got a thunk. Oh wait, I need to access the '5'? No
different than doing so for
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 ++ 
longList ++ (repeat 5)
Getting to the first 5 is still O(n).
Tillmann Rendel wrote:
> Adrian Neumann wrote:
>> I was wondering how expensive appending something to a list really is.
>> Say I write
>> I'd say "longList ++ " 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 . Summed together, that
> makes O(n) actual calls of ++ for one written by the programmer.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Lanny Ripple <lanny at cisco.com>
ScmDB / Cisco Systems, Inc.
More information about the Haskell-Cafe