[Haskell-cafe] Basic list exercise

[Jeff Clites]

> It seems that this solution is constantly building and breaking apart pairs.

At first glance it seems fine. In order to pull a sublist off the front of a list you’ll need to build a new list for that part, so the disassemble/reassemble is necessary there.

You can use an “as pattern” to avoid re-creating `y:ys` in your else clause, but that’s somewhat minor. I don’t see anywhere else where you are pulling something apart and then recreating the same thing.

Regarding the other response, an unboxed pair is just an optimization whereby a pair of values can be returned from a function without actually allocating heap storage, but it’s just reducing memory allocation, nothing conceptually more fancy.

Jeff

> On Mar 16, 2023, at 6:34 PM, 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/a24f39f8/attachment.html>