[Haskell-cafe] Basic list exercise

[David Feuer]

I don't know prolog, but I believe the answer to your last question is no.
The functions will actually be function closures in this case. There's no
way to leave a (native) Haskell list open to being extended at the end,
except to the extent that lazy evaluation does so. Somewhat separately,
while it would be possible for a Haskell implementation to construct
strict-spined list-like structures with constant stack space using tail
recursion modulo cons, GHC doesn't do that.

On Sun, Mar 26, 2023, 1:59 PM Todd Wilson <twilson at csufresno.edu> wrote:

> 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
>>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20230326/fb540e3b/attachment.html>