[Haskell-cafe] Basic list exercise

17 Mar 2023

      Dear Cafe,

Here's a basic exercise in list processing: define a function

runs :: Ord a => [a] -> [[a]]

that breaks up its input list into a list of increasing "runs"; e.g.,

runs [3,4,5,6,2,3,4,1,2,1]  --->  [[3,4,5,6],[2,3,4],[1,2],[1]]

A natural solution is the following:

runs [] = []
runs (x:xs) = let (ys, zs) = run x xs
              in (x:ys) : runs zs
  where
    run x [] = ([], [])
    run x (y:ys) = if x <= y
                   then let (us, vs) = run y ys
                        in (y:us, vs)
                   else ([], y:ys)

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?)

Todd Wilson