= Solution
Use <pattern matching> to separate the empty <list> from a head and tail. In <Haskell>, hide the conflicting <Standard Prelude> names; the examination's `init` returns \i[all] <prefixes of a list>, unlike the usual <Standard Prelude> function of that name.
``
import Prelude hiding (map, length, init, tails, foldr, compare)
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
length :: Num n => [a] -> n
length [] = 0
length (_:xs) = 1 + length xs
copy :: (Eq n, Num n) => n -> a -> [a]
copy 0 xs = []
copy n xs = xs : copy (n-1) xs
combine :: [[a]] -> [[a]] -> [[a]]
combine [] _ = []
combine _ [] = []
combine (xs:xss) (ys:yss) = (xs ++ ys) : combine xss yss
init :: [a] -> [[a]]
init [] = [[]]
init (x:xs) = [] : map (x:) (init xs)
tails :: [a] -> [[a]]
tails [] = [[]]
tails (x:xs) = (x:xs) : tails xs
``
The <map function> preserves the input <list> shape while transforming each entry. `length` counts the cons cells. `copy` repeats the whole value `xs`, so for the specified use its second argument is a <list> and the result is a <list> of <lists>. Its inferred type is more general: the repeated value can have any <data type>. If one restricts the interface to <lists>, the corresponding type is `(Eq n, Num n) => n -> [a] -> [[a]]`. The numeric argument has the <precondition> that it is a nonnegative <integer>; the most general inferred numeric constraints do not guarantee termination on arbitrary values of their instances. An explicitly integral interface may instead use `Integral n => n -> [a] -> [[a]]`.
`combine` performs <list concatenation> head by head and stops as soon as either outer <list> ends. For `init`, every nonempty <prefix of a list> starts with `x` and continues with a <prefix of a list> from `xs`; prepending `[]` supplies the shortest <prefix of a list>. For `tails`, the longest <suffix of a list> is the whole input, followed by all <suffixes of a list> of its tail. For example, `init [1,2] = [[],[1],[1,2]]` and `tails [1,2] = [[1,2],[2],[]]`. Thus both include the empty <list>, and
$$
\boxed{|\operatorname{init}(xs)|=|\operatorname{tails}(xs)|=|xs|+1.}
$$
Back to article page
