Consider the following code snippet:

-- list_1 = [1, 2, 3]
-- list_2 = [4, 5, 6] 
final_list =  list_1 ++ list_2
result = map (+1) final_list

Is the time spent by it proportional just to the length of final_list, and the price of list concatenation is not paid?

My idea is that concatenation is done lazily; to quote the source of GHC Base.hs,

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

Since map constantly chips away the head of the list, I suppose that the concatenation as done by the recursive call in the last line is always done in lockstep with the map execution, so list_1 is effectively scanned only once.

Is this correct?


That's correct. It's easy to test your theory by making list_2 infinite:

list_1 = [1, 2, 3]
list_2 = repeat 4
final_list = list_1 ++ list_2
result = map (+1) final_list

print $ take 10 result
-- Outputs [2,3,4,5,5,5,5,5,5,5]

Congratulations! You just ran an infinite loop in a few microseconds! (Not really).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.