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? (Brent Yorgey)
2. Re: list splitting - nice implementation? (Peter Hall)
3. Re: list splitting - nice implementation? (KC)
----------------------------------------------------------------------
Message: 1
Date: Sun, 18 Nov 2012 10:13:15 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sun, Nov 18, 2012 at 11:53:23AM +0100, Tobias Brandt wrote:
> 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)
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
------------------------------
Message: 2
Date: Sun, 18 Nov 2012 15:13:55 +0000
From: Peter Hall <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: Emmanuel Touzery <[email protected]>
Cc: "[email protected]" <[email protected]>
Message-ID:
<caa6hak7nmsb_dbpgnqpcwg+3vgw6rsutgemgm5xxnmjpg-x...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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 <[email protected]> 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" <[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
>>>
>>>
>>
> _______________________________________________
> 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/91f29918/attachment-0001.htm>
------------------------------
Message: 3
Date: Sun, 18 Nov 2012 11:10:53 -0800
From: KC <[email protected]>
Subject: Re: [Haskell-beginners] list splitting - nice implementation?
To: Emmanuel Touzery <[email protected]>
Cc: "[email protected]" <[email protected]>
Message-ID:
<camlkxyns_dp330hhqj3twmqoisoa0m7dtyo9ed2mijxf_3q...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
For efficiency considerations, look at the "core" code generated.
On Sun, Nov 18, 2012 at 2:06 AM, Emmanuel Touzery <[email protected]> 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" <[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 algorithm, it works for infinite lists.
>>
>> On 18 November 2012 08:45, Emmanuel Touzery <[email protected]> wrote:
>>>
--
--
Regards,
KC
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 53, Issue 24
*****************************************
