= 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 \b[$\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.
Back to article page
