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.