= Solution
For <prefixes of a list>, the corresponding <Haskell> definitions are
``
inits :: [a] -> [[a]]
inits xs = [] : ninits xs
pinits :: [a] -> [[a]]
pinits [] = []
pinits (x:xs) = [] : map (x:) (pinits xs)
ninits :: [a] -> [[a]]
ninits [] = []
ninits (x:xs) = map (x:) (inits xs)
``
The empty prefix is available without inspecting the input in `inits`. Every nonempty <prefix of a list> begins with its input's head, explaining the last equation. For `pinits (x:xs)`, prepend `x` only to proper prefixes of `xs`, and include the empty prefix.
On finite inputs, `inits [] = [[]]`, whereas both other functions return `[]`. On an infinite input, all finite prefixes are proper and these definitions produce them incrementally. Fully constructing all elements of all prefixes takes $\Theta(n^2)$ work for an input of length $n$, matching the size of that output; there are no repeated end-append operations to add another factor.
Back to article page
