In tutorial https://markkarpov.com/tutorial/ghc-optimization-and-fusion.html#fusion-without-rewrite-rules is a code example, which will not be optimized by fusion.

map0 :: (a -> b) -> [a] -> [b]
map0 _ []     = []
map0 f (x:xs) = f x : map0 f xs

foldr0 :: (a -> b -> b) -> b -> [a] -> b
foldr0 _ b []     = b
foldr0 f b (a:as) = foldr0 f (f a b) as

nofusion0 :: [Int] -> Int
nofusion0 = foldr0 ( ) 0 . map0 sqr

sqr :: Int -> Int
sqr x = x * x

My question is: Why isn't function foldr0 ( ) 0 . map0 sqr automatically inlined together into one recursion if the compiler can easily prove, that map0 doesn't change data structure dimension and deduce everything on run from the up of structure to the down of structure? I can't still find out, why this kind of code can't be automatically optimized without rewritting rules.

Do you know any specific reason, why this optimization isn't used please?

Thanks.

CodePudding user response：

I think the most promising approach that could optimize your example is called supercompilation. There is a paper about supercompilation for lazy functional languages: https://www.microsoft.com/en-us/research/publication/supercompilation-by-evaluation/.

In the future work section of the paper the authors state:

The major barriers to the use of supercompilation in practice are code bloat and compilation time.

There has been work on trying to integrate supercompilation into GHC, but it has not yet been successful. I don't know all the details, but there is a very technical GHC wiki page about it: https://gitlab.haskell.org/ghc/ghc/-/wikis/supercompilation.