[Haskell-beginners] list splitting - nice implementation?

[Kim-Ee Yeoh]

On Sun, Nov 18, 2012 at 4:47 PM, Tobias Brandt <tob.brandt at googlemail.com>
 wrote:

> split xs = getSnds $ span (uncurry (<)) $ zip xs (tail xs)
>     where getSnds (as, bs) = (map snd as, map snd bs)
>

You could prepend negative infinity to not lose the first element.

-- Kim-Ee


On Sun, Nov 18, 2012 at 4:47 PM, Tobias Brandt <tob.brandt at googlemail.com>wrote:

> 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:
>
>> 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
>>
>>
>
> _______________________________________________
> 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/fe130c89/attachment.htm>