[Haskell-beginners] list splitting - nice implementation?

[Kim-Ee Yeoh]

On Sun, Nov 18, 2012 at 2:45 PM, Emmanuel Touzery <etouzery at gmail.com>
 wrote:
>  i could code this by hand, but i'm trying to use as much as possible
builtin higher-order functions.

Seems to me you've fallen into a false proxy trap [1].

True, experienced Haskellers frequently reuse code. But why do they do that?

>  It is concise alright, but it seems contrived and also in terms of
performance I don't think it's OK (for small lists sure but for big lists?).

More questions to ask:
* What's the best performance big-Oh-wise possible?
* What's firstPart and secondPart, big-Oh-wise?

[1]
http://sethgodin.typepad.com/seths_blog/2012/11/avoiding-the-false-proxy-trap.html


-- Kim-Ee


On Sun, Nov 18, 2012 at 2:45 PM, Emmanuel Touzery <etouzery at gmail.com>wrote:

> Hello,
>
>  i wonder what would be the idiomatic way to achieve that algorithm in
> haskell:
>
> [1,4,56,450,23,46,52] => [1,4,56,450]
> [1,4,56,450,23,46,52] => [23,46,52]
>
>  in other words split the list when one element gets smaller than the
> previous one. Tge rest of the time the list is sorted. There would be only
> two lists, not N. I always need the first or second sublist, I don't need
> both at once. But of course a more complete algorithm handling the N case
> and/or returning both sublists would be good.
>
>  i could code this by hand, but i'm trying to use as much as possible
> builtin higher-order functions. However in this case so far I've only come
> up with this:
>
> import Data.List
>
> isSorted :: Ord a => [a] -> Bool
> isSorted l = (sort l) == l
>
> secondPart :: Ord a => [a] -> [a]
> secondPart l = head $ filter isSorted (tails l)
>
> firstPart :: Ord a => [a] -> [a]
> firstPart l = last $ filter isSorted (inits l)
>
>  It is concise alright, but it seems contrived and also in terms of
> performance I don't think it's OK (for small lists sure but for big lists?).
>
>  Anyway, somehow I think something as simple as this must be doable very
> concisely and with optimal performance using only builtin higher-order
> functions. Any idea?
>
>  Thanks!
>
> Emmanuel
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/e8b702f6/attachment-0001.htm>