search

ndmitchell / extra

Extra Haskell functions
Other
93 stars 37 forks source link

Use GHC's definition of spanEnd? #75

Closed andreasabel closed 3 years ago

andreasabel commented 3 years ago

Hoogling for spanEnd I found your definition and the one in ghc's Util, see https://hackage.haskell.org/package/ghc-8.10.2/docs/src/Util.html#spanEnd

spanEnd :: (a -> Bool) -> [a] -> ([a], [a])
spanEnd p l = go l [] [] l
  where
  go yes _        rev_no [] = (yes, reverse rev_no)
  go yes rev_yes  rev_no (x:xs)
    | p x       = go yes (x : rev_yes) rev_no                  xs
    | otherwise = go xs  []            (x : rev_yes ++ rev_no) xs

This implementation is quite a bit more complicated than its specification spanEnd p l == reverse (span p (reverse l)). This suggests there were good reasons for the convoluted implementation.

So maybe switch to GHC's implementation?!

ndmitchell commented 3 years ago

Good catch! I define my spanEnd on top of breakEnd, but the same approach should apply to breakEnd. A patch would be most welcome.

ndmitchell commented 3 years ago

In fact, GHC's version is pretty dubious.

spanEnd (\x -> traceShow x $ even x) [1,1,1,1,2]

With GHC that prints out 1,1,1,1,2. With extra it prints out 2,1. So GHC applies the predicate vastly more times than necessary. I much prefer the extra version, and would consider over-applying the predicate to be a bug.

andreasabel commented 3 years ago

They seem to want to traverse the list from left-to-right. I do not understand why, though. Since a result can only be delivered when the end of the list is reached, it (naturally) does not work for infinite streams. Thus, it is unclear what the advantage is over bimap reverse . span p . reverse.

One of the many places where stating the programmers' intention in the documentation would have helped...