= Solution
Use these <structural recursion> definitions in <Haskell>:
``
tails :: [a] -> [[a]]
tails xs = xs : ptails xs
ptails :: [a] -> [[a]]
ptails [] = []
ptails (_:xs) = tails xs
ntails :: [a] -> [[a]]
ntails [] = []
ntails xs@(_:rest) = xs : ntails rest
``
The first definition returns a known outer constructor even when `xs` is undefined, so `null (tails undefined)` is `False`, as required. The pattern in `ntails` must first determine whether the input is empty. Each <suffix of a list> is shared with the original <list>; on a finite input of length $n$, constructing the outer lists takes $O(n)$ work and additional outer-list space. No suffix is copied or measured repeatedly.
Back to article page
