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. list splitting - nice implementation? (Emmanuel Touzery)
2. Re: list splitting - nice implementation? (Emmanuel Touzery)
3. Re: list splitting - nice implementation? (KC)
4. Re: list splitting - nice implementation? (Emmanuel Touzery)
5. Re: list splitting - nice implementation? (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Sun, 18 Nov 2012 08:45:44 +0100
From: Emmanuel Touzery <[email protected]>
Subject: [Haskell-beginners] list splitting - nice implementation?
To: [email protected]
Message-ID:
<CAC42RemjPejcHY9O92Ny_eXkaUMCxbjLAG=czvawypqybut...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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-0001.htm>
------------------------------
Message: 2
Date: Sun, 18 Nov 2012 08:51:11 +0100
From: Emmanuel Touzery <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: [email protected]
Message-ID:
<CAC42Re=a+bv4hjqwig8p6sszzuqg8ttqhy39wdz48_jfvsx...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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 <[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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121118/6c276f11/attachment-0001.htm>
------------------------------
Message: 3
Date: Sun, 18 Nov 2012 01:02:26 -0800
From: KC <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: Emmanuel Touzery <[email protected]>
Cc: [email protected]
Message-ID:
<CAMLKXym=utywuxaxbaav+znyskttfuimfearmesksfc6d5p...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
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 <[email protected]> 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 <[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
>
--
--
Regards,
KC
------------------------------
Message: 4
Date: Sun, 18 Nov 2012 10:08:34 +0100
From: Emmanuel Touzery <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: "[email protected]" <[email protected]>
Message-ID:
<CAC42RenXmiENAmgV3kqDuJ=8nrxo0yuhm7ya0-zabf5s9q+...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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" <[email protected]> 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 <[email protected]>
> 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 <[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
> >
>
>
>
> --
> --
> Regards,
> KC
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121118/80c7ac4d/attachment-0001.htm>
------------------------------
Message: 5
Date: Sun, 18 Nov 2012 16:35:32 +0700
From: Kim-Ee Yeoh <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: Emmanuel Touzery <[email protected]>
Cc: [email protected]
Message-ID:
<CAPY+ZdRoaV=5lkbbbzl+17zecvgyqdragrrnoy8xstgppz3...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Sun, Nov 18, 2012 at 2:45 PM, Emmanuel Touzery <[email protected]>
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 <[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/e8b702f6/attachment.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 53, Issue 22
*****************************************
