Proposal: Add functions to get consecutive elements to Data.List
I propose adding two new functions to Data.List: zipConsecutives :: [a] -> [(a,a)] zipConsecutives xs = zip xs (tail xs) zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs) (with possibly more efficient implementations) The Trac feature request is at https://ghc.haskell.org/trac/ghc/ticket/11815 . Why These functions are useful when one wants to process consecutive pairs of elements in a sequence, which is not uncommon. The ticket lists some examples, reiterated here: -- diff consecutive elements: diffs = zipConsecutivesWith (flip (-)) -- determine if list is ascending (similar for descending and strict): isAscending = and . zipConsecutivesWith (<=) -- an old friend of ours: fibs = 1 : 1 : zipConsecutivesWith (+) fibs -- get the edges of a closed path defined by points (ps): edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps) Why add to Data.List (and base) The definition must either use an extra equation for the empty list case: zipConsecutives [] = [] zipConsecutives xs = zip xs (tail xs) which makes it non practical to define inline at each use site. Or one may omit the empty list equation, which is safe (thanks to laziness), but that may not be immediately obvious. (It wasn't to me anyway.) The tail function is generally considered unsafe so it is not desirable to force the user to use it. The proposed functions would offer an alternative. The Data.List module is often imported unqualified, so new identifiers may cause collissions. I do find it rather unlikely that the proposed names would cause such problems, however. Deadline for discussion: 2016-05-31.
On Tue, 12 Apr 2016, Johan Holmquist wrote:
zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs)
I call it mapAdjacent in my utility-ht package: http://hackage.haskell.org/package/utility-ht-0.0.11/docs/Data-List-HT.html#... You could simply import that one.
Yes, mapAdjacent is mentioned in the linked feature request.
But simply importing does not help, because one also need to manage another
dependency in the project then. Adding another dependency is a rather big
deal, so if one only needs a single, simple function from a package one
will have to consider whether to add that dependency or just define the
function in the project's utility module. Also one first had to find out
about the utility-ht library and its definition of mapAdjacent.
I am proposing inclusion into base to make it readily available out of the
box. I think it would fit rather well together with the other zips in
Data.List.
2016-04-12 23:01 GMT+02:00 Henning Thielemann : On Tue, 12 Apr 2016, Johan Holmquist wrote: zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs) I call it mapAdjacent in my utility-ht package: http://hackage.haskell.org/package/utility-ht-0.0.11/docs/Data-List-HT.html#... You could simply import that one.
On Tue, Apr 12, 2016 at 10:45 PM, Johan Holmquist
I am proposing inclusion into base to make it readily available out of the box. I think it would fit rather well together with the other zips in Data.List.
But then once you go there, I have a list library with 7 more zip variants, 7 more group variants, 5 more partition variants, some more spans and breaks and viewR and duplicate dropping and merges and splits and etc. And of course I also think they're all useful and I use them all the time, so surely worth including in Data.List. I suspect just about everyone has a personal library of list utilities, all of which are general purpose and useful to that person. Where to stop? Interestingly I don't have mapAdjacent because I've never needed it, but I have zipNext and zipPrev, which I do use frequently, so there's also quite a bit of bikeshedding potential on the general vs. specific scale. I don't mind keeping a local library of things that adapted for my personal style.
On Wed, 13 Apr 2016, Johan Holmquist wrote:
I am proposing inclusion into base to make it readily available out of the box. I think it would fit rather well together with the other zips in Data.List.
It's only out-of-the-box for a recent GHC. You will exclude any older compiler just because of this simple function. If 'base' would be separate from GHC this would be no issue.
That's OK. Ofcourse it does mean that code written for a base with this
included won't work with an older base and hence older compiler. But things
have been added to base before, so it's not a new situtation.
2016-04-13 8:25 GMT+02:00 Henning Thielemann
On Wed, 13 Apr 2016, Johan Holmquist wrote:
I am proposing inclusion into base to make it readily available out of the
box. I think it would fit rather well together with the other zips in Data.List.
It's only out-of-the-box for a recent GHC. You will exclude any older compiler just because of this simple function.
If 'base' would be separate from GHC this would be no issue.
I am neutral on this proposal. I grepped the Agda source (100kloc) for zip.*tail and get 6 uses that fall into your pattern. However, I am not so sure this warrants a new function, in the end zipConsecutivesWith f xs is not shorter than zipWith f xs (tail xs) unless xs is a long name. ./TypeChecking/Free/Tests.hs:54:strictlyAscending l = and $ zipWith (<) l $ tail l ./TypeChecking/Errors.hs:709: two = zipWith (\a b -> [a,b]) s (tail s) ./Interaction/Highlighting/Precise.hs:225: and (zipWith (<=) (map to $ init rs) (map from $ tail rs)) ./Interaction/Highlighting/Range.hs:52: and (zipWith (<) (map to $ init rs) (map from $ tail rs)) ./Syntax/Position.hs:169: and (zipWith (<) (map iEnd $ init is) (map iStart $ tail is)) ./Utils/List.hs:219:sorted xs = and $ zipWith (<=) xs (tail xs) On 12.04.2016 22:55, Johan Holmquist wrote:
I propose adding two new functions to Data.List:
zipConsecutives :: [a] -> [(a,a)] zipConsecutives xs = zip xs (tail xs)
zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs)
(with possibly more efficient implementations)
The Trac feature request is at https://ghc.haskell.org/trac/ghc/ticket/11815.
Why
These functions are useful when one wants to process consecutive pairs of elements in a sequence, which is not uncommon. The ticket lists some examples, reiterated here:
-- diff consecutive elements: diffs = zipConsecutivesWith (flip (-))
-- determine if list is ascending (similar for descending and strict): isAscending = and . zipConsecutivesWith (<=)
-- an old friend of ours: fibs = 1 : 1 : zipConsecutivesWith (+) fibs
-- get the edges of a closed path defined by points (ps): edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps)
Why add to Data.List (and base)
The definition must either use an extra equation for the empty list case:
zipConsecutives [] = [] zipConsecutives xs = zip xs (tail xs)
which makes it non practical to define inline at each use site. Or one may omit the empty list equation, which is safe (thanks to laziness), but that may not be immediately obvious. (It wasn't to me anyway.) The tail function is generally considered unsafe so it is not desirable to force the user to use it. The proposed functions would offer an alternative.
The Data.List module is often imported unqualified, so new identifiers may cause collissions. I do find it rather unlikely that the proposed names would cause such problems, however.
Deadline for discussion: 2016-05-31.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/
On Wed, 13 Apr 2016, Andreas Abel wrote:
I am neutral on this proposal. I grepped the Agda source (100kloc) for zip.*tail and get 6 uses that fall into your pattern. However, I am not so sure this warrants a new function, in the end
zipConsecutivesWith f xs
is not shorter than
zipWith f xs (tail xs)
unless xs is a long name.
Sometimes mapAdjacent allows partial application, like here:
./TypeChecking/Free/Tests.hs:54:strictlyAscending l = and $ zipWith (<) l $ tail l
and here
./Utils/List.hs:219:sorted xs = and $ zipWith (<=) xs (tail xs)
-1 zip xs (tail xs) is a simple, well-known idiom. If you think there's an education problem, you could document and explain it in the haddock for zip or zipWith. As you note yourself, there is no problem with empty lists. If you are worried about tail, use drop 1 as David suggests. On 04/12/2016 11:55 PM, Johan Holmquist wrote:
I propose adding two new functions to Data.List:
zipConsecutives :: [a] -> [(a,a)] zipConsecutives xs = zip xs (tail xs)
zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs)
(with possibly more efficient implementations)
The Trac feature request is at https://ghc.haskell.org/trac/ghc/ticket/11815.
Why
These functions are useful when one wants to process consecutive pairs of elements in a sequence, which is not uncommon. The ticket lists some examples, reiterated here:
-- diff consecutive elements: diffs = zipConsecutivesWith (flip (-))
-- determine if list is ascending (similar for descending and strict): isAscending = and . zipConsecutivesWith (<=)
-- an old friend of ours: fibs = 1 : 1 : zipConsecutivesWith (+) fibs
-- get the edges of a closed path defined by points (ps): edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps)
Why add to Data.List (and base)
The definition must either use an extra equation for the empty list case:
zipConsecutives [] = [] zipConsecutives xs = zip xs (tail xs)
which makes it non practical to define inline at each use site. Or one may omit the empty list equation, which is safe (thanks to laziness), but that may not be immediately obvious. (It wasn't to me anyway.) The tail function is generally considered unsafe so it is not desirable to force the user to use it. The proposed functions would offer an alternative.
The Data.List module is often imported unqualified, so new identifiers may cause collissions. I do find it rather unlikely that the proposed names would cause such problems, however.
Deadline for discussion: 2016-05-31.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-1. I think these are good functions, but I don't think base is the place
for them. They just don't seem "fundamental" enough. That said, they can be
optimized for list fusion based on this implementation, and even use build
to fuse the other way. No zipWith implementation will do this.
zipWithAdj f xs = foldr go (`seq` []) xs Nothing where
go x r Nothing = r (Just x)
go x r (Just prev) = f prev x : r (Just x)
On Apr 13, 2016 3:38 AM, "Roman Cheplyaka"
-1
zip xs (tail xs) is a simple, well-known idiom. If you think there's an education problem, you could document and explain it in the haddock for zip or zipWith.
As you note yourself, there is no problem with empty lists. If you are worried about tail, use drop 1 as David suggests.
On 04/12/2016 11:55 PM, Johan Holmquist wrote:
I propose adding two new functions to Data.List:
zipConsecutives :: [a] -> [(a,a)] zipConsecutives xs = zip xs (tail xs)
zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs)
(with possibly more efficient implementations)
The Trac feature request is at https://ghc.haskell.org/trac/ghc/ticket/11815.
Why
These functions are useful when one wants to process consecutive pairs of elements in a sequence, which is not uncommon. The ticket lists some examples, reiterated here:
-- diff consecutive elements: diffs = zipConsecutivesWith (flip (-))
-- determine if list is ascending (similar for descending and strict): isAscending = and . zipConsecutivesWith (<=)
-- an old friend of ours: fibs = 1 : 1 : zipConsecutivesWith (+) fibs
-- get the edges of a closed path defined by points (ps): edges ps = zipConsecutivesWith makeEdge (ps ++ take 1 ps)
Why add to Data.List (and base)
The definition must either use an extra equation for the empty list case:
zipConsecutives [] = [] zipConsecutives xs = zip xs (tail xs)
which makes it non practical to define inline at each use site. Or one may omit the empty list equation, which is safe (thanks to laziness), but that may not be immediately obvious. (It wasn't to me anyway.) The tail function is generally considered unsafe so it is not desirable to force the user to use it. The proposed functions would offer an alternative.
The Data.List module is often imported unqualified, so new identifiers may cause collissions. I do find it rather unlikely that the proposed names would cause such problems, however.
Deadline for discussion: 2016-05-31.
_______________________________________________ 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
Hi! I have no say in the matter. Having said that...
-1. I think these are good functions, but I don't think base is the place for them. They just don't seem "fundamental" enough.
I do agree with you on that point, but because in it's `zip <*> tail` form, it does not pass the Fairbairn threshold. But given your optimization (which you won't inline when you need it), I think it does. Cheers, Tobias Florek
On Wed, 13 Apr 2016, David Feuer wrote:
-1. I think these are good functions, but I don't think base is the place for them. They just don't seem "fundamental" enough. That said, they can be optimized for list fusion based on this implementation, and even use build to fuse the other way. No zipWith implementation will do this.
zipWithAdj f xs = foldr go (`seq` []) xs Nothing where go x r Nothing = r (Just x) go x r (Just prev) = f prev x : r (Just x)
Btw. I have also this more general variant: mapAdjacent :: (Traversable f) => (a -> a -> b) -> NonEmpty f a -> f b mapAdjacent f (NonEmpty x xs) = snd $ Trav.mapAccumL (\a0 a1 -> (a1, f a0 a1)) x xs Maybe this is also better for fusion? http://hackage.haskell.org/package/non-empty-0.2.1/docs/Data-NonEmpty.html#v...
It is not strictly more general because it cannot handle empty sequences.
2016-04-13 10:47 GMT+02:00 Henning Thielemann : On Wed, 13 Apr 2016, David Feuer wrote: -1. I think these are good functions, but I don't think base is the place for them. They just don't seem "fundamental"
enough. That said, they can be optimized for list fusion based on this
implementation, and even use build to fuse the
other way. No zipWith implementation will do this. zipWithAdj f xs = foldr go (`seq` []) xs Nothing where
go x r Nothing = r (Just x)
go x r (Just prev) = f prev x : r (Just x) Btw. I have also this more general variant: mapAdjacent :: (Traversable f) => (a -> a -> b) -> NonEmpty f a -> f b
mapAdjacent f (NonEmpty x xs) =
snd $ Trav.mapAccumL (\a0 a1 -> (a1, f a0 a1)) x xs Maybe this is also better for fusion? http://hackage.haskell.org/package/non-empty-0.2.1/docs/Data-NonEmpty.html#v...
_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Hi, Am Dienstag, den 12.04.2016, 22:55 +0200 schrieb Johan Holmquist:
I propose adding two new functions to Data.List:
zipConsecutives :: [a] -> [(a,a)] zipConsecutives xs = zip xs (tail xs)
zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs)
(with possibly more efficient implementations)
I’m +1 on this. The fact that people debate whether tail or drop 1 is the right thing to use here point to the fact that this is less trivial than it looks. When I have to write it, it takes me a moment to think whether it is " "zip xs (tail xs)" or " "zip (tail xs) xs". Also, when _reading_ code, "zip xs (tail xs)" requires more thought than zipConsecutives. Furthermore, the standard idiom "zip xs (tail xs)" refers to its argument multiple times. It is thus not a combinator that you can put into a chain of function applications. Also, for this reason, if you compare lenths, then please compare the lengths of (\xs -> zip xs (tail xs)) with zipConsecutives And finally, an explicit name for zipConsecutives has the potential for list-fusion (see #11815 for some discussion in that direction). Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
On 2016-04-12 22:55, Johan Holmquist wrote:
I propose adding two new functions to Data.List:
zipConsecutives :: [a] -> [(a,a)] zipConsecutives xs = zip xs (tail xs)
zipConsecutivesWith :: (a -> a -> b) -> [a] -> [b] zipConsecutivesWith f xs = zipWith f xs (tail xs)
(with possibly more efficient implementations)
For what it's worth, the function for combining adjacent elements is sometimes called 'pairwise' in Python, maybe based on this list of recipes: https://docs.python.org/2/library/itertools.html#recipes Maybe that's a viable naming alternative? -- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing
Hi, Am Mittwoch, den 13.04.2016, 10:23 +0200 schrieb Frerich Raabe:
For what it's worth, the function for combining adjacent elements is sometimes called 'pairwise' in Python, maybe based on this list of recipes:
https://docs.python.org/2/library/itertools.html#recipes
Maybe that's a viable naming alternative?
thanks for digging that up. It’s worth considering, and has a more pleasant tone to it. OTOH "pairwise" could maybe more likely be thought to mean [(x1,x2),(x3,x4),..] Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
participants (9)
-
Andreas Abel -
David Feuer -
Evan Laforge -
Frerich Raabe -
Henning Thielemann -
Joachim Breitner -
Johan Holmquist -
Roman Cheplyaka -
Tobias Florek