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