[Haskell-cafe] Basic list exercise

[Todd Wilson]

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 at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20230326/1a5b331d/attachment.html>