[GHC] #9623: Use Data.List.dropWhileEnd
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.8.3 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Easy (less than 1 | Type of failure: hour) | None/Unknown Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- The GHC tree has many instances of `reverse . dropWhile ... . reverse`. As well as being harder to read and work with (searching for those forms led me to discover #9616) this approach is less efficient than `dropWhileEnd`. I think I've found all the places this is used, and I'll submit a patch to fix all the instances except for tests and nofib. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: patch Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Easy (less than 1 Type of failure: | hour) None/Unknown | Blocked By: Test Case: | Related Tickets: Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: new => patch Comment: One use of `reverse . dropWhile isSpace . reverse` turned out to be embedded in what someone suggested correctly was a complete reimplementation of `unwords . words`, so I just used that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by thomie): * status: patch => new * component: Compiler => libraries (other) Comment: So `dropWhileEnd` was not added to base until version 4.5 (ghc 7.4), so to allow compilation with older versions of ghc, it would have to be conditionally imported and defined in the files you changed: {{{#!haskell #if MIN_VERSION_base(4,5,0) import Data.List(dropWhileEnd) #endif }}} {{{#!haskell #if !MIN_VERSION_base(4,5,0) dropWhileEnd :: (a -> Bool) -> [a] -> [a] dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x : xs) [] #endif }}} And most of these patches should go to Github, since that is where those projects are maintained: [http://github.com/haskell/cabal cabal], [http://github.com/haskell/filepath filepath], [http://github.com/haskell/haddock haddock] and [http://github.com/judah/haskeline haskeline]. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:2 thomie]:
So `dropWhileEnd` was not added to base until version 4.5 (ghc 7.4), so to allow compilation with older versions of ghc, it would have to be conditionally imported and defined in the files you changed
I'll get on that. Does GHC <7.4 compile GHC 7.9, or can I skip that for the stuff in the compiler? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by thomie): Last time I tried 7.6 did not even compile 7.9, so I believe you can skip that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by thomie): It turns out [wiki:Repositories win32] also has its [https://github.com/haskell/win32 issue tracker] on Github. The patch for hsc2hs looks good to me, but rdr1.diff needs work. If you upload a new version with the same name, it will be overwritten. I don't think you can delete attachments. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by rwbarton): GHC is supposed to be able to be built with the previous two stable releases, so 7.9/7.10 should be buildable with 7.6 and 7.8. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): There's a separate potential issue I don't think is likely to affect any of these uses: `dropWhileEnd` is defined like this: {{{#!hs dropWhileEnd :: (a -> Bool) -> [a] -> [a] dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x : xs) [] }}} This is (relatively) strict in the elements of the list and (relatively) lazy in its spine. This is the opposite of the `reverse . dropWhile p . reverse` behavior. There should (according to some theory) also be a {{{#!hs dropWhileEndLE :: (a -> Bool) -> [a] -> [a] dropWhileEndLE p = foldr (\x xs -> if null xs && p x then [] else x : xs) [] }}} that's the other way around. We could call such a thing `dropWhileEnd'`, but that naming convention clashes with another pair of things that should exist and don't: {{{#!hs takeWhileEnd :: (a -> Bool) -> [a] -> [a] takeWhileEnd p = fst . foldr go ([], False) where go x (rest, done) | not done && p x = (x:rest, False) | otherwise = (rest, True) takeWhileEnd' p = fst . foldr go ([], False) where go x (rest, done) | p x && not done = (x:rest, False) | otherwise = (rest, True) }}} `takeWhileEnd'` is strict in both the elements and the spine (assuming a strict predicate), while `takeWhileEnd` is only strict in the spine. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Criterion has spoken. `dropWhileEnd isSpace` seems to be much slower in typical cases than even `reverse . dropWhile isSpace . reverse`. Even a faster predicate, `(== ' ')`, gives a (much smaller) disadvantage to `dropWhileEnd`. However, the above `dropWhileEndLE` appears to be faster than the double reverse in all cases. So I'll add it to the utilities module and use that instead. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by refold): Replying to [comment:8 dfeuer]:
However, the above `dropWhileEndLE` appears to be faster than the double reverse in all cases. So I'll add it to the utilities module and use that instead.
Since `dropWhileEndLE` is both faster and has less surprising semantics (spine-strict instead of element-strict), I think that the standard library should be changed to use this version. And we should also add `takeWhileEnd` while we're at it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
Replying to [comment:8 dfeuer]:
However, the above `dropWhileEndLE` appears to be faster than the double reverse in all cases. So I'll add it to the utilities module and use that instead.
Since `dropWhileEndLE` is both faster and has less surprising semantics (spine-strict instead of element-strict), I think that the standard
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:9 refold]: library should be changed to use this version. And we should also add `takeWhileEnd` while we're at it. It seems to be faster in the common case of trimming spaces from fairly short strings. It would be pretty bad for cutting a little bit off the end of a lazily-read file. I would be in favor of adding `dropWhileEndLE` (by some name) to `Data.List`, and perhaps deprecating the name `dropWhileEnd` in favor of something less confusing like `takeUntilLast = dropWhileEnd . not`, but just changing the semantics of an existing function seems generally frowned upon. That said, the semantics of `Data.Text.Lazy.dropWhileEnd`, that someone suggested I check into, are much more confusing to me so far, so there may be a bit of room to wiggle things around. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by refold): Replying to [comment:10 dfeuer]:
It seems to be faster in the common case of trimming spaces from fairly short strings. It would be pretty bad for cutting a little bit off the end of a lazily-read file.
Hmm, I see now. That's because {{{ dropWhileEnd isSpace ("foo\n" ++ undefined) == "foo" ++ undefined }}} but {{{ dropWhileEndLE isSpace ("foo\n" ++ undefined) == undefined }}} so the `LE` version would need to read the whole file in memory. IMO the `LE` version is more practical since you usually do stuff like `return . map (dropWhileEnd isSpace) . lines =<< readFile "foo"` instead of just dropping the end of the file. For reference: the original discussion on the libraries list is [http://www.haskell.org/pipermail/libraries/2011-September/016829.html here]. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
Replying to [comment:10 dfeuer]:
It seems to be faster in the common case of trimming spaces from fairly short strings. It would be pretty bad for cutting a little bit off
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:11 refold]: the end of a lazily-read file.
Hmm, I see now. That's because
{{{ dropWhileEnd isSpace ("foo\n" ++ undefined) == "foo" ++ undefined }}}
but
{{{ dropWhileEndLE isSpace ("foo\n" ++ undefined) == undefined }}}
so the `LE` version would need to read the whole file in memory.
IMO the `LE` version is more practical since you usually do stuff like
`return . map (dropWhileEnd isSpace) . lines =<< readFile "foo"` instead of just dropping the end of the file.
For reference: the original discussion on the libraries list is
[http://www.haskell.org/pipermail/libraries/2011-September/016829.html here]. I see now that Roman Leshchinskiy [http://www.haskell.org/pipermail/libraries/2011-September/016841.html proposed] precisely the definition of what I call `dropWhileEndLE`. It looks like there was a lot of confusion back then about the exact laziness properties of the different proposed definitions, and it appears no one recognized the significance of the order of `&&` operands to the semantics. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd
-------------------------------------+-------------------------------------
Reporter: dfeuer | Owner:
Type: task | Status: new
Priority: normal | Milestone: 7.10.1
Component: libraries | Version: 7.8.3
(other) | Keywords:
Resolution: | Architecture: Unknown/Multiple
Operating System: | Difficulty: Easy (less than 1
Unknown/Multiple | hour)
Type of failure: | Blocked By:
None/Unknown | Related Tickets:
Test Case: |
Blocking: |
Differential Revisions: |
-------------------------------------+-------------------------------------
Comment (by Joachim Breitner
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: closed Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: new => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: closed => new * resolution: fixed => Comment: Reopening due to changeset:d6d5c127b86dc186b25add2843cb83fc12e72a85. David, your `dropWhileEndLE` is not available outside GHC, right? So `GHC.Windows` should not use it? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by nomeata): * owner: => dfeuer -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:15 nomeata]:
Reopening due to changeset:d6d5c127b86dc186b25add2843cb83fc12e72a85. David, your `dropWhileEndLE` is not available outside GHC, right? So `GHC.Windows` should not use it?
Ay, you're right. That one should just use `Data.List.dropWhileEnd` instead. Now I just have to figure out how to modify the commit (ugh). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd
-------------------------------------+-------------------------------------
Reporter: dfeuer | Owner: dfeuer
Type: task | Status: new
Priority: normal | Milestone: 7.10.1
Component: libraries | Version: 7.8.3
(other) | Keywords:
Resolution: | Architecture: Unknown/Multiple
Operating System: | Difficulty: Easy (less than 1
Unknown/Multiple | hour)
Type of failure: | Blocked By:
None/Unknown | Related Tickets:
Test Case: |
Blocking: |
Differential Revisions: |
-------------------------------------+-------------------------------------
Comment (by Joachim Breitner
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: closed Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: new => closed * resolution: => fixed Comment: I amended the patch for you. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: closed Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:19 nomeata]:
I amended the patch for you.
Something seems wrong. The patch you linked to still isn't right for Windows, and people way above my pay grade continue to complain on Phab. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: closed Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nomeata): Even with changeset:eb3533997e33602007a1a1a760a72bfcb4fba3ee/ghc it’s still broken? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9623: Use Data.List.dropWhileEnd -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: closed Priority: normal | Milestone: 7.10.1 Component: libraries | Version: 7.8.3 (other) | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Sorry, I think probably some people hadn't pulled that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9623#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC