[Haskell-beginners] list splitting - nice implementation?
kc1956 at gmail.com
Sun Nov 18 10:02:26 CET 2012
Lists are good if they are short; otherwise, lists are good if you are
only traversing them from head to tail or decapitating them.
You want a more complex data structure.
On Sat, Nov 17, 2012 at 11:51 PM, Emmanuel Touzery <etouzery at gmail.com> wrote:
> well for isSorted, better use the implementation from Data.List.Ordered.
> That part was poor in performance for sure, but it wasn't my main focus, I
> was more interested in the rest.
> On Sun, Nov 18, 2012 at 8:45 AM, Emmanuel Touzery <etouzery at gmail.com>
>> 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
More information about the Beginners