[Haskell-cafe] Basic list exercise

[Zemyla]

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/6b0a3806/attachment.html>