[Haskell-beginners] list splitting - nice implementation?
Emmanuel Touzery
etouzery at gmail.com
Sun Nov 18 08:45:44 CET 2012
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/e62ec687/attachment.htm>
More information about the Beginners
mailing list