25 Jul
2014
25 Jul
'14
4:35 a.m.
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 (