[Haskell-cafe] Basic list exercise

[Todd Wilson]

Interesting. So one consequence of this, if I understand correctly, is that
the aforementioned library implementation
<https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#sort>
of `sort` could actually be improved by rewriting the `ascending` function
there so that it returned a pair, as in my code, rather than had a
"difference-list" functional accumulator argument that is finally applied
in the base case.

--Todd

On Sun, Mar 26, 2023 at 12:53 PM David Feuer <david.feuer at gmail.com> wrote:

> 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/0278fd78/attachment.html>