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

`sum`

using direct recursion:

[…]

A user might expect`sum [1,2,3]`

to be optimised to 6. However, GHC will not inline`sum`

because it is a self-recursive definition and hence a loop-breaker. The compiler is not smart enough to realise that repeatedly inlining`sum`

will 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`

/`filter`

etc. 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.