Use Data.List.dropWhileEnd

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 (closed)) 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.

Trac metadata

Trac field	Value
Version	7.8.3
Type	Task
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed milestone to %7.10.1

changed weight to 5

added Ttask Trac import labels

Attached file rdr1.diff (download).

Sorry; this patch has some unrelated ffi stuff and duplicates the patch for #9616 (closed). I promise I'll learn git soon.

Attached file rdrCabal.diff (download).

Attached file rdrfilepath.diff (download).

Attached file rdrhaddock.diff (download).

Attached file rdrhaskeline.diff (download).

Attached file rdrhsc2hs.diff (download).

Attached file rdrWin23.diff (download).

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.

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:

#if MIN_VERSION_base(4,5,0)
import Data.List(dropWhileEnd)
#endif

#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: cabal, filepath, haddock and haskeline.

Trac metadata

Trac field	Value
Component	Compiler → libraries (other)

Replying to [ticket:9623#comment:88434 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?

Last time I tried 7.6 did not even compile 7.9, so I believe you can skip that.

It turns out win32 also has its 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.

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.

There's a separate potential issue I don't think is likely to affect any of these uses, but actually might: dropWhileEnd is defined like this:

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

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:

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.

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.

Replying to [ticket:9623#comment:88661 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.

Replying to [ticket:9623#comment:88724 refold]:

Replying to [ticket:9623#comment:88661 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.

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.