OC TIL: wrapping list comprehension in a function can prevent fusion
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.
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
Add comment