List fusion: Make traverse et al. good producers
Today, any effectful function that produces a list will not fuse with downstream consumers. So
foo :: Maybe [Int]
foo = fmap (fmap (+1)) . traverse id . fmap Just . fmap (*2) $ [0..100]will materialise two lists: One for the result of traverse and one for foo.
I think we could get rid of the first list by defining a new build variant, buildA:
buildA :: forall f a. Applicative f => (forall b. (f a -> b -> b) -> b -> b) -> f [a]
buildA g = g (liftA2 (:)) (pure [])
{-# INLINE[1] buildM #-}
"foldr/buildA" forall (c :: a -> b -> b) (z :: b) (g :: forall b. (f a -> b -> b) -> b -> b). GHC.Base.foldr c z `fmap` (buildA g) = g (liftA2 c) (pure z)
traverse2 :: Applicative f => (a -> f b) -> [a] -> f [b]
traverse2 f as = buildA $ \fc fz -> GHC.Base.foldr (\a as -> fc (f a) as) fz as
{-# INLINE traverse2 #-}Where traverse2 is basically like map, but built with buildA instead of build. I believe we could even reuse the fusion helper mapFB.
Unfortunately, the new RULE will not fire for the example above, for reasons that are beyond my understanding. There's a warning that an existing rule for foldr shadows it, but shouldn't that also apply for foldr/build? Maybe (probably) fmap is inlined too early? Not sure.