Re: [Haskell-cafe] Basic list exercise

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 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 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.