[Haskell-cafe] Basic list exercise

[Todd Wilson]

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 at 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 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/20230316/67e2f71c/attachment.html>