> My question: can we do better than this? It seems that this solution is> constantly building and breaking apart pairs. (Or is it, when optimized?)
I don't think we can do better (as others have commented). Laziness is a benefit for peeling off only the beginning(s) of possibly-infinite (sub-)lists.
Possibly splitting off the head to call sub-function `run x xs` is also "breaking apart". If you don't like pairs, you can split the returned list itself to give the pairing.
Using `l@(y:zs)` as did Viktor might help a little if the compiler is particularly dumb. (GHC isn't.)
> runs :: Ord a => [a] -> [[a]]
>
> runs [] = []
> runs l@[x] = [l]
> runs (x: l@(y:zs))
> | x <= y = let (ys:zs) = runs l in ((x:ys) : zs)
> | otherwise = ([x]: runs l)
This solution appears to achieve the same level of laziness as Viktor's.
AntC