[Haskell-beginners] list splitting - nice implementation?
tob.brandt at googlemail.com
Sun Nov 18 10:47:49 CET 2012
Here is a possible solution:
split xs = getSnds $ span (uncurry (<)) $ zip xs (tail xs)
where getSnds (as, bs) = (map snd as, map snd bs)
firstPart xs = fst $ split xs
sndPart xs = snd $ split xs
This is a one pass algortihm, it works for infinite lists.
On 18 November 2012 08:45, Emmanuel Touzery <etouzery at gmail.com> wrote:
> i wonder what would be the idiomatic way to achieve that algorithm in
> [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?
> Beginners mailing list
> Beginners at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Beginners