[Haskell-beginners] list splitting - nice implementation?

[Peter Hall]

import Control.Applicative

breakup :: Ord a => [a] -> ([a],[a])
breakup [] = ([],[])
breakup xs@(x:_) = unpairs . breakWhenLess . pairs $ x:xs
    where pairs = zip <$> tail <*> id
          unpairs (xs,ys) = (fst <$> xs, fst <$> ys)
          breakWhenLess = break (uncurry (<))

Trick is to duplicate the first element so it doesn't get 'lost' by the
tail zip. Applicatives not strictly necessary, but I like them.

Peter


On 18 November 2012 10:06, Emmanuel Touzery <etouzery at gmail.com> wrote:

> That is EXACTLY the kind of answer i was hoping for!
> Great implementation, I'll be sure to reuse that trick of zipping with the
> tail of the list.. really really good.
>
> I'm relieved it's not trivial (for me) to write since i could not come up
> with it, and happy i understand it :-)
>
> Intuitively it's more expensive than what an imperative language would do
> (new list creations, going several times over the list -zip, spam, map -
> still O(n) though).
>
> If it was in your project you'd use that, or would you use a more
> "straightforward" implementation and you came up with this one just because
> i asked explicitely for such a way?
> On 18 Nov 2012 10:47, "Tobias Brandt" <tob.brandt at googlemail.com> wrote:
>
>> Here is a possible solution:
>>
>> import Data.List
>>
>> 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/91f29918/attachment.htm>