Does using Haskell's (++) operator to append to list cause multiple list traversals? -

does appending haskell list (++) cause lists traversed multiple times?

i tried simple experiment in ghci.

the first run:

$ ghci ghci, version 7.8.4: http://www.haskell.org/ghc/  :? prelude> let t = replicate 9999999 'a' ++ ['x'] in last t 'x' (0.33 secs, 1129265584 bytes) 

the second run:

$ ghci ghci, version 7.8.4: http://www.haskell.org/ghc/  :? prelude> let t = replicate 9999999 'a' in last t 'a' (0.18 secs, 568843816 bytes) 

the difference ++ ['x'] append last element list. causes runtime increase .18s .33s, , memory increase 568mb 1.12gb.

so seems indeed cause multiple traversals. can confirm on more theoretical grounds?

i'd talk bit happens when enable optimizations, because can transform performance characteristics of program pretty radically. i'll looking @ core output produced ghc -o2 main.hs -ddump-simpl -dsuppress-all. also, run compiled programs +rts -s info memory usage , running time.

with ghc 7.8.4 2 versions of code run in same amount of time , same amount of heap allocation. that's because replicate 9999999 'a' , ++ ['x'] replaced genlist 9999999, genlist looks following (not same, employ liberal translation original core):

genlist :: int -> [char] genlist n | n <= 1 = "ax"           | otherwise = 'a' : genlist (n - 1) 

since generation , concatenation in single step, allocate each list cell once.

with ghc 7.10.1, fancy new optimizations list processing. both of our programs allocate memory print $ "hello world" program (about 52 kb on machine). because skip list creation entirely. last fused away too; instead call getlast 9999999, getlast being:

getlast :: int -> char getlast 1 = 'x' getlast n = getlast (n - 1) 

in executable we'll have small machine code loop counts down 9999999 1. ghc not quite smart enough skip computation , go straight returning 'x', job nevertheless, , in end gives rather different original code.