<div dir="ltr">Interesting. So one consequence of this, if I understand correctly, is that the aforementioned <a href="https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#sort" target="_blank">library implementation</a> 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.<div><div><br></div><div>--Todd</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Mar 26, 2023 at 12:53 PM David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div>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.</div><div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Sun, Mar 26, 2023, 1:59 PM Todd Wilson <<a href="mailto:twilson@csufresno.edu" target="_blank">twilson@csufresno.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">I want to thank all of those who contributed to this thread. If I can summarize the contributions (feel free to clarify any misrepresentations):<div><ul><li>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?</li><li>The compiler will avoid breaking down and reconstructing pairs on each recursive call, even though that is how it is coded.</li><li>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?<br></li><li>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. </li></ul><div>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?</div></div><div><br></div><div>Todd Wilson</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Mar 16, 2023 at 6:33 PM Todd Wilson <<a href="mailto:twilson@csufresno.edu" rel="noreferrer" target="_blank">twilson@csufresno.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Dear Cafe,</div><div><br></div>Here's a basic exercise in list processing: define a function<div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><font face="monospace">runs :: Ord a => [a] -> [[a]]</font></div></blockquote>that breaks up its input list into a list of increasing "runs"; e.g.,</div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><font face="monospace">runs [3,4,5,6,2,3,4,1,2,1]</font> ---> <font face="monospace">[[3,4,5,6],[2,3,4],[1,2],[1]]</font><br></div></blockquote></div><div>A natural solution is the following:</div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><font face="monospace">runs [] = []<br>runs (x:xs) = let (ys, zs) = run x xs</font></div><div><font face="monospace"> in (x:ys) : runs zs</font></div><div><font face="monospace"> where<br> run x [] = ([], [])<br> run x (y:ys) = if x <= y</font></div><div><font face="monospace"> then let (us, vs) = run y ys</font></div><div><font face="monospace"> in (y:us, vs)</font></div><div><span style="font-family:monospace"> else ([], y:ys)</span></div></blockquote>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?)<br></div><div><br></div><div>Todd Wilson</div></div>
</blockquote></div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div></div>
</blockquote></div>