rolling span and groupBy for lists

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

rolling span and groupBy for lists

Harendra Kumar
Hi,

For a small problem, I was looking for a groupBy like function that groups based on a predicate on successive elements but I could not find one. I wrote these little functions for that purpose:

-- | Like span, but with a predicate that compares two successive elements. The
-- span ends when the two successive elements do not satisfy the predicate.
rollingSpan :: (a -> a -> Bool) -> [a] -> ([a], [a])
rollingSpan _ xs@[] = (xs, xs)
rollingSpan _ xs@[_] = (xs, [])
rollingSpan p (x1:xs@(x2:_))
    | p x1 x2 =
        let (ys, zs) = rollingSpan p xs
        in (x1 : ys, zs)
    | otherwise = ([x1], xs)

-- | Like 'groupBy' but with a predicate that compares two successive elements.
-- A group ends when two successive elements do not satisfy the predicate.
rollingGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
rollingGroupBy _ [] = []
rollingGroupBy cmp xs =
    let (ys, zs) = rollingSpan cmp xs
    in ys : rollingGroupBy cmp zs

Are there any existing functions that serve this purpose or is there any simpler way to achieve such functionality? If not, where is the right place for these, if any. Can they be included in Data.List in base?

Thanks,
Harendra

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: rolling span and groupBy for lists

David Feuer-2
This is the wrong list. You probably meant to email haskell-cafe or perhaps [hidden email].



David Feuer
Well-Typed, LLP

-------- Original message --------
From: Harendra Kumar <[hidden email]>
Date: 2/4/18 10:50 PM (GMT-05:00)
Subject: rolling span and groupBy for lists

Hi,

For a small problem, I was looking for a groupBy like function that groups
based on a predicate on successive elements but I could not find one. I
wrote these little functions for that purpose:

-- | Like span, but with a predicate that compares two successive elements.
The
-- span ends when the two successive elements do not satisfy the predicate.
rollingSpan :: (a -> a -> Bool) -> [a] -> ([a], [a])
rollingSpan _ xs@[] = (xs, xs)
rollingSpan _ xs@[_] = (xs, [])
rollingSpan p (x1:xs@(x2:_))
    | p x1 x2 =
        let (ys, zs) = rollingSpan p xs
        in (x1 : ys, zs)
    | otherwise = ([x1], xs)

-- | Like 'groupBy' but with a predicate that compares two successive
elements.
-- A group ends when two successive elements do not satisfy the predicate.
rollingGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
rollingGroupBy _ [] = []
rollingGroupBy cmp xs =
    let (ys, zs) = rollingSpan cmp xs
    in ys : rollingGroupBy cmp zs

Are there any existing functions that serve this purpose or is there any
simpler way to achieve such functionality? If not, where is the right place
for these, if any. Can they be included in Data.List in base?

Thanks,
Harendra

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: rolling span and groupBy for lists

Harendra Kumar
In reply to this post by Harendra Kumar
I was mainly asking if it makes sense to include these functions in base/Data.List. Since the base package is maintained and ships along with ghc, and the issues are also raised at ghc trac I thought this is the right list. I am copying to [hidden email] as well. 

-harendra

On 5 February 2018 at 09:53, David Feuer <[hidden email]> wrote:
This is the wrong list. You probably meant to email haskell-cafe or perhaps [hidden email].



David Feuer
Well-Typed, LLP

-------- Original message --------
From: Harendra Kumar <[hidden email]>
Date: 2/4/18 10:50 PM (GMT-05:00)
Subject: rolling span and groupBy for lists

Hi,

For a small problem, I was looking for a groupBy like function that groups
based on a predicate on successive elements but I could not find one. I
wrote these little functions for that purpose:

-- | Like span, but with a predicate that compares two successive elements.
The
-- span ends when the two successive elements do not satisfy the predicate.
rollingSpan :: (a -> a -> Bool) -> [a] -> ([a], [a])
rollingSpan _ xs@[] = (xs, xs)
rollingSpan _ xs@[_] = (xs, [])
rollingSpan p (x1:xs@(x2:_))
    | p x1 x2 =
        let (ys, zs) = rollingSpan p xs
        in (x1 : ys, zs)
    | otherwise = ([x1], xs)

-- | Like 'groupBy' but with a predicate that compares two successive
elements.
-- A group ends when two successive elements do not satisfy the predicate.
rollingGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
rollingGroupBy _ [] = []
rollingGroupBy cmp xs =
    let (ys, zs) = rollingSpan cmp xs
    in ys : rollingGroupBy cmp zs

Are there any existing functions that serve this purpose or is there any
simpler way to achieve such functionality? If not, where is the right place
for these, if any. Can they be included in Data.List in base?

Thanks,
Harendra


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: rolling span and groupBy for lists

Evan Laforge
In reply to this post by Harendra Kumar
I have my own list library with a bunch of things like this.  I think
it's what most people do, and some upload them to hackage, e.g.
utility-ht or the split package, or data-ordlist.

Specifically, I think rollingGroupBy is what I call splitWith:

-- | Split @xs@ before places where @f@ matches.
--
-- > split_with (==1) [1,2,1]
-- > --> [[], [1, 2], [1]]
split_with :: (a -> Bool) -> [a] -> NonNull [a]
    -- ^ output is non-null, and the contents are also, except the first one

You can probably find something like this in 'split', or if not, that
might be a good place to contribute it.

I have a bunch of grouping functions too, which I use all the time, so
if there's some kind of general list grouping package then maybe I
could put them there.

On the other hand, this sort of thing is pretty individual, so it
doesn't seem so bad for each person to have their own local library.
That way you know it fits your style.  Ultimately I think that's why
none of the split functions made it into Data.List, every person has a
slightly different idea of what it should be.

On Sun, Feb 4, 2018 at 7:50 PM, Harendra Kumar <[hidden email]> wrote:

> Hi,
>
> For a small problem, I was looking for a groupBy like function that groups
> based on a predicate on successive elements but I could not find one. I
> wrote these little functions for that purpose:
>
> -- | Like span, but with a predicate that compares two successive elements.
> The
> -- span ends when the two successive elements do not satisfy the predicate.
> rollingSpan :: (a -> a -> Bool) -> [a] -> ([a], [a])
> rollingSpan _ xs@[] = (xs, xs)
> rollingSpan _ xs@[_] = (xs, [])
> rollingSpan p (x1:xs@(x2:_))
>     | p x1 x2 =
>         let (ys, zs) = rollingSpan p xs
>         in (x1 : ys, zs)
>     | otherwise = ([x1], xs)
>
> -- | Like 'groupBy' but with a predicate that compares two successive
> elements.
> -- A group ends when two successive elements do not satisfy the predicate.
> rollingGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
> rollingGroupBy _ [] = []
> rollingGroupBy cmp xs =
>     let (ys, zs) = rollingSpan cmp xs
>     in ys : rollingGroupBy cmp zs
>
> Are there any existing functions that serve this purpose or is there any
> simpler way to achieve such functionality? If not, where is the right place
> for these, if any. Can they be included in Data.List in base?
>
> Thanks,
> Harendra
>
> _______________________________________________
> ghc-devs mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: rolling span and groupBy for lists

Harendra Kumar
According to hayoo there seem to be 7 different implementations of this same function. Yours is 8th and mine is 9th and other people may have more not uploaded or maybe the ones that hayoo is not able to find. Does that make a case for including this in some standard place?

-harendra

On 5 February 2018 at 12:22, Evan Laforge <[hidden email]> wrote:
I have my own list library with a bunch of things like this.  I think
it's what most people do, and some upload them to hackage, e.g.
utility-ht or the split package, or data-ordlist.

Specifically, I think rollingGroupBy is what I call splitWith:

-- | Split @xs@ before places where @f@ matches.
--
-- > split_with (==1) [1,2,1]
-- > --> [[], [1, 2], [1]]
split_with :: (a -> Bool) -> [a] -> NonNull [a]
    -- ^ output is non-null, and the contents are also, except the first one

You can probably find something like this in 'split', or if not, that
might be a good place to contribute it.

I have a bunch of grouping functions too, which I use all the time, so
if there's some kind of general list grouping package then maybe I
could put them there.

On the other hand, this sort of thing is pretty individual, so it
doesn't seem so bad for each person to have their own local library.
That way you know it fits your style.  Ultimately I think that's why
none of the split functions made it into Data.List, every person has a
slightly different idea of what it should be.

On Sun, Feb 4, 2018 at 7:50 PM, Harendra Kumar <[hidden email]> wrote:
> Hi,
>
> For a small problem, I was looking for a groupBy like function that groups
> based on a predicate on successive elements but I could not find one. I
> wrote these little functions for that purpose:
>
> -- | Like span, but with a predicate that compares two successive elements.
> The
> -- span ends when the two successive elements do not satisfy the predicate.
> rollingSpan :: (a -> a -> Bool) -> [a] -> ([a], [a])
> rollingSpan _ xs@[] = (xs, xs)
> rollingSpan _ xs@[_] = (xs, [])
> rollingSpan p (x1:xs@(x2:_))
>     | p x1 x2 =
>         let (ys, zs) = rollingSpan p xs
>         in (x1 : ys, zs)
>     | otherwise = ([x1], xs)
>
> -- | Like 'groupBy' but with a predicate that compares two successive
> elements.
> -- A group ends when two successive elements do not satisfy the predicate.
> rollingGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
> rollingGroupBy _ [] = []
> rollingGroupBy cmp xs =
>     let (ys, zs) = rollingSpan cmp xs
>     in ys : rollingGroupBy cmp zs
>
> Are there any existing functions that serve this purpose or is there any
> simpler way to achieve such functionality? If not, where is the right place
> for these, if any. Can they be included in Data.List in base?
>
> Thanks,
> Harendra
>
> _______________________________________________
> ghc-devs mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: rolling span and groupBy for lists

Brandon Allbery
Why do I suddenly catch a whiff of https://xkcd.com/927/ ?

On Mon, Feb 5, 2018 at 1:13 PM, Harendra Kumar <[hidden email]> wrote:
According to hayoo there seem to be 7 different implementations of this same function. Yours is 8th and mine is 9th and other people may have more not uploaded or maybe the ones that hayoo is not able to find. Does that make a case for including this in some standard place?

-harendra

On 5 February 2018 at 12:22, Evan Laforge <[hidden email]> wrote:
I have my own list library with a bunch of things like this.  I think
it's what most people do, and some upload them to hackage, e.g.
utility-ht or the split package, or data-ordlist.

Specifically, I think rollingGroupBy is what I call splitWith:

-- | Split @xs@ before places where @f@ matches.
--
-- > split_with (==1) [1,2,1]
-- > --> [[], [1, 2], [1]]
split_with :: (a -> Bool) -> [a] -> NonNull [a]
    -- ^ output is non-null, and the contents are also, except the first one

You can probably find something like this in 'split', or if not, that
might be a good place to contribute it.

I have a bunch of grouping functions too, which I use all the time, so
if there's some kind of general list grouping package then maybe I
could put them there.

On the other hand, this sort of thing is pretty individual, so it
doesn't seem so bad for each person to have their own local library.
That way you know it fits your style.  Ultimately I think that's why
none of the split functions made it into Data.List, every person has a
slightly different idea of what it should be.

On Sun, Feb 4, 2018 at 7:50 PM, Harendra Kumar <[hidden email]> wrote:
> Hi,
>
> For a small problem, I was looking for a groupBy like function that groups
> based on a predicate on successive elements but I could not find one. I
> wrote these little functions for that purpose:
>
> -- | Like span, but with a predicate that compares two successive elements.
> The
> -- span ends when the two successive elements do not satisfy the predicate.
> rollingSpan :: (a -> a -> Bool) -> [a] -> ([a], [a])
> rollingSpan _ xs@[] = (xs, xs)
> rollingSpan _ xs@[_] = (xs, [])
> rollingSpan p (x1:xs@(x2:_))
>     | p x1 x2 =
>         let (ys, zs) = rollingSpan p xs
>         in (x1 : ys, zs)
>     | otherwise = ([x1], xs)
>
> -- | Like 'groupBy' but with a predicate that compares two successive
> elements.
> -- A group ends when two successive elements do not satisfy the predicate.
> rollingGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
> rollingGroupBy _ [] = []
> rollingGroupBy cmp xs =
>     let (ys, zs) = rollingSpan cmp xs
>     in ys : rollingGroupBy cmp zs
>
> Are there any existing functions that serve this purpose or is there any
> simpler way to achieve such functionality? If not, where is the right place
> for these, if any. Can they be included in Data.List in base?
>
> Thanks,
> Harendra
>
> _______________________________________________
> ghc-devs mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs




--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: rolling span and groupBy for lists

Harendra Kumar
Yes, I did too :-) But there is a key difference in this case, all these definitions are mathematically equivalent with identical semantics instead of being some fuzzy subjective standards.

-harendra

On 5 February 2018 at 23:46, Brandon Allbery <[hidden email]> wrote:
Why do I suddenly catch a whiff of https://xkcd.com/927/ ?

On Mon, Feb 5, 2018 at 1:13 PM, Harendra Kumar <[hidden email]> wrote:
According to hayoo there seem to be 7 different implementations of this same function. Yours is 8th and mine is 9th and other people may have more not uploaded or maybe the ones that hayoo is not able to find. Does that make a case for including this in some standard place?

-harendra

On 5 February 2018 at 12:22, Evan Laforge <[hidden email]> wrote:
I have my own list library with a bunch of things like this.  I think
it's what most people do, and some upload them to hackage, e.g.
utility-ht or the split package, or data-ordlist.

Specifically, I think rollingGroupBy is what I call splitWith:

-- | Split @xs@ before places where @f@ matches.
--
-- > split_with (==1) [1,2,1]
-- > --> [[], [1, 2], [1]]
split_with :: (a -> Bool) -> [a] -> NonNull [a]
    -- ^ output is non-null, and the contents are also, except the first one

You can probably find something like this in 'split', or if not, that
might be a good place to contribute it.

I have a bunch of grouping functions too, which I use all the time, so
if there's some kind of general list grouping package then maybe I
could put them there.

On the other hand, this sort of thing is pretty individual, so it
doesn't seem so bad for each person to have their own local library.
That way you know it fits your style.  Ultimately I think that's why
none of the split functions made it into Data.List, every person has a
slightly different idea of what it should be.

On Sun, Feb 4, 2018 at 7:50 PM, Harendra Kumar <[hidden email]> wrote:
> Hi,
>
> For a small problem, I was looking for a groupBy like function that groups
> based on a predicate on successive elements but I could not find one. I
> wrote these little functions for that purpose:
>
> -- | Like span, but with a predicate that compares two successive elements.
> The
> -- span ends when the two successive elements do not satisfy the predicate.
> rollingSpan :: (a -> a -> Bool) -> [a] -> ([a], [a])
> rollingSpan _ xs@[] = (xs, xs)
> rollingSpan _ xs@[_] = (xs, [])
> rollingSpan p (x1:xs@(x2:_))
>     | p x1 x2 =
>         let (ys, zs) = rollingSpan p xs
>         in (x1 : ys, zs)
>     | otherwise = ([x1], xs)
>
> -- | Like 'groupBy' but with a predicate that compares two successive
> elements.
> -- A group ends when two successive elements do not satisfy the predicate.
> rollingGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
> rollingGroupBy _ [] = []
> rollingGroupBy cmp xs =
>     let (ys, zs) = rollingSpan cmp xs
>     in ys : rollingGroupBy cmp zs
>
> Are there any existing functions that serve this purpose or is there any
> simpler way to achieve such functionality? If not, where is the right place
> for these, if any. Can they be included in Data.List in base?
>
> Thanks,
> Harendra
>
> _______________________________________________
> ghc-devs mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs




--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] rolling span and groupBy for lists

Brandon Allbery
In reply to this post by Evan Laforge
We have two groups of "leaders", with partially opposing goals. This is a disaster looking for an excuse to happen.

On Mon, Feb 5, 2018 at 2:29 PM, Harendra Kumar <[hidden email]> wrote:
On 6 February 2018 at 00:33, Sergiu Ivanov <[hidden email]> wrote:
Thus quoth  Harendra Kumar  on Mon Feb 05 2018 at 18:30 (+0100):
> Yes, Hayoo seems to be giving better results, I found more variants having
> the behavior I want, it seems this variant is quite popular but still not
> in any standard libraries.
>
> Interestingly the problem of too many choices and no standard one that can
> be discovered applies to search engines as well. In this case there are
> only two choices but still it is of the same nature. I knew about hayoo but
> forgot to use it in this case. How much time should one spend on finding a
> trivial function before giving up and making the choice to write their own?
> I wish there was a standard, quick, good quality way of discovering what to
> use.  It seems the Haskell ecosystem DNA encourages more and more
> fragmentation rather than consolidation. I think the community/leaders
> should acknowledge this problem and work on making things better in the
> short/long run.

A Single Liberal Unified Registry of Haskell Packages (SLUPR), an effort
in this direction, has been recently announced:

Unfortunately, in my opinion, SLURP is taking things exactly in the opposite direction. I was talking about the problem of choice above and SLURP is giving even more choices  and therefore encouraging more fragmentation. We should have just one good choice to stop wasting time and energy finding the best choice among millions available. Everyone should focus on making that one choice better rather spending energy in creating their own alternatives. This is where the Haskell ecosystem philosophy differs, it provides many choices in all aspects, it may be good in some cases but not always. SLURP is a technology solution which exactly fits in the same DNA. Technology can help us achieve the tasks that we set out to do but technology cannot motivate and influence us in what we choose to do and therefore ti cannot make the community focus on one goal - that requires real people leadership. If we do not focus on one goal, even with the best technology we may not succeed. Just my 2 cents.

-harendra

 


> -harendra
>
> On 5 February 2018 at 22:02, Sergiu Ivanov <[hidden email]> wrote:
>
>> Hello Harendra,
>>
>> Thus quoth  Harendra Kumar  on Mon Feb 05 2018 at 16:43 (+0100):
>> >
>> > The irony is that theoretically you can find a Haskell package or
>> > implementation of whatever you can imagine but quite often it takes more
>> > time to discover it than writing your own.
>>
>> Sometimes Hayoo! helps me out in such situations:
>>
>>   http://hayoo.fh-wedel.de/?query=groupBy
>>
>> utility-ht shows up.
>>
>> --
>> Sergiu
>>


--
Sergiu


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.



--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs