This fuses:

[(x, y) | x <- [0 .. 10], y <- [0 .. 10]]

But this does not:

liftA2 (,) [0 .. 10] [0 .. 10]

Because the latter inlines to:

let xs = [0..10]; ys = [0..10] in xs >>= \x -> ys >>= \y -> (x, y)

And GHC is afraid to push the ys binding into the \x -> ... lambda because that might duplicate the work of evaluating [0…10]. Even though in the end fusing everything would be beneficial.

See: https://gitlab.haskell.org/ghc/ghc/-/issues/24663

  • jaror@kbin.socialOP
    1·
    8 months ago

    Stream fusion does work:

    data Stream a = forall s. Stream !(s -> Step s a) !s
data Step s a = Yield a !s | Skip !s | Done

data Tup a b = Tup !a !b

cartesianProduct :: Stream a -> Stream b -> Stream (a, b)
cartesianProduct (Stream step1 s01) (Stream step2 s02) = Stream step' s' where
  s' = Tup s01 s02
  step' (Tup s1 s2) =
    case step1 s1 of
      Yield x s1' ->
        case step2 s2 of
          Yield y s2' -> Yield (x, y) (Tup s1 s2')
          Skip s2' -> Skip (Tup s1 s2')
          Done -> Skip (Tup s1' s02)
      Skip s1' -> Skip (Tup s1' s2)
      Done -> Done

eft :: Int -> Int -> Stream Int
eft x y = Stream step x where
  step s
    | s > y = Done
    | otherwise = Yield s (s + 1)

fooS :: Stream (Int, Int)
fooS = cartesianProduct (eft 0 10) (eft 0 10)

toList :: Stream a -> [a]
toList (Stream step s0) = go s0 where
  go !s =
    case step s of
      Yield x s' -> x : go s'
      Skip s' -> go s'
      Done -> []

foo :: [(Int,Int)]
foo = toList fooS