Proposal reminder: Add functions to get consecutive elements to Data.List

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

Proposal reminder: Add functions to get consecutive elements to Data.List

Johan Holmquist
The discussion period for this proposal is near (31 of May).

So far I count 1 for and 2 against the proposal.

Joachim Breitner made a good enumeration of some advantages of adding these to base. Here is an enumeration of pros:

* Availability in Data.List gives this pattern a common name.

* A common name for this makes code easier to read and decreases the risk of getting the definition wrong.

* The argument won't have to be repeated, hence making it easier to chain the functions.

* List-fusion potential.


Tobias Florek pointed out that `zip <*> tail` can be used to define this inline without the need for repeating the argument and made a reference to the Fairbairn threshold. This is elegant, but I am afraid that people might consider this obscure code golfing if used.

Cheers
Johan Holmquist


---------- Forwarded message ----------
From: Henning Thielemann <[hidden email]>
Date: 2016-04-13 13:28 GMT+02:00
Subject: Re: Proposal: Add functions to get consecutive elements to Data.List
To: Johan Holmquist <[hidden email]>
Cc: Haskell Libraries <[hidden email]>



On Wed, 13 Apr 2016, Johan Holmquist wrote:

It is not strictly more general because it cannot handle empty sequences.

Think of it as if it handles the non-[] case.


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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

David Feuer

You promised a collection of use cases. I seem to have missed it. Could you send the link again?

On May 19, 2016 1:35 AM, "Johan Holmquist" <[hidden email]> wrote:
The discussion period for this proposal is near (31 of May).

So far I count 1 for and 2 against the proposal.

Joachim Breitner made a good enumeration of some advantages of adding these to base. Here is an enumeration of pros:

* Availability in Data.List gives this pattern a common name.

* A common name for this makes code easier to read and decreases the risk of getting the definition wrong.

* The argument won't have to be repeated, hence making it easier to chain the functions.

* List-fusion potential.


Tobias Florek pointed out that `zip <*> tail` can be used to define this inline without the need for repeating the argument and made a reference to the Fairbairn threshold. This is elegant, but I am afraid that people might consider this obscure code golfing if used.

Cheers
Johan Holmquist


---------- Forwarded message ----------
From: Henning Thielemann <[hidden email]>
Date: 2016-04-13 13:28 GMT+02:00
Subject: Re: Proposal: Add functions to get consecutive elements to Data.List
To: Johan Holmquist <[hidden email]>
Cc: Haskell Libraries <[hidden email]>



On Wed, 13 Apr 2016, Johan Holmquist wrote:

It is not strictly more general because it cannot handle empty sequences.

Think of it as if it handles the non-[] case.


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


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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Henning Thielemann

On Thu, 19 May 2016, David Feuer wrote:

> You promised a collection of use cases. I seem to have missed it. Could you send the link again?


I found the following uses in my libraries:

* mapAdjacent subtract
     differences between consecutive elements, inverse of cumulative sum (scanl (+) 0)

* and . mapAdjacent (==)
     check whether all elements in a list are equal

* and . mapAdjacent (<=)
     check whether elements are sorted

* mapAdjacent (/=) . map signum
     find zero crossings

* head . dropWhile (uncurry (/=)) . mapAdjacent (,)
     drop until convergence

* mapAdjacent (\x y -> (snd x, fst y))
     turn list of intervals into list of gaps

* mapAdjacent (,)
     collect state transitions for a Hidden Markov model

* product . mapAdjacent binomial . scanr1 (+)
     compute multinomial coefficient
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Henning Thielemann

On Thu, 19 May 2016, Henning Thielemann wrote:

> On Thu, 19 May 2016, David Feuer wrote:
>
>> You promised a collection of use cases. I seem to have missed it. Could you
>> send the link again?
>
>
> I found the following uses in my libraries:
>
> * mapAdjacent subtract
>    differences between consecutive elements, inverse of cumulative sum
> (scanl (+) 0)
>
> * and . mapAdjacent (==)
>    check whether all elements in a list are equal
>
> * and . mapAdjacent (<=)
>    check whether elements are sorted
>
> * mapAdjacent (/=) . map signum
>    find zero crossings
>
> * head . dropWhile (uncurry (/=)) . mapAdjacent (,)
>    drop until convergence
>
> * mapAdjacent (\x y -> (snd x, fst y))
>    turn list of intervals into list of gaps
>
> * mapAdjacent (,)
>    collect state transitions for a Hidden Markov model
>
> * product . mapAdjacent binomial . scanr1 (+)
>    compute multinomial coefficient


I found another application: Compute the longest duplicated string.
    https://programmingpraxis.com/2010/12/14/longest-duplicated-substring/

import Data.List
import Data.List.HT (mapAdjacent)
import qualified Data.List.Key as K

lds :: Ord a => [a] -> [a]
lds = K.maximum length . mapAdjacent lcp . sort . tails where
     lcp (x:xs) (y:ys) | x == y = x : lcp xs ys
     lcp _      _               = []
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Johan Holmquist
In reply to this post by David Feuer
Also these two were mentioned earlier (using zipConsecutivesWith):

    -- fibonacci:
    fibs = 1 : 1 : zipConsecutivesWith (+) fibs

    -- get the edges of a closed path defined by points (ps):
    edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps)

There are two things to decide:

1. Whether this should indeed be added to base (Data.List)
2. What names we should use in case of inclusion in base

The proposed functions are:

    zipConsecutives :: [a] -> [(a,a)]

and

    zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b]

I would not object to some shorter names, such as zipConsecs, zipConsecsWith etc...

2016-05-19 7:37 GMT+02:00 David Feuer <[hidden email]>:

You promised a collection of use cases. I seem to have missed it. Could you send the link again?

On May 19, 2016 1:35 AM, "Johan Holmquist" <[hidden email]> wrote:
The discussion period for this proposal is near (31 of May).

So far I count 1 for and 2 against the proposal.

Joachim Breitner made a good enumeration of some advantages of adding these to base. Here is an enumeration of pros:

* Availability in Data.List gives this pattern a common name.

* A common name for this makes code easier to read and decreases the risk of getting the definition wrong.

* The argument won't have to be repeated, hence making it easier to chain the functions.

* List-fusion potential.


Tobias Florek pointed out that `zip <*> tail` can be used to define this inline without the need for repeating the argument and made a reference to the Fairbairn threshold. This is elegant, but I am afraid that people might consider this obscure code golfing if used.

Cheers
Johan Holmquist


---------- Forwarded message ----------
From: Henning Thielemann <[hidden email]>
Date: 2016-04-13 13:28 GMT+02:00
Subject: Re: Proposal: Add functions to get consecutive elements to Data.List
To: Johan Holmquist <[hidden email]>
Cc: Haskell Libraries <[hidden email]>



On Wed, 13 Apr 2016, Johan Holmquist wrote:

It is not strictly more general because it cannot handle empty sequences.

Think of it as if it handles the non-[] case.


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



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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Theodore Lief Gannon
Whoops, responded privately (and also made a mistake I wanted to correct, so I guess that works out). To the list this time:

I don't like using the 'zip' terminology here; I feel like that should be reserved for multiple distinct data sources.

Why not 'map2'?

On Thu, May 19, 2016 at 4:32 AM, Johan Holmquist <[hidden email]> wrote:
Also these two were mentioned earlier (using zipConsecutivesWith):

    -- fibonacci:
    fibs = 1 : 1 : zipConsecutivesWith (+) fibs

    -- get the edges of a closed path defined by points (ps):
    edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps)

There are two things to decide:

1. Whether this should indeed be added to base (Data.List)
2. What names we should use in case of inclusion in base

The proposed functions are:

    zipConsecutives :: [a] -> [(a,a)]

and

    zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b]

I would not object to some shorter names, such as zipConsecs, zipConsecsWith etc...

2016-05-19 7:37 GMT+02:00 David Feuer <[hidden email]>:

You promised a collection of use cases. I seem to have missed it. Could you send the link again?

On May 19, 2016 1:35 AM, "Johan Holmquist" <[hidden email]> wrote:
The discussion period for this proposal is near (31 of May).

So far I count 1 for and 2 against the proposal.

Joachim Breitner made a good enumeration of some advantages of adding these to base. Here is an enumeration of pros:

* Availability in Data.List gives this pattern a common name.

* A common name for this makes code easier to read and decreases the risk of getting the definition wrong.

* The argument won't have to be repeated, hence making it easier to chain the functions.

* List-fusion potential.


Tobias Florek pointed out that `zip <*> tail` can be used to define this inline without the need for repeating the argument and made a reference to the Fairbairn threshold. This is elegant, but I am afraid that people might consider this obscure code golfing if used.

Cheers
Johan Holmquist


---------- Forwarded message ----------
From: Henning Thielemann <[hidden email]>
Date: 2016-04-13 13:28 GMT+02:00
Subject: Re: Proposal: Add functions to get consecutive elements to Data.List
To: Johan Holmquist <[hidden email]>
Cc: Haskell Libraries <[hidden email]>



On Wed, 13 Apr 2016, Johan Holmquist wrote:

It is not strictly more general because it cannot handle empty sequences.

Think of it as if it handles the non-[] case.


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



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



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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

David Feuer

I think I like mapPairwise. And I really will try to get a proper list fusion implementation for this if it goes in. The rewrite-back rules are always a bit of a pain.

On May 19, 2016 2:34 PM, "Theodore Lief Gannon" <[hidden email]> wrote:
Whoops, responded privately (and also made a mistake I wanted to correct, so I guess that works out). To the list this time:

I don't like using the 'zip' terminology here; I feel like that should be reserved for multiple distinct data sources.

Why not 'map2'?

On Thu, May 19, 2016 at 4:32 AM, Johan Holmquist <[hidden email]> wrote:
Also these two were mentioned earlier (using zipConsecutivesWith):

    -- fibonacci:
    fibs = 1 : 1 : zipConsecutivesWith (+) fibs

    -- get the edges of a closed path defined by points (ps):
    edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps)

There are two things to decide:

1. Whether this should indeed be added to base (Data.List)
2. What names we should use in case of inclusion in base

The proposed functions are:

    zipConsecutives :: [a] -> [(a,a)]

and

    zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b]

I would not object to some shorter names, such as zipConsecs, zipConsecsWith etc...

2016-05-19 7:37 GMT+02:00 David Feuer <[hidden email]>:

You promised a collection of use cases. I seem to have missed it. Could you send the link again?

On May 19, 2016 1:35 AM, "Johan Holmquist" <[hidden email]> wrote:
The discussion period for this proposal is near (31 of May).

So far I count 1 for and 2 against the proposal.

Joachim Breitner made a good enumeration of some advantages of adding these to base. Here is an enumeration of pros:

* Availability in Data.List gives this pattern a common name.

* A common name for this makes code easier to read and decreases the risk of getting the definition wrong.

* The argument won't have to be repeated, hence making it easier to chain the functions.

* List-fusion potential.


Tobias Florek pointed out that `zip <*> tail` can be used to define this inline without the need for repeating the argument and made a reference to the Fairbairn threshold. This is elegant, but I am afraid that people might consider this obscure code golfing if used.

Cheers
Johan Holmquist


---------- Forwarded message ----------
From: Henning Thielemann <[hidden email]>
Date: 2016-04-13 13:28 GMT+02:00
Subject: Re: Proposal: Add functions to get consecutive elements to Data.List
To: Johan Holmquist <[hidden email]>
Cc: Haskell Libraries <[hidden email]>



On Wed, 13 Apr 2016, Johan Holmquist wrote:

It is not strictly more general because it cannot handle empty sequences.

Think of it as if it handles the non-[] case.


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



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



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


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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Bardur Arantsson-2
In reply to this post by Johan Holmquist
On 05/19/2016 07:27 AM, Johan Holmquist wrote:
> The discussion period for this proposal is near (31 of May).
>

+1.


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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Bardur Arantsson-2
In reply to this post by David Feuer
On 05/19/2016 08:38 PM, David Feuer wrote:
> I think I like mapPairwise. And I really will try to get a proper list
> fusion implementation for this if it goes in. The rewrite-back rules are
> always a bit of a pain.
>

Another name option might be to use "mapAdjacent" or similar. (Though
actually, perhaps "pairwise" is more descriptive.)

Regards,

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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Edward Kmett-2
In reply to this post by David Feuer
I'm personally a weak -1 on adding a mapAdjacent combinator. 

Ultimately

length "mapAdjacent" == length "ap zip tail" 

and there are all the silly nearby functions that sound like they'd want similar names that would use things like:

mapPairwise f (a:b:cs) = f a b:mapPairwise f cs

or

mapPairwise f (a:bcs@(b:cs)) = f a b:mapPairwise f bcs

leading to some confusion, and forcing you to read the docs to figure out what the function does.

-Edward

On Thu, May 19, 2016 at 2:38 PM, David Feuer <[hidden email]> wrote:

I think I like mapPairwise. And I really will try to get a proper list fusion implementation for this if it goes in. The rewrite-back rules are always a bit of a pain.

On May 19, 2016 2:34 PM, "Theodore Lief Gannon" <[hidden email]> wrote:
Whoops, responded privately (and also made a mistake I wanted to correct, so I guess that works out). To the list this time:

I don't like using the 'zip' terminology here; I feel like that should be reserved for multiple distinct data sources.

Why not 'map2'?

On Thu, May 19, 2016 at 4:32 AM, Johan Holmquist <[hidden email]> wrote:
Also these two were mentioned earlier (using zipConsecutivesWith):

    -- fibonacci:
    fibs = 1 : 1 : zipConsecutivesWith (+) fibs

    -- get the edges of a closed path defined by points (ps):
    edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps)

There are two things to decide:

1. Whether this should indeed be added to base (Data.List)
2. What names we should use in case of inclusion in base

The proposed functions are:

    zipConsecutives :: [a] -> [(a,a)]

and

    zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b]

I would not object to some shorter names, such as zipConsecs, zipConsecsWith etc...

2016-05-19 7:37 GMT+02:00 David Feuer <[hidden email]>:

You promised a collection of use cases. I seem to have missed it. Could you send the link again?

On May 19, 2016 1:35 AM, "Johan Holmquist" <[hidden email]> wrote:
The discussion period for this proposal is near (31 of May).

So far I count 1 for and 2 against the proposal.

Joachim Breitner made a good enumeration of some advantages of adding these to base. Here is an enumeration of pros:

* Availability in Data.List gives this pattern a common name.

* A common name for this makes code easier to read and decreases the risk of getting the definition wrong.

* The argument won't have to be repeated, hence making it easier to chain the functions.

* List-fusion potential.


Tobias Florek pointed out that `zip <*> tail` can be used to define this inline without the need for repeating the argument and made a reference to the Fairbairn threshold. This is elegant, but I am afraid that people might consider this obscure code golfing if used.

Cheers
Johan Holmquist


---------- Forwarded message ----------
From: Henning Thielemann <[hidden email]>
Date: 2016-04-13 13:28 GMT+02:00
Subject: Re: Proposal: Add functions to get consecutive elements to Data.List
To: Johan Holmquist <[hidden email]>
Cc: Haskell Libraries <[hidden email]>



On Wed, 13 Apr 2016, Johan Holmquist wrote:

It is not strictly more general because it cannot handle empty sequences.

Think of it as if it handles the non-[] case.


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



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



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


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



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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

wren romano
In reply to this post by Theodore Lief Gannon
On Thu, May 19, 2016 at 2:33 PM, Theodore Lief Gannon <[hidden email]> wrote:
> Whoops, responded privately (and also made a mistake I wanted to correct, so
> I guess that works out). To the list this time:
>
> I don't like using the 'zip' terminology here; I feel like that should be
> reserved for multiple distinct data sources.
>
> Why not 'map2'?

I too dislike the "zip" terminology here, for the same reason. But I
also I mislike "map" since this isn't functorial in any particular way
(I'd expect "map2" to have to do with some sort of 2-functors).

I'm agnostic on adding the function vs not, but If we're bikeshedding
for short names how about "twine"? (The problem I see with "pairwise"
is that it's ambiguous about whether values get "reused": i.e.,
matching even elements to odds[1], vs matching every element to the
next/last.)

[1] I also note without comment that this interpretation is the
inverse to what is traditionally called "zip" in the non-wellfounded
set theory community; e.g., when viewing streams (like the Thue–Morse
sequence) as a greatest solution to a system of equations.

--
Live well,
~wren
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Johan Holmquist
We have now passed the deadline for discussion of this proposal.

The count is 2 for and 3 against. Including myself in the vote would yield a tie on the outcome.

The response was more positive than I had thought it would be, albeit not entirely conclusive. I think it would be fair to put this to rest for now. I guess it will come up again in the future, since the functions are useful enough to warrant a common name IMO.

Many thanks to all for the valuable input.

/Johan


2016-05-20 7:27 GMT+02:00 wren romano <[hidden email]>:
On Thu, May 19, 2016 at 2:33 PM, Theodore Lief Gannon <[hidden email]> wrote:
> Whoops, responded privately (and also made a mistake I wanted to correct, so
> I guess that works out). To the list this time:
>
> I don't like using the 'zip' terminology here; I feel like that should be
> reserved for multiple distinct data sources.
>
> Why not 'map2'?

I too dislike the "zip" terminology here, for the same reason. But I
also I mislike "map" since this isn't functorial in any particular way
(I'd expect "map2" to have to do with some sort of 2-functors).

I'm agnostic on adding the function vs not, but If we're bikeshedding
for short names how about "twine"? (The problem I see with "pairwise"
is that it's ambiguous about whether values get "reused": i.e.,
matching even elements to odds[1], vs matching every element to the
next/last.)

[1] I also note without comment that this interpretation is the
inverse to what is traditionally called "zip" in the non-wellfounded
set theory community; e.g., when viewing streams (like the Thue–Morse
sequence) as a greatest solution to a system of equations.

--
Live well,
~wren
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


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

Re: Proposal reminder: Add functions to get consecutive elements to Data.List

Henning Thielemann

On Wed, 1 Jun 2016, Johan Holmquist wrote:

> The response was more positive than I had thought it would be, albeit not entirely conclusive. I think it would be fair
> to put this to rest for now. I guess it will come up again in the future, since the functions are useful enough to
> warrant a common name IMO.

In the meantime you can just use utility-ht:mapAdjacent. :-)
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries