Proposal reminder: Add functions to get consecutive elements to Data.List
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 <lemming@henning-thielemann.de> Date: 2016-04-13 13:28 GMT+02:00 Subject: Re: Proposal: Add functions to get consecutive elements to Data.List To: Johan Holmquist <holmisen@gmail.com> Cc: Haskell Libraries <libraries@haskell.org> 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.
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" <holmisen@gmail.com> 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 <lemming@henning-thielemann.de> Date: 2016-04-13 13:28 GMT+02:00 Subject: Re: Proposal: Add functions to get consecutive elements to Data.List To: Johan Holmquist <holmisen@gmail.com> Cc: Haskell Libraries <libraries@haskell.org>
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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
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
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 _ _ = []
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 <david.feuer@gmail.com>:
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" <holmisen@gmail.com> 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 <lemming@henning-thielemann.de> Date: 2016-04-13 13:28 GMT+02:00 Subject: Re: Proposal: Add functions to get consecutive elements to Data.List To: Johan Holmquist <holmisen@gmail.com> Cc: Haskell Libraries <libraries@haskell.org>
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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
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 <holmisen@gmail.com> 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 <david.feuer@gmail.com>:
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" <holmisen@gmail.com> 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 <lemming@henning-thielemann.de> Date: 2016-04-13 13:28 GMT+02:00 Subject: Re: Proposal: Add functions to get consecutive elements to Data.List To: Johan Holmquist <holmisen@gmail.com> Cc: Haskell Libraries <libraries@haskell.org>
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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
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" <tanuki@gmail.com> 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 <holmisen@gmail.com> 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 <david.feuer@gmail.com>:
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" <holmisen@gmail.com> 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 <lemming@henning-thielemann.de> Date: 2016-04-13 13:28 GMT+02:00 Subject: Re: Proposal: Add functions to get consecutive elements to Data.List To: Johan Holmquist <holmisen@gmail.com> Cc: Haskell Libraries <libraries@haskell.org>
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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
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,
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 <david.feuer@gmail.com> 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" <tanuki@gmail.com> 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 <holmisen@gmail.com> 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 <david.feuer@gmail.com>:
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" <holmisen@gmail.com> 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 <lemming@henning-thielemann.de> Date: 2016-04-13 13:28 GMT+02:00 Subject: Re: Proposal: Add functions to get consecutive elements to Data.List To: Johan Holmquist <holmisen@gmail.com> Cc: Haskell Libraries <libraries@haskell.org>
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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
On Thu, May 19, 2016 at 2:33 PM, Theodore Lief Gannon <tanuki@gmail.com> 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
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 <winterkoninkje@gmail.com>:
On Thu, May 19, 2016 at 2:33 PM, Theodore Lief Gannon <tanuki@gmail.com> 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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
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. :-)
participants (7)
-
Bardur Arantsson -
David Feuer -
Edward Kmett -
Henning Thielemann -
Johan Holmquist -
Theodore Lief Gannon -
wren romano