[GHC] #11815: Data.List: Add a function to get consecutive elements (mapConsecutives)
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature | Status: new request | Priority: low | Milestone: Component: | Version: libraries/base | Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- A recurring pattern is to get a list of all consecutive elements of a list, for further processing. I propose adding the following function to `Data.List` for this: {{{ mapConsecutives :: (a -> a -> b) -> [a] -> [b] mapConsecutives _ [] = [] mapConsecutives f xs = zipWith f xs (tail xs) }}} Since it requires pattern matching, to separate the empty case, it is not practical to inline at each use site. Sidenote: A similar function `mapAdjacent` is available in the `utility- ht` library (with a partial implementation(!)) [1]. I realise that `Data.List` is often imported unqualified and hence additions may cause trouble. I would have raised this on the libraries mailing list first, but the guidelines for proposals pointed me here. [1] http://hackage.haskell.org/package/utility-ht-0.0.11/docs/Data-List- HT.html#v:mapAdjacent -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Fun fact: The definition is equivalent to {{{#!hs mapConsecutives :: (a -> a -> b) -> [a] -> [b] mapConsecutives f xs = zipWith f xs (tail xs) }}} because of lazyness and `zipWith _ [] _ = []`. But it might still not be worth inlining it, as it cannot not fuse with `xs` for various reasons. No strong opinion on this function, but I would not object. Is there a better name that immediatelly gives away what it does? Also, in the interest of smaller building blocks, should we maybe provide {{{#!hs consecutiveElements:: [a] -> [(a,a)] consecutiveElements xs = zip xs (tail xs) }}} instead? Again, better name wanted. It also has a slightly more helpful type signature. Or provide both, similar to `zip` and `zipWith`. How about the names `zipConsecutive` and `zipConsecutiveWith`? By their analogies to `zip` and `zipWith`, the usage should be pretty clear. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by holmisen): Ah, I never thought of the laziness making `tail` safe here. Really good to know. `zipConsecutive` and `zipConsecutiveWith` looks good. Should not be too likely to collide with other names for users who import `Data.List`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by nomeata): * cc: dfeuer (added) Comment: If we indeed provide this function here, we might as well want to invest the effort to provide a well-engineered implementation. You could try to find out if * an explicit recursion function is significantly faster and * if it is possible to write `zipConsecutive` as a good consumer or good producer or both, in terms of list fusion. David Feuer might be interested in thinking about the second point. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by holmisen): Some basic benchmarking using criterion to compare both functions implemented by zip and zipWith versus explicit recursion did not show much difference. Explicit recursion seem to be very slightly faster on my setup (compiling with -O). However, this was my first time using criterion, so I could have made all sorts of silly mistakes. I do not know how to measure the list fusion producer/consumer behavior. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Feel free to push your code somewhere (e.g. a github gist) for review. It might be educating to look at the Core code (`-ddump-simpl`). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
If we indeed provide this function here, we might as well want to invest
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:3 nomeata]: the effort to provide a well-engineered implementation. You could try to find out if
* an explicit recursion function is significantly faster and * if it is possible to write `zipConsecutive` as a good consumer or
good producer or both, in terms of list fusion.
David Feuer might be interested in thinking about the second point.
I thought about something quite similar very recently! The fusion-enabled version would look something like this, with all the usual `RULES` noise added: {{{#!hs zipConsecutiveWith :: (a -> a -> b) -> [a] -> [b] zipConsecutiveWith f xs = build builder where builder c n = foldr go (`seq` n) xs Nothing go x r Nothing = r (Just x) go x r (Just prev) = f prev x `c` r (Just x) }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): For educational porpoises, note that GHC is quite good at recognizing that the recursive call always receives a `Just` value, so it can use a worker- wrapper transformation to avoid all the `Maybe` business. I don't know if the `seq` is strictly necessary here, but times I've left that out of similar forms I've ended up regretting it eventually. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Right, I expected something like this with `Nothing` and `Just`, which made me less hopeful for good performance. Are you sure that GHC is able to w/w the worker here and avoid the Maybes? Maybe with argument constructor specialization... I should just try it out. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by holmisen): Replying to [comment:5 nomeata]:
Feel free to push your code somewhere (e.g. a github gist) for review.
This is what I used: http://lpaste.net/159278 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Thanks. With large lists, `-O2` and `zipConsWith`, there is a significant difference (15% faster). With just `-O`, the difference is smaller (10%), but still there. But the libraries are built with `-O2` anyways. So I’d be in favor of the explicitly recursive variants. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by holmisen): Thank you. I could update the proposal description with an edit explaining that two functions (zipConsecutives and zipConsecutivesWith) be added. Then I am not sure how to proceed. Should I just wait for a while to let this settle or should I make a patch or some other thing? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): I'd like to see some numbers for the fusion-capable version in various contexts. Also, I'm not fully convinced that this particular function is of sufficient general utility to include in `Data.List`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by holmisen): Replying to [comment:12 dfeuer]:
I'd like to see some numbers for the fusion-capable version in various contexts. Also, I'm not fully convinced that this particular function is of sufficient general utility to include in `Data.List`.
I have thought about compiling a list of use cases for this in a blog post or similar. Maybe now I'll actually get around to do that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by holmisen: @@ -24,0 +24,38 @@ + + ---- + + UPDATE FROM DISCUSSION: + + The modified proposal is to add the following two functions: + + {{{ + 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 first would mainly be + for consistency with the other zip functions. + + (Maybe we could abbreviate "Consecutives" into "Consecs".) + + Some use cases that immediately comes to mind: + + {{{ + -- 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) + }}} + + The last one is from a real world case where a polygon (represented as + points) was to be translated to a list of corresponding edges. New description: A recurring pattern is to get a list of all consecutive elements of a list, for further processing. I propose adding the following function to `Data.List` for this: {{{ mapConsecutives :: (a -> a -> b) -> [a] -> [b] mapConsecutives _ [] = [] mapConsecutives f xs = zipWith f xs (tail xs) }}} Since it requires pattern matching, to separate the empty case, it is not practical to inline at each use site. Sidenote: A similar function `mapAdjacent` is available in the `utility- ht` library (with a partial implementation(!)) [1]. I realise that `Data.List` is often imported unqualified and hence additions may cause trouble. I would have raised this on the libraries mailing list first, but the guidelines for proposals pointed me here. [1] http://hackage.haskell.org/package/utility-ht-0.0.11/docs/Data-List- HT.html#v:mapAdjacent ---- UPDATE FROM DISCUSSION: The modified proposal is to add the following two functions: {{{ 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 first would mainly be for consistency with the other zip functions. (Maybe we could abbreviate "Consecutives" into "Consecs".) Some use cases that immediately comes to mind: {{{ -- 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) }}} The last one is from a real world case where a polygon (represented as points) was to be translated to a list of corresponding edges. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Good examples! I think this is ready to be be proposed on the libraries list; as described at https://wiki.haskell.org/Library_submissions#Guide_to_proposers. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by holmisen): Thanks. I'll contact the libraries list. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by thomie): Libraries discussion: * https://mail.haskell.org/pipermail/libraries/2016-April/026899.html * https://mail.haskell.org/pipermail/libraries/2016-May/026994.html -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: (none) Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by gbaz): Should this be closed since the proposal met a negative vote? https://mail.haskell.org/pipermail/libraries/2016-June/027072.html -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11815: Data.List: Add a function to get consecutive elements (mapConsecutives) -------------------------------------+------------------------------------- Reporter: holmisen | Owner: (none) Type: feature request | Status: new Priority: low | Milestone: Component: libraries/base | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by holmisen): I do not know about the process for this, but as the proposer I think there are two ways to move forward; either make another try on the libraries list or closing the ticket. The vote was non conclusive if counting my own vote, but as of now I do not intend to make another go at the libraries list. It would be neat with a name for this function, but with the low interest it might be better to close this ticket so that it does not distract people from other issues. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11815#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC