Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: list splitting - nice implementation? (Tobias Brandt)
2. Re: list splitting - nice implementation? (Emmanuel Touzery)
3. Re: list splitting - nice implementation? (Kim-Ee Yeoh)
4. Re: list splitting - nice implementation? (Tobias Brandt)
----------------------------------------------------------------------
Message: 1
Date: Sun, 18 Nov 2012 10:47:49 +0100
From: Tobias Brandt <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: Emmanuel Touzery <[email protected]>
Cc: [email protected]
Message-ID:
<CAOOWqipyPbbs=emlyaiqap0bkkhl-q3tfal55xytqmgr4g+...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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 <[email protected]> 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
> [email protected]
> 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-0001.htm>
------------------------------
Message: 2
Date: Sun, 18 Nov 2012 11:06:57 +0100
From: Emmanuel Touzery <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: "[email protected]" <[email protected]>
Message-ID:
<CAC42RenOaEvZf26xmKT7cHeaoRxxKLpv=scamdz_wjbbzzw...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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" <[email protected]> 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 <[email protected]> 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
>> [email protected]
>> 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-0001.htm>
------------------------------
Message: 3
Date: Sun, 18 Nov 2012 17:33:53 +0700
From: Kim-Ee Yeoh <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: Tobias Brandt <[email protected]>
Cc: [email protected]
Message-ID:
<capy+zdqamkunb1404d2aidnha0styoqpsv--lmfe5+hy0lk...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Sun, Nov 18, 2012 at 4:47 PM, Tobias Brandt <[email protected]>
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 <[email protected]>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 <[email protected]> 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
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> 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-0001.htm>
------------------------------
Message: 4
Date: Sun, 18 Nov 2012 11:53:23 +0100
From: Tobias Brandt <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: Kim-Ee Yeoh <[email protected]>
Cc: [email protected]
Message-ID:
<caoowqiqnupctqux-ase+h5ch4k_2kdp96xxkhp3qrey8vx0...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On 18 November 2012 11:33, Kim-Ee Yeoh <[email protected]> wrote:
> On Sun, Nov 18, 2012 at 4:47 PM, Tobias Brandt <[email protected]>
> 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-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 53, Issue 23
*****************************************
