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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Lanny Ripple <[EMAIL PROTECTED]> ScmDB / Cisco Systems, Inc. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe