<div dir="ltr">By "using unboxed pairs", do you mean that Haskell optimizes this so that it is equivalent somehow to the following Prolog version of my program?<div><br></div><div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="monospace">runs([], []).<br>runs([X|Xs], [[X|Ys]|Rs]) :-<br>    run(X, Xs, Ys, Zs),<br>    runs(Zs, Rs).<br><br>run(_, [], [], []) :- !.<br>run(X, [Y|Ys], [Y|Us], Vs) :- X =< Y, !, run(Y, Ys, Us, Vs).<br>run(_, Ys, [], Ys).</font><br></div></blockquote><br></div><div>Here, it is clear that, in the second clause for `runs`, computation is happening on two fronts -- `Ys` and `Rs` -- and we can build the two conses in the return value before we do the calls that fill in the missing parts, so this ends up being a tail recursion. When the computation that produces `Ys` finishes, the computation that produces `Rs` can resume. Maybe this can best be explained functionally using continuations?</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:38 PM Zemyla <<a href="mailto:zemyla@gmail.com">zemyla@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">If you use a case statement instead of a let statement in the recursive case, then GHC will know the pairs are being made and immediately taken apart, and will optimize it to use unboxed pairs internally.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Mar 16, 2023, 20:33 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"><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>
_______________________________________________<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>
</blockquote></div>