list splitting - nice implementation?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Emmanuel Touzery
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/e62ec687/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Emmanuel Touzery
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>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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/6c276f11/attachment.htm>

KC
Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

KC
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>
> 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
>



--
--
Regards,
KC


Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Emmanuel Touzery
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
functions.

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>
> 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>
> > 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
> >
>
>
>
> --
> --
> Regards,
> KC
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/80c7ac4d/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Kim-Ee Yeoh
Administrator
In reply to this post by Emmanuel Touzery
On Sun, Nov 18, 2012 at 2:45 PM, Emmanuel Touzery <etouzery at gmail.com>
 wrote:
>  i could code this by hand, but i'm trying to use as much as possible
builtin higher-order functions.

Seems to me you've fallen into a false proxy trap [1].

True, experienced Haskellers frequently reuse code. But why do they do that?

>  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?).

More questions to ask:
* What's the best performance big-Oh-wise possible?
* What's firstPart and secondPart, big-Oh-wise?

[1]
http://sethgodin.typepad.com/seths_blog/2012/11/avoiding-the-false-proxy-trap.html


-- Kim-Ee


On Sun, Nov 18, 2012 at 2:45 PM, 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/e8b702f6/attachment-0001.htm>

Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Tobias Brandt
In reply to this post by Emmanuel Touzery
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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/651c68ad/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Emmanuel Touzery
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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/f5dd52c5/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Kim-Ee Yeoh
Administrator
In reply to this post by Tobias Brandt
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>

Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Tobias Brandt
On 18 November 2012 11:33, Kim-Ee Yeoh <ky3 at atamo.com> wrote:

> 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.
>
>

Oops, didn't noticed that, nice catch. I'd rather do the following, as it
works for all types that can be compared with (<), not just for numbers:

split xs = getSnds $ span (uncurry (<)) $ zip xs (tail xs)
    where getSnds (as, bs) = (head xs : map snd as, map snd bs)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121118/4378a91e/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Brent Yorgey-2
On Sun, Nov 18, 2012 at 11:53:23AM +0100, Tobias Brandt wrote:

> On 18 November 2012 11:33, Kim-Ee Yeoh <ky3 at atamo.com> wrote:
>
> > 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.
> >
> >
>
> Oops, didn't noticed that, nice catch. I'd rather do the following, as it
> works for all types that can be compared with (<), not just for numbers:
>
> split xs = getSnds $ span (uncurry (<)) $ zip xs (tail xs)
>     where getSnds (as, bs) = (head xs : map snd as, map snd bs)

ghci> split []
([*** Exception: Prelude.head: empty list

Better add a special case for split [].

Incidentally, this is one splitting pattern (splitting based on a
relation between consecutive elements) that the split package [1] does
NOT cover.  I think I have an idea of how to support it but it would
require rewriting a bunch of the internals of the library.

-Brent

[1] http://hackage.haskell.org/package/split


Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

Peter Hall
In reply to this post by Emmanuel Touzery
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>

KC
Reply | Threaded
Open this post in threaded view
|

list splitting - nice implementation?

KC
In reply to this post by Emmanuel Touzery
For efficiency considerations, look at the "core" code generated.

On Sun, Nov 18, 2012 at 2:06 AM, 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).

See first remark.

>
> 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 algorithm, it works for infinite lists.
>>
>> On 18 November 2012 08:45, Emmanuel Touzery <etouzery at gmail.com> wrote:
>>>


--
--
Regards,
KC