Skip to content

GitLab

  • Menu
Projects Groups Snippets
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
  • GHC GHC
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,862
    • Issues 4,862
    • List
    • Boards
    • Service Desk
    • Milestones
    • Iterations
  • Merge requests 456
    • Merge requests 456
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Deployments
    • Deployments
    • Releases
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #18949
Closed
Open
Created Nov 13, 2020 by Sebastian Graf@sgraf812Developer

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.

Edited Nov 13, 2020 by Sebastian Graf
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking