On the Haskell Wiki, the following can be read
Will GHC ever inline recursive definitions with static arguments?
Sometimes people ask if GHC is smart enough to unroll a recursive definition when given a static argument. For example, if we could define
sumusing direct recursion:
[…]
A user might expectsum [1,2,3]to be optimised to 6. However, GHC will not inlinesumbecause it is a self-recursive definition and hence a loop-breaker. The compiler is not smart enough to realise that repeatedly inliningsumwill terminate.
And then it goes on to describe a ‘trick’ whereby the whole list-argument is lifted to the type-level, which ‘works’ iff all the elements in the list are also static, but also completely changes the way the function is called.
A few days ago another idea came to mind: Just simply applying rewrite rules.
Turns out that this works perfectly! While GHC will never inline loop-breakers on its own, it will happily apply your rewrite rules:
sumExample :: Int
sumExample = simpleSum [1,2,3,4,5]
simpleSum :: [Int] -> Int
{-# NOINLINE simpleSum #-}
simpleSum [] = 0
simpleSum (x : xs) = x + simpleSum xs
{-# RULES
"simpleSum/base" simpleSum [] = 0
"simpleSum/recurse" forall x xs. simpleSum (x : xs) = x + simpleSum xs
#-}
Or, another example:
findFirstExample :: Int -> Maybe String
findFirstExample x = findFirst [(10, "a"), (20, "b"), (30, "c")] x
findFirst :: Eq k => [(k, v)] -> k -> Maybe v
{-# NOINLINE findFirst #-}
findFirst [] _ = Nothing
findFirst ((k, v) : xs) needle = if k == needle then Just v else findFirst xs needle
{-# RULES
"findFirst/base" forall x. findFirst [] x = Nothing
"findFirst/recurse" forall k v xs needle. findFirst ((k, v) : xs) needle = if k == needle then Just v else findFirst xs needle
#-}
This results in (-ddump-simpl -dsuppress-all):
sumExample = I# 15#
for sum and
findFirstExample
= \ x_a24A ->
case x_a24A of { I# y_i2yB ->
case y_i2yB of {
__DEFAULT -> Nothing;
10# -> lvl_r2zM;
20# -> lvl1_r2zN;
30# -> lvl2_r2zO
}
}
for findFirst.
After sharing this with a couple of people, @MorrowM pointed out that recently GHC has obtained rewrite rules that turn list literals into calls to build, therefore allowing list literals to take part in list fusion, meaning that as long as you implement something in terms of e.g. foldr or another list fusion participant, there already are rewrite rules like the above in place that do the work for you and you don’t have to add them yourself:
EDIT: GHC has had these rewrite rules for a long while (at least 16 years). Rather, it’s specifically lookup, which findFirst is based on, which only recently started participating in list fusion. Thanks for the errata @MorrowM!
sumExampleFold :: Int
sumExampleFold = foldBasedSum [1,2,3,4,5]
foldBasedSum :: [Int] -> Int
{-# INLINE foldBasedSum #-}
foldBasedSum xs = foldr (+) 0 xs
resp.
findFirstFoldExample :: Int -> Maybe String
findFirstFoldExample x = findFirst [(10, "a"), (20, "b"), (30, "c")] x
findFirstFold :: Eq k => [(k, v)] -> k -> Maybe v
{-# INLINE findFirstFold #-}
findFirstFold xs key = foldr (\(k,v) acc -> if k == key then Just v else acc) Nothing xs
(The core/STG output is identical.)
So there’s a few lessons:
- Specifically if you’re dealing with lists, try to implement your recursive functions using
foldr/map/filteretc. and they might very well already fully inline on static inputs. - For any other recursive function that you expect will regularly be called with static inputs: Just copy the definition of the function as a set of rewrite rules, and GHC will happily inline it for you.
- (Side note: Could GHC theoretically be extended to automatically create rewrite rules like these for loop breakers? Or would that be unsound?)
I imagine that this technique can be very useful in the definition of combinators of eDSLs, as they are often recursive but usually called with static arguments.
!). Maybe a simple rule like the following already suffices:
. Maybe there is a way around that, but I don’t currently see it.
!