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?

runs([], []).
runs([X|Xs], [[X|Ys]|Rs]) :-
run(X, Xs, Ys, Zs),
runs(Zs, Rs).

run(_, [], [], []) :- !.
run(X, [Y|Ys], [Y|Us], Vs) :- X =< Y, !, run(Y, Ys, Us, Vs).
run(_, Ys, [], Ys).

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?

Todd Wilson

On Thu, Mar 16, 2023 at 6:38 PM Zemyla <zemyla@gmail.com> wrote:

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.

On Thu, Mar 16, 2023, 20:33 Todd Wilson <twilson@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.