Why aren't composed self-recursive functions with same data structure (same dims) on in and out inlined together with other recursions?

user_2976142 0
Viewed 96

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.

compiler-optimization ghc optimization haskell
1 Answers

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.

user_152075680
Related