I want to thank all of those who contributed to this thread. If I can summarize the contributions (feel free to clarify any misrepresentations):

The code I provided for this problem is probably optimal, except perhaps for the small point about using an @-pattern in `run` to avoid reconstructing `y:ys` in the last line -- but isn't this also something the compiler could easily discover and take advantage of without explicit direction?
The compiler will avoid breaking down and reconstructing pairs on each recursive call, even though that is how it is coded.
Although nobody commented on my Prolog version (perhaps because this is a Haskell list!), the point I made there about compiling this as a tail call that doesn't grow the stack should also apply to Haskell (does it?). One thing that's clear from the Prolog code is that it goes down the input list and distributes the elements to one of two places -- the end of the current run or the beginning of a new run -- interspersed with some cons-cell creation. Is that what's happening in Haskell also?
Reference was made to Haskell's `sort` implementation, which essentially finds runs (increasing and decreasing) in the input before repeatedly merging them in pairs until one run remains. Decreasing runs can be turned into increasing ones by using a tail call with a list accumulator, the way iterative reverse works. But increasing runs are handled in the same way that my Prolog code does, essentially by using what appears to be the Haskell equivalent of Prolog's difference-lists: functions whose arguments are the extendible ends of lists.

I'm intrigued by the idea mentioned in this last bullet point. Is this functional equivalent of Prolog's difference lists -- essentially partial data structures that are grown top-down rather than bottom-up, actually efficient? Is there an overhead penalty to be paid for using functions here, or is it compiled away into Prolog-like tail calls that fill in the missing parts of the data structure?

Todd Wilson

On Thu, Mar 16, 2023 at 6:33 PM Todd Wilson <twilson@csufresno.edu> wrote:

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