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