On Sun, Nov 18, 2012 at 2:45 PM, Emmanuel Touzery
i could code this by hand, but i'm trying to use as much as possible builtin higher-order functions.
It is concise alright, but it seems contrived and also in terms of
Seems to me you've fallen into a false proxy trap [1].
True, experienced Haskellers frequently reuse code. But why do they do that?
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-tra...
-- Kim-Ee
On Sun, Nov 18, 2012 at 2:45 PM, Emmanuel Touzery
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@haskell.org http://www.haskell.org/mailman/listinfo/beginners