optimization - Can GHC really never inline map, scanl, foldr, etc.?

Question

I've noticed the GHC manual says "for a self-recursive function, the loop breaker can only be the function itself, so an INLINE pragma is always ignored."

Doesn't this say every application of common recursive functional constructs like map, zip, scan*, fold*, sum, etc. cannot be inlined?

You could always rewrite all these function when you employ them, adding appropriate strictness tags, or maybe employ fancy techniques like the "stream fusion" recommended here.

Yet, doesn't all this dramatically constrain our ability to write code that's simultaneously fast and elegant?

Answer 1

Indeed, GHC cannot at present inline recursive functions. However:

• GHC will still specialise recursive functions. For instance, given

  fac :: (Eq a, Num a) => a -> a
  fac 0 = 1
  fac n = n * fac (n-1)
  
  f :: Int -> Int
  f x = 1 + fac x
  

  GHC will spot that fac is used at type Int -> Int and generate a specialised version of fac for that type, which uses fast integer arithmetic.

  This specialisation happens automatically within a module (e.g. if fac and f are defined in the same module). For cross-module specialisation (e.g. if f and fac are defined in different modules), mark the to-be-specialised function with an INLINABLE pragma:

  {-# INLINABLE fac #-}
  fac :: (Eq a, Num a) => a -> a
  ...
  

• There are manual transformations which make functions nonrecursive. The lowest-power technique is the static argument transformation, which applies to recursive functions with arguments which don't change on recursive calls (eg many higher-order functions such as map, filter, fold*). This transformation turns

  map f []     = []
  map f (x:xs) = f x : map f xs
  

  into

  map f xs0 = go xs0
    where
      go []     = []
      go (x:xs) = f x : go xs
  

  so that a call such as

   g :: [Int] -> [Int]
   g xs = map (2*) xs
  

  will have map inlined and become

   g [] = []
   g (x:xs) = 2*x : g xs
  

  This transformation has been applied to Prelude functions such as foldr and foldl.

• Fusion techniques are also make many functions nonrecursive, and are more powerful than the static argument transformation. The main approach for lists, which is built into the Prelude, is shortcut fusion. The basic approach is to write as many functions as possible as non-recursive functions which use foldr and/or build; then all the recursion is captured in foldr, and there are special RULES for dealing with foldr.

  Taking advantage of this fusion is in principle easy: avoid manual recursion, preferring library functions such as foldr, map, filter, and any functions in this list. In particular, writing code in this style produces code which is "simultaneously fast and elegant".

• Modern libraries such as text and vector use stream fusion behind the scenes. Don Stewart wrote a pair of blog posts (1, 2) demonstrating this in action in the now obsolete library uvector, but the same principles apply to text and vector.

  As with shortcut fusion, taking advantage of stream fusion in text and vector is in principle easy: avoid manual recursion, preferring library functions which have been marked as "subject to fusion".

• There is ongoing work on improving GHC to support inlining of recursive functions. This falls under the general heading of supercompilation, and recent work on this seems to have been led by Max Bolingbroke and Neil Mitchell.