[Haskell-beginners] list splitting - nice implementation?
etouzery at gmail.com
Sun Nov 18 10:08:34 CET 2012
Well it's possible to code this by passing over the list only once, the
question is, is it possible consicely using builtin haskell higher order
In my case the list is very short so it's really an academic question.
On 18 Nov 2012 10:02, "KC" <kc1956 at gmail.com> wrote:
> 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>
> > 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,
> > was more interested in the rest.
> > On Sun, Nov 18, 2012 at 8:45 AM, 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
> >> two lists, not N. I always need the first or second sublist, I don't
> >> both at once. But of course a more complete algorithm handling the N
> >> 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
> >> 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
> >> 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Beginners