Would it be a good or bad idea to make dropWhile try to fuse?

David Feuer david.feuer at gmail.com
Fri Jul 25 04:35:58 UTC 2014


As Graham Hutton describes in "A tutorial on the universality and
expressiveness of fold",

dropWhile p = fst . foldr go ([], [])
  where
    go x (ys, xs) = (if p x then ys else x:xs, x:xs)

We can write this for real:

dropWhile :: forall a . (a -> Bool) -> [a] -> [a]
dropWhile p list = build dropWhile'
  where
    dropWhile' :: forall b . (a -> b -> b) -> b -> b
    dropWhile' c n = fst $ foldr go (n, n) list
      where
        go x (ys, xs) = let xs' = x `c` xs in (if p x then ys else xs', xs')

This is generally awful, because it could copy a large portion of the
list with no benefit. However, if it fuses, it will sometimes give
good results. For example, compiling

f m n = foldr (+) 0 $ dropWhile (<m) $ map (+1) [1..n]

yields Core that does not produce a intermediate list. Does anyone
have any thoughts about whether this one is worth pursuing?

David Feuer


More information about the Libraries mailing list