= Solution
The following shared step consumes exactly one input element per recursive call of `group1`:
``
prependRun :: Eq a => a -> [[a]] -> [[a]]
prependRun x xss = (x:same):rest
where
~(same,rest) = case xss of
[] -> ([],[])
run@(y:_):runs
| x == y -> (run,runs)
| otherwise -> ([],xss)
group1 :: Eq a => [a] -> [[a]]
group1 [] = []
group1 (x:xs) = prependRun x (group1 xs)
``
The helper's input consists of nonempty runs. If its first run starts with `x`, prepend `x` to that run; otherwise create a new singleton run. <Structural induction> proves that these are the maximal equal runs in order. The irrefutable pair binding `~(same,rest)` preserves <lazy evaluation>: the first output group exposes its initial `x` without inspecting the recursively grouped tail. Thus even an infinite constant input can expose the first group and each finite prefix of that group. Finite inputs take <linear time> when <equality tests> take <constant time>.
Back to article page
