= Solution
A call can instead produce an entire run and recurse on the unused input:
``
groupRuns :: Eq a => [a] -> [[a]]
groupRuns [] = []
groupRuns (x:xs) = (x:ys) : groupRuns zs
where (ys,zs) = span (== x) xs
``
Here `span` returns the longest matching <prefix of a list> and the remaining <suffix of a list>. Thus `x:ys` is the first maximal run, while `zs` begins the next run or is empty. Each recursive call produces one outer output element. The lazy pair binding permits output of the first constructor before the run's endpoint is known. Every finite input position is scanned a bounded number of times, so the <time complexity> is $\Theta(n)$ for unit-cost equality, including output construction.<Haskell 2010 Language Report>[Chapter 9, Standard Prelude, definition of span]{ref}
Back to article page
