Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 3 / a / Solution

List concatenation copies the spine of its first operand and shares the second:

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

For finite first-operand length $m$, fully producing the copied spine costs $\Theta (m+1)$, independently of the second-operand length. With lazy evaluation, requesting only the first few result constructors can cost less; the bound concerns the complete concatenation spine, without forcing its element values or traversing the already existing second operand.