GHC optimization and fusion

Published on November 22, 2019, last updated August 4, 2026

GHC pragmas
Fusion
Conclusion

The tutorial is my attempt to explain all important GHC optimization ideas in one place. I included some benchmarked examples that should help to demonstrate the techniques in practice.

GHC pragmas

Pragmas are a kind of special hint for the compiler. You should be familiar with the LANGUAGE pragma that enables language extensions in GHC, e.g.:

{-# LANGUAGE OverloadedStrings #-}

The same syntax is used for all GHC pragmas.

We will cover 3 kinds of pragmas:

INLINE and INLINABLE
SPECIALIZE
RULES

Inlining

When a program is compiled, functions become labels—strings associated with positions in machine code. To call a function, its arguments must be put in the appropriate places in memory, on the stack, and in registers. The execution flow then jumps to the address where the function begins. After executing the function body, it is necessary to restore the state of the stack and registers so that they look just like they did before the call. We also need to jump back to continue executing the program. All these manipulations are not free. For a short function they may actually take longer than executing the function body itself.

The idea of inlining is simple: insert the function body directly where we would otherwise have a function call. The functions that are inlined tend to be short, so code duplication is minimal. At the same time we may get a considerable performance boost. Inlining is perhaps the simplest and yet a very efficient way to improve performance in certain cases. Furthermore, we will see shortly that inlining in GHC is not just about eliminating the calls themselves; it’s also a way to enable other optimizations.

How GHC does inlining by itself

When GHC decides whether to inline a particular function, it looks at its size and assigns some sort of weight to that function in a given context. The decision is made on a per-call basis, and a given function may be inlined in one place and called in another. We won’t go into the details of how a function’s weight (or cost) is calculated, but it should make sense that the lighter the function, the keener the compiler is to inline it.

It is worth noting that GHC is careful to avoid excessive code bloat and does not inline blindly. When deciding whether to inline, GHC considers the following:

Does it make sense to inline at a particular call site? Consider this example:
```
map f xs
```
Here, inlining f would produce map (\x -> body) xs, which is not any better than the original, so GHC does not inline it.

The example can be generalized: GHC only inlines functions that are applied to as many arguments as they have syntactically on the left-hand side (LHS) of their definition. This makes sense, because otherwise the body would need to be wrapped in a lambda anyway.

To clarify, let’s steal an example from the GHC user guide:
```
comp1 :: (b -> c) -> (a -> b) -> a -> c
comp1 f g = \x -> f (g x)

comp2 :: (b -> c) -> (a -> b) -> a -> c
comp2 f g x = f (g x)
```
comp1 has only two arguments on its LHS, while comp2 has three, so a call like this
```
map (comp1 not not) xs
```
optimizes better than a similar call with comp2.
How much code duplication would inlining cause? Code bloat is bad, as it increases compilation time and program size and lowers cache hit rates.
How much work duplication would inlining cause? Consider the examples from the paper Secrets of the GHC inliner:
```
let x = foo 1000 in x + x
```
where foo is expensive to compute. Inlining x would result in two calls to foo instead of one.

Let’s see another example:
```
let x = foo 1000
    f = \y -> x * y
in … (f 3) … (f 4)
```
This example shows that work can be duplicated even if x only appears once. If we inline x at its occurrence site, it will be evaluated every time f is called. This is why inlining inside a lambda may not be a good idea.

It is not surprising that GHC is quite conservative about work duplication. However, it makes sense to put up with some duplication of work, because inlining often opens up new transformation opportunities at the inlining site. Avoiding the call itself is not the only (and actually not the main) reason to do inlining. Inlining brings together pieces of code that were previously separate, thus allowing subsequent passes of the optimizer to do more wonderful work.

With this in mind, you shouldn’t be too surprised to learn that the body of an inlineable function (or right-hand side, RHS) is not optimized by GHC. This is an important point that we’ll revisit later. It is left unoptimized so that other machinery can do its work after inlining. For that machinery it is important that the function’s body is intact, because it operates on a rather syntactic level and optimizations, if applied, would leave almost no chance for the machinery to do its work. For now, remember that the bodies of functions that GHC sees as inlineable won’t be optimized; they will be inserted “as is”.

One of the simplest optimization techniques GHC can use with inlining is plain old beta-reduction—the application of functions to their arguments. But this is nothing short of compile-time evaluation of a program, which means that GHC must somehow ensure that it terminates.

This brings us to two edge cases:

Self-recursive functions are never inlined. This should be quite obvious, because if we chose to inline one, we would never finish.
With mutually recursive definitions, GHC selects one or more loop breakers. Loop breakers are just functions that GHC chooses to call (i.e. not inline) to break the loop it would get into if it started to inline everything. For example, if we have a defined via b and b defined via a, we can choose either of them as a loop breaker. GHC tries not to select a function that would be very beneficial to inline (but if it has no choice, it will).

Finally, before we move on to discussing how one can manually control inlining, it’s important to understand a couple of things about how compiled Haskell programs are stored.

As with many other languages that compile to native machine code, after compilation we get .o files, called object files. They contain object code, which is machine code that can be used in an executable but cannot usually be executed on its own. Every module produces an object file of its own. It’s hard to work with object files alone, because they contain information in a not very friendly form—you can execute it, but you cannot reason about it.

To keep additional information about a compiled module, GHC also creates interface files. They contain the version of GHC that was used, the list of modules that the compiled module depends on, the list of things it exports and imports, and other information. Most importantly, interface files contain the bodies of inlineable functions, which can be used for cross-module inlining. This is an important thing to understand: we cannot inline a function if we don’t have its body verbatim. Unless the function’s body is dumped in an interface file, we only have object code, which cannot be used for inlining.

How to control inlining

Let’s discuss how to control inlining explicitly.

`INLINEABLE`

myFunction :: Int -> Int
myFunction = …
{-# INLINEABLE myFunction #-}

The main effect of the INLINEABLE pragma is that GHC will keep in mind that this function may be inlined, even if it would not otherwise consider it for inlining. We don’t get any guarantee about whether the function will be inlined in any particular case, but now the unfolding of the function will be dumped to an interface file, which means that it will be possible to inline it in another module.

With a function marked INLINEABLE, we can use the special built-in function called inline, which tells GHC to try very hard to inline its argument at a particular call site, like this:

foo = bar (inline myFunction) baz

Semantically, inline is just the identity function.

Let’s see an example of INLINEABLE in action. We have a module Goaf (it stands for GHC optimization and fusion) with this:

module Goaf
  ( inlining0 )
where

inlining0 :: Int -> Int
inlining0 0 = 0
inlining0 n = n * n + inlining0 (n - 1)

inlining0 is self-recursive, so GHC will not consider it for inlining, and by default it will not dump its unfolding into the interface file either. If we compile with -O2 (as we will do in every example from now on) and dump the Goaf.hi interface file, we will see no unfolding of the recursive worker’s body (the exact output depends on your GHC version; this is from GHC 9.10):

$ ghc --show-iface Goaf.hi

…

  $winlining0 :: GHC.Prim.Int# -> GHC.Prim.Int#
  [HasNoCafRefs, TagSig: <TagDunno>, LambdaFormInfo: LFReEntrant 1,
   Arity: 1, Strictness: <1L>, Inline: [2]]

  inlining0 :: GHC.Types.Int -> GHC.Types.Int
  [HasNoCafRefs, TagSig: <TagProper>, LambdaFormInfo: LFReEntrant 1,
   Arity: 1, Strictness: <1!P(1L)>, CPR: 1, Inline: [2],
   Unfolding: Core: StableSystem <1,TrueFalse>
              \ (ds :: GHC.Types.Int) ->
              case ds of wild { GHC.Types.I# ww ->
              case $winlining0 ww of ww1 { DEFAULT -> GHC.Types.I# ww1 } }]

…

$winlining0 is a compiled function that works on unboxed integers Int#, and it does the actual recursion. inlining0 itself is a thin wrapper around it that unwraps its Int argument and wraps the result of type Int# back into a normal Int using Int‘s constructor I#. We will not go into a detailed explanation of unboxed data and primitives, but Int# is just your bare-metal, hard-working C int, while Int is our familiar boxed, lazy Haskell Int.

We see two important things here:

The body of the recursive worker $winlining0 is not dumped into the interface file—there is no Unfolding: line for it—which means that other modules have lost the ability to look inside it.
Still, GHC turned inlining0 itself into a small wrapper whose unfolding is dumped (that’s the Unfolding: Core: StableSystem part). The idea is that if inlining0 is called in an arithmetic context with some other operations on Ints, GHC might be able to inline the wrapper and better glue together the things that work on Int#s.

Now let’s use the INLINEABLE pragma:

inlining1 :: Int -> Int
inlining1 0 = 0
inlining1 n = n * n + inlining1 (n - 1)
{-# INLINEABLE inlining1 #-}

which results in:

…

  $winlining1 :: GHC.Prim.Int# -> GHC.Prim.Int#
  [HasNoCafRefs, TagSig: <TagDunno>, LambdaFormInfo: LFReEntrant 1,
   Arity: 1, Strictness: <1L>, Inline: [2],
   Unfolding(loop-breaker): Core: StableUser
                            \ (ww :: GHC.Prim.Int#) ->
                            case ww of ds {
                              DEFAULT
                              -> case $winlining1 (GHC.Prim.-# ds 1#) of ww1 { DEFAULT ->
                                 GHC.Prim.+# (GHC.Prim.*# ds ds) ww1 }
                              0# -> 0# }]

  inlining1 :: GHC.Types.Int -> GHC.Types.Int
  [HasNoCafRefs, TagSig: <TagProper>, LambdaFormInfo: LFReEntrant 1,
   Arity: 1, Strictness: <1!P(1L)>, CPR: 1, Inline: [2],
   Unfolding: Core: StableSystem <1,TrueFalse>
              \ (ds :: GHC.Types.Int) ->
              case ds of wild { GHC.Types.I# ww ->
              case $winlining1 ww of ww1 { DEFAULT -> GHC.Types.I# ww1 } }]

The wrapper looks the same as before, but now the recursive worker $winlining1 has a complete unfolding in our interface file (the Unfolding(loop-breaker): Core: StableUser part). It is unlikely that this will improve performance of a call like this considerably, because our function is rather slow and executed only once:

benchmarking inlining0
time                 5.653 ms   (5.632 ms .. 5.673 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 5.614 ms   (5.601 ms .. 5.627 ms)
std dev              39.86 μs   (33.20 μs .. 48.70 μs)

benchmarking inlining1
time                 5.455 ms   (5.442 ms .. 5.471 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 5.447 ms   (5.432 ms .. 5.458 ms)
std dev              38.08 μs   (28.36 μs .. 58.38 μs)

As expected, INLINEABLE gives only marginal improvement in this case. Its real value is that the worker’s body is now available for cross-module inlining and specialization, as we’ll see shortly.

It turns out that inlining is not the only thing that requires access to the function body to work; some other optimizations do as well. The INLINEABLE pragma effectively removes the module boundaries that could otherwise prevent other optimizations from being applied. We will see how this works with specializing in the next section. Because of this, it is not unusual to see INLINEABLE used on a self-recursive function. The intention is not to inline the function, but to dump its definition into the interface file.

`INLINE` and `NOINLINE`

A more straightforward approach to control inlining is to use the INLINE pragma. When GHC calculates the weight of a function, this pragma makes the function seem very lightweight, to the extent that GHC will always decide to inline it. {-# INLINE myFunction #-} will cause unconditional inlining of myFunction everywhere (except for edge cases, like when myFunction is self-recursive).

Inlining is always an option for the compiler unless you tell it that a particular function should not be inlined. Sometimes you will want to do that. In such cases the NOINLINE pragma may be helpful.

Let’s take an example from the http-client-tls package, which adds TLS support to http-client. The package defines an HTTP Manager that stores information about open connections. The manager is expensive to create, and ideally you should have only one such manager for maximal connection sharing. To make this easier, there is a globalManager :: IORef Manager which you can get and set when you’re in the IO monad. To get the IORef of the global manager, the following code is used:

globalManager :: IORef Manager
globalManager =
  unsafePerformIO (newTlsManager >>= newIORef)
{-# NOINLINE globalManager #-}

unsafePerformIO has the type IO a -> a—it runs effectful IO code while disguising itself as a pure value. Why is this useful? We want an IORef, not an IO IORef, as the latter is just a recipe for getting an IORef pointing to yet another such manager. unsafePerformIO allows us to run the IO action that produces the IORef once and share the result for all future use—this is the treatment that only pure values get. The globalManager value meets the conditions for sharing—it is named and lives at the top level. Yet there is a catch: GHC can just inline globalManager at its call sites, causing re-evaluation. To prevent this, we add the NOINLINE pragma.

Specializing

To understand how specializing works, we first need to review how ad-hoc polymorphism with type classes is implemented in GHC.

When there is a type class constraint in the signature of a function:

foo :: Num a => a -> a
foo = …

This means that the function should work differently for different as. This is accomplished by passing around a dictionary that is indexed by the methods of a given type class. During compilation, the example above turns into:

foo :: Num a -> a -> a
foo d = …

Note the d argument of type Num a. This is a dictionary that contains functions that implement the methods of the Num type class. When a method of that type class needs to be called, the dictionary is indexed by the name of that method and the extracted function is used. Not only does foo accept the dictionary as an additional argument, it also passes it to polymorphic functions inside foo, and those functions may pass it down to functions in their bodies:

foo :: Num a -> a -> a
foo d = … bar d …
  where
    bar, baz :: Num a -> a -> a
    bar d = … baz d …
    baz d = …

Passing and indexing are not free—they make your program slower. At the same time, it is not possible to run a polymorphic function without fixing its types. Given that, it should be possible for GHC to figure out which implementation should be used in each place and speed things up considerably. When we turn a polymorphic function into one specialized for concrete type(s), we are doing specializing.

Syntactically, a SPECIALIZE pragma can be put anywhere its type signature can be put:

foo :: Num a => a -> a
foo = …
{-# SPECIALIZE foo :: Int -> Int #-}

The specialized type may be any type that is less polymorphic than the type of the original function. In other words, the following is valid:

{-# SPECIALIZE f :: <type> #-}

when

f_spec :: <type>
f_spec = f

is valid.

The effect of the pragma is to generate a specialized version of the specified function and a rewrite rule that rewrites calls to the original function into calls to its specialized version whenever the types match.

It is important to understand the relationship between inlining and specializing—both produce specialized code in the end. Inlining is more general but also more wasteful, because it relies on inserting the function body at every call site. The body will be optimized and specialized again and again, leading to longer compilation times and code bloat. With specializing, the compiler generates a number of versions of the function in question with fixed types and uses them when appropriate. If there is no matching specialized version, you’ll get non-specialized, slow code. This is why marking a function as inlineable is sometimes better—you don’t need to guess which types the users of your code will need; you get them all covered.

For a practical example, let’s start with this code:

module Goaf
  ( special0'
  , special0 )
where

special0' :: (Num a, Enum a) => a -> a
special0' x =
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000]

special0 :: Int -> Int
special0 x = special0' x `rem` 10

In the interface file we get (I’ve elided the very long body of the specialized worker):

…

  $w$sspecial0' :: GHC.Prim.Int# -> GHC.Prim.Int#
  [HasNoCafRefs, LambdaFormInfo: LFReEntrant 1, Arity: 1,
   Strictness: <L>, Inline: [2],
   Unfolding: Core: <vanilla>
              \ (ww :: GHC.Prim.Int#) -> … a LOT of code …]

  special0 :: GHC.Types.Int -> GHC.Types.Int
  [HasNoCafRefs, TagSig: <TagProper>, LambdaFormInfo: LFReEntrant 1,
   Arity: 1, Strictness: <1!P(L)>, CPR: 1,
   Unfolding: Core: StableSystem <1,TrueFalse>
              \ (x :: GHC.Types.Int) ->
              case special0_$sspecial0' x of a1 { GHC.Types.I# ipv ->
              GHC.Types.I# (GHC.Prim.remInt# ipv 10#) }]

  special0' ::
    (GHC.Internal.Num.Num a, GHC.Internal.Enum.Enum a) => a -> a
  [HasNoCafRefs, LambdaFormInfo: LFReEntrant 3, Arity: 3,
   Strictness: <SP(SC(S,C(1,L)),A,LC(L,C(1,L)),A,A,A,L)>…]

  special0_$sspecial0' :: GHC.Types.Int -> GHC.Types.Int
  [HasNoCafRefs, TagSig: <TagProper>, LambdaFormInfo: LFReEntrant 1,
   Arity: 1, Strictness: <1!P(L)>, CPR: 1, Inline: [2],
   Unfolding: Core: StableSystem <1,TrueFalse>
              \ (x :: GHC.Types.Int) ->
              case x of wild { GHC.Types.I# ww ->
              case $w$sspecial0' ww of ww1 { DEFAULT -> GHC.Types.I# ww1 } }]

"SPEC special0' @Int" forall ($dNum :: GHC.Internal.Num.Num GHC.Types.Int)
                             ($dEnum :: GHC.Internal.Enum.Enum GHC.Types.Int).
  special0' @GHC.Types.Int $dNum $dEnum = special0_$sspecial0'

GHC is really good at specializing when a polymorphic function is defined and used in the same module. I could not really find a case where GHC would fail to specialize on its own, bravo! The specialized version of special0' is called $w$sspecial0' here, and it works on Int# for maximal speed. Note the "SPEC special0' @Int" rewrite rule at the bottom: it rewrites any call of special0' at type Int into a call of the specialized version.

What else do we see? special0' is compiled, but not dumped into the interface file. This means that if we use it from another module, we should get considerably worse performance compared to special0.

Let’s try:

benchmarking special0
time                 5.457 ms   (5.436 ms .. 5.477 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 5.481 ms   (5.470 ms .. 5.492 ms)
std dev              35.69 μs   (29.94 μs .. 44.88 μs)

benchmarking special0_alt   <---- defined in a separate module
time                 5.462 ms   (5.436 ms .. 5.496 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 5.472 ms   (5.458 ms .. 5.485 ms)
std dev              41.42 μs   (33.29 μs .. 55.02 μs)

What is going on? special0_alt was able to take advantage of the specialized function $w$sspecial0'! But if we remove the export of special0, the situation changes, as special0_alt will no longer be able to find the appropriate specialization:

benchmarking special0_alt
time                 912.0 ms   (866.2 ms .. 947.7 ms)
                     1.000 R²   (NaN R² .. 1.000 R²)
mean                 931.0 ms   (919.8 ms .. 939.9 ms)
std dev              13.88 ms   (0.0 s .. 15.45 ms)

Let’s try to fix the ×167 slowdown by specializing special0' explicitly:

special0' :: (Num a, Enum a) => a -> a
special0' x =
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000] +
  product [x..1000000]
{-# SPECIALIZE special0' :: Int -> Int #-}

This brings our specialization back (GHC labels rules generated from an explicit SPECIALIZE pragma with USPEC, for “user SPEC”):

  special0'_$sspecial0' :: GHC.Types.Int -> GHC.Types.Int
  [HasNoCafRefs, TagSig: <TagProper>, LambdaFormInfo: LFReEntrant 1,
   Arity: 1, Strictness: <1!P(L)>, CPR: 1, Inline: [2],
   Unfolding: Core: StableSystem <1,TrueFalse>
              \ (x :: GHC.Types.Int) ->
              case x of wild { GHC.Types.I# ww ->
              case $w$sspecial0' ww of ww1 { DEFAULT -> GHC.Types.I# ww1 } }]

"USPEC special0' @Int" forall ($dEnum :: GHC.Internal.Enum.Enum GHC.Types.Int)
                              ($dNum :: GHC.Internal.Num.Num GHC.Types.Int).
  special0' @GHC.Types.Int $dNum $dEnum = special0'_$sspecial0'

And special0_alt starts to run fast again:

benchmarking special0_alt
time                 5.392 ms   (5.381 ms .. 5.403 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 5.399 ms   (5.392 ms .. 5.408 ms)
std dev              25.12 μs   (16.60 μs .. 38.90 μs)

To recapitulate:

GHC has no problem specializing for you when a polymorphic function is used in the same module in which it’s defined: it has the body and it knows what to do.
Lack of specialization makes polymorphic functions run very slowly.
If you can guess which specializations to request from GHC when you write your module, prefer SPECIALIZE.
Otherwise, rely on INLINE and INLINEABLE.

Rewrite rules

Haskell, being a pure language, makes it possible to perform a wide range of transformations without changing the meaning of a program. Let’s see how this is done with rewrite rules.

The `RULES` pragma

The RULES pragma allows us to write arbitrary rules for how to transform certain combinations of functions. Here is an example of RULES in use:

{-# RULES
"map/map" forall f g xs. map f (map g xs) = map (f . g) xs
  #-}

There may be zero or more rules in a RULES pragma. You may write each on its own line, or even several on one line, separating them with semicolons.
The closing #-} should start in a column to the right of the opening {-#.
Each rule has a name, enclosed in double quotes. The name itself has no significance; it is only used when GHC needs to refer to the rule in its output.
Each variable mentioned in a rule must either be in scope (e.g. map), or bound by the forall (e.g. f, g, xs). The variables bound by the forall are called pattern variables.
A pattern variable may optionally have a type signature. But if the type of the pattern variable is polymorphic, it must have a type signature. For example:
```
{-# RULES
"fold/build"  forall k z (g :: forall b. (a -> b -> b) -> b -> b).
              foldr k z (build g) = g k z
  #-}
```
Since g has a polymorphic type, it must have a type signature.
The left hand side of a rule must consist of a top-level variable applied to arbitrary expressions. For example, this is not OK:
```
{-# RULES
"wrong1"   forall e1 e2.  case True of { True -> e1; False -> e2 } = e1
"wrong2"   forall f.      f True = True
  #-}
```
In "wrong1", the LHS is not an application; in "wrong2", the LHS has a pattern variable in the head.
A rule does not need to be in the same module as the variables it mentions, though of course they need to be in scope.
All rules are implicitly exported from the module, and are therefore in force in any module that imports the module that defined the rule, directly or indirectly. (That is, if A imports B, which imports C, then C‘s rules are in force when compiling A.) The situation is similar to that with instance declarations.
Inside a rule forall is treated as a keyword, regardless of any other flag settings. Furthermore, inside a rule, the language extension -XScopedTypeVariables is automatically enabled.
Like other pragmas, the RULES pragmas are always checked for scope errors, and are typechecked. Typechecking means that the LHS and RHS of a rule are typechecked, and must have the same type.

The GHC user guide explains what rewrite rules do:

GHC uses a very simple, syntactic, matching algorithm for matching a rule LHS with an expression. It seeks a substitution which makes the LHS and expression syntactically equal modulo alpha-conversion (that is, a rule matches only if types match, too). The pattern (rule), but not the expression, is eta-expanded if necessary. (Eta-expanding the expression can lead to laziness bugs.) But no beta-conversion is performed (that’s called higher-order matching).

This requirement of verbatim matching modulo alpha conversion, combined with the fact that a lot is going on during GHC’s optimization process, makes working with rules a bit tricky. That is, sometimes rules do not fire. Some cases of this are covered in the next section.

On the other hand, when several rules match at once, GHC will pick one arbitrarily to apply. You might be wondering “why not choose, say, the first one?”—well, given that rules are much like instance declarations with respect to how they are imported, there is no order among them. The only thing GHC can do is either apply none or pick one at random and apply that.

Gotchas

Even though GHC tries to apply the rules as it optimizes the program, there are many ways for things to go south. This can make writing rewrite rules a frustrating experience. This section highlights some of the problems you might encounter.

GHC does not attempt to verify whether the RHS has the same meaning as the LHS. It is the responsibility of the programmer to ensure that the rules do not change the meaning of the expressions. An example of a rule that may seem obviously correct is something like this:
```
{-# RULES
"double reverse" forall xs. reverse (reverse xs) = xs
  #-}
```
At first glance it makes sense, doesn’t it? The "double reverse" rule nevertheless does not preserve the meaning of the expression it transforms. reverse (reverse xs) applied to an infinite list would diverge, never yielding any element, while the infinite list xs can be consumed normally, given that it’s never forced in its entirety.
GHC does not attempt to ensure that rules terminate. For example:
```
{-# RULES
"loop" forall x y. f x y = f y x
  #-}
```
will cause the compiler to go into an infinite loop.
Not only must every transformation avoid introducing any difference in meaning, ability to terminate, and so on, but it is also desirable that we get the same result regardless of the order in which we apply the transformations. This property is called confluence.

Here is an example that will hopefully demonstrate what is meant:
```
{-# RULES
"f/f" forall x. f (f x) = f x
"f/g" forall x. f (g x) = fg x
  #-}
```
The "f/f" rule states that f is a kind of idempotent function, while the "f/g" rule recognizes the particular combination of f and g and replaces it with the ad-hoc implementation fg.

Now consider rewriting f . f . g. If we first apply "f/f", then we’ll end up with fg x, but if we first apply "f/g", then we’ll get f . fg. The system is not confluent. An obvious fix would be to add this rule:
```
{-# RULES
"f/fg" forall x. f (fg x) = fg x
  #-}
```
which makes the system confluent. GHC does not attempt to check if your rules are confluent, so take some time to check your rule set for confluence.
Writing rules matching on methods of type classes is futile because methods will be specialized by GHC before rewrite rules have a chance to be applied. Such rules won’t fire because the types of specialized functions won’t match the types specified in the rewrite rules.

While inlining can get in the way of rewrite rules, it can also help glue together different pieces of code. There is a special modifier to the INLINE pragma called CONLIKE that tells GHC “hey, if inlining this any number of times helps some rewrite rules fire, go wild and inline”. CONLIKE stands for “constructor-like”. GHC maintains the invariant that every constructor application has arguments that can be duplicated at no cost: variables, literals, and type applications—hence the name. You can find out more about this in the paper Secrets of the GHC inliner.

The phase control

As you can see, a lot is happening during the optimization passes, and things have the potential to interfere with each other in undesirable ways. There must be a way to say: this should happen first, that should happen after. Well, there is a way.

GHC has the concept of simplifier phases. The phases are numbered and run in decreasing order towards zero. By default (controlled by -fsimplifier-phases, which defaults to 2) the numbered phases are 2, 1, and finally the last phase, which has the number 0. There is also an initial “gentle” phase that runs before the numbered ones, but you cannot attach phase numbers to it, so for our purposes the phases we can talk about are 2, 1, and 0.

Unfortunately, the phase separation does not give fine-grained control, but just enough for us to construct something that works. In an ideal world, we would like to be able to specify which optimization procedure depends on which, but instead we have only two options:

Specify from which phase onward a given rewrite rule or inline/specialize pragma should be enabled.
Specify up to which phase (not including it) a rule should be enabled.

This boils down to adding [n] or [~n] after the pragma’s name:

                         -- Before phase 2     Phase 2 and later
{-# INLINE   [2]  f #-}  --      No                 Yes
{-# INLINE   [~2] f #-}  --      Yes                No
{-# NOINLINE [2]  f #-}  --      No                 Maybe
{-# NOINLINE [~2] f #-}  --      Maybe              No

{-# INLINE   f #-}       --      Yes                Yes
{-# NOINLINE f #-}       --      No                 No

Regarding “maybe”:

By “Maybe” we mean that the usual heuristic inlining rules apply (if the function body is small, or it is applied to interesting-looking arguments etc).

Phase control also works for SPECIALIZE and on a per-rule basis in RULES. Let’s take a look at how it works with the SPECIALIZE pragma:

foo :: Num a => a -> a
foo = …
{-# SPECIALIZE [1] foo :: Int -> Int #-}

⇒

fooForInts :: Int -> Int -- generated by GHC
fooForInts = …
{-# NOINLINE [1] foo #-}
{-# RULES    [1] foo = fooForInts #-}

Here the phase indication for SPECIALIZE has the effect of disabling inlining until it’s time to activate the specializing rule.

As an example of how phase control can be indispensable with rewrite rules, it’s enough to look at the map-specific rules found in the Prelude:

-- Up to (but not including) phase 1, we use the "map" rule to
-- rewrite all saturated applications of map with its build/fold
-- form, hoping for fusion to happen.
-- In phase 1 and 0, we switch off that rule, inline build, and
-- switch on the "mapList" rule, which rewrites the foldr/mapFB
-- thing back into plain map.
--
-- It's important that these two rules aren't both active at once
-- (along with build's unfolding) else we'd get an infinite loop
-- in the rules.  Hence the activation control below.
--
-- The "mapFB" rule optimizes compositions of map.
--
-- This same pattern is followed by many other functions:
-- e.g. append, filter, iterate, repeat, etc.

{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g)
  #-}

Note two important points here:

Without the phase control, both the "map" and "mapList" rules would be active at the same time and GHC would end up in an infinite loop. The phase control is the only way to make this set of rules work.
We first use the "map" rule, and then we use "mapList", which essentially rewrites the function back into its map form. This strategy is called pair rules. The rules try to rewrite a function into a fusion-friendly form, but if by the time we hit phase 1 fusion still has not happened, it’s better to rewrite it back.

It may not be obvious how the result of "map" is going to match the "mapList" rule, but if you keep in mind the definition build g = g (:) [] and the fact that it will most certainly be inlined by phase 1, then "mapList" should make perfect sense.

This brings us to the next major topic of this tutorial…

Fusion

Before we start talking about fusion, we need to define what fusion is. Fusion is a technique that allows us to avoid constructing intermediate results (lists, vectors, arrays…) when chaining operations (functions).

To demonstrate the benefits of fusion, it is enough to start with a simple composition of functions that you may find yourself writing quite often. The only difference is that we will use our own, homemade functions implemented naively:

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

Let’s see how nofusion0 [0..1000000] performs:

benchmarking nofusion0
time                 155.4 ms   (146.4 ms .. 162.4 ms)
                     0.996 R²   (0.980 R² .. 1.000 R²)
mean                 155.1 ms   (151.3 ms .. 159.0 ms)
std dev              5.522 ms   (3.154 ms .. 7.537 ms)

With weigh I’m getting the following:

Case                  Bytes  GCs  Check
nofusion0       249,259,656  448  OK

In a lazy language like Haskell, laziness just changes when parts of the intermediate lists are allocated, but they still must be allocated, because the next step in the pipeline takes them as input. That is the overhead we want to eliminate with fusion.

Can we do better if we rewrite everything as a single function that sums and multiplies in one pass? Let’s give it a try:

manuallyFused :: [Int] -> Int
manuallyFused []     = 0
manuallyFused (x:xs) = x * x + manuallyFused xs

Let’s benchmark it:

benchmarking manuallyFused
time                 17.10 ms   (16.71 ms .. 17.54 ms)
                     0.996 R²   (0.992 R² .. 0.998 R²)
mean                 17.18 ms   (16.87 ms .. 17.62 ms)
std dev              932.8 μs   (673.7 μs .. 1.453 ms)

Case                 Bytes  GCs  Check
manuallyFused   96,646,160  153  OK

The improvement is dramatic. We just manually fused the two functions and produced code that runs faster, consumes less memory, and does the same thing. But should we give up composability and elegance—the main benefits of functional programming?

What we would like to achieve is the following:

Write beautiful, composable programs.
Avoid allocating intermediate results whenever possible.

Point 2 can be, and has been, addressed in different ways:

We can build a vocabulary of primitive operations in such a way that they do not produce results immediately. When the primitives are combined, they produce a function that does not produce results immediately either. To get the final result, we need a function that can run the composite action we have constructed. This is how the repa package works, for example.
We want to have our cake and eat it too. We can expose an interface where every primitive produces a result immediately, but we also add rewrite rules that make GHC rewrite our expressions in such a way that in the end the compiler gets one tight loop without intermediate allocations.

Let’s see the first approach in action.

Fusion without rewrite rules

Returning to the example with map and foldr, we can rewrite the functions differently using the principles we have just discussed. It is essential for fusion that we don’t write our functions as transformations on whole lists, because then we are back to the problem of creating those lists at some point.

In fact, it is not obvious how to have several independent functions that conceptually work on linked lists without recreating the list structure in some form. So we won’t start with fusion that works on linked lists. Instead, let’s start with a more obvious example—arrays.

Fusing arrays

An array can be represented as a combination of its size and a function that takes an index and returns the value at that index. We can write:

data Array a = Array Int (Int -> a)

rangea :: Int -> Array Int
rangea n = Array n id

mapa :: (a -> b) -> Array a -> Array b
mapa f (Array size g) = Array size (f . g)

foldra :: (a -> b -> b) -> b -> Array a -> b
foldra f b (Array size g) = go 0 b
  where
    go n b' | n < size  = go (n + 1) (f (g n) b')
            | otherwise = b'

fuseda :: Int -> Int
fuseda = foldra (+) 0 . mapa sqr . rangea

Here, we have what repa calls delayed arrays:

Note that the function rangea allows us to create arrays whose elements are filled with their indices.
Now, if you take a look at mapa, it doesn’t really do anything other than make the indexing function just a little bit more complex, so we don’t create any intermediate results with it.
foldra allows us to traverse an entire array and get a value computed from all its elements. It plays the role of the consumer in our case.
fuseda 1000000 does the same thing as manuallyFused [0..1000000], but runs much faster.

Of course, fuseda is not equivalent in power to manuallyFused, but it shows that it is possible to have composability and speed at the same time. We get this by just changing the indexing function without actually doing anything with the real array.

Fusing lists

Now let’s try to do something like this for linked lists. We should start with the idea of not touching the real list, but modifying a function that does… what? What should such a function do with a list? If the most basic operation on an array is indexing it by the position of its elements, then what is the most basic operation on a list? How is a linked list consumed?

If we have a list [a], then the way it’s usually consumed is via unconsing. There is a function named uncons in Data.List for that; let’s take a look at it:

uncons :: [a] -> Maybe (a, [a])
uncons []     = Nothing
uncons (a:as) = Just (a, as)

Here we can get the head of a list and its remainder, but if the list is empty, we get nothing. This idea is captured by using Maybe in the type. Let’s try to represent a delayed list as a wrapper around an uncons-like function:

newtype List a = List ([a] -> Maybe (a, [a]))

How about map and foldr? It looks like they follow from that definition rather naturally:

map1 :: (a -> b) -> List a -> List b
map1 g (List f) = List h
  where
    h s' = case f s' of
      Nothing       -> Nothing
      Just (x, s'') -> Just (g x, s'')

This does not type check though:

Couldn’t match type a with b

What’s the problem? Well, remember that we just want to make the inner function more complex. In this particular case, it means that it should consume a list of type [a] and produce a list of type [b], which means that the inner function should have the type [a] -> Maybe (b, [a]) (remember, we produce the elements of [b] one at a time). Clearly, this type signature differs from what we have so far. We should adjust it:

newtype List a b = List ([a] -> Maybe (b, [a]))

The type List a b means: we produce a list of elements of type b from a list of elements of type a. Not a very intuitive type for something like a linked list, but let’s put up with it and see what comes out of it.

Now map1 compiles:

map1 :: (a -> b) -> List s a -> List s b
map1 g (List f) = List h
  where
    h s' = case f s' of
      Nothing       -> Nothing
      Just (x, s'') -> Just (g x, s'')

The signature says: when you have a list with a elements obtained by consuming something of type s, I will give you another list that produces b elements, still consuming the same s.

Let’s implement foldr1 (this is not foldr1 from the Prelude; the numeric suffix just shows which example it belongs to). To implement foldr1 we need something to consume, because we want to get a single value in the end.

We could pass a source of values directly to foldr1, but that’s not nice, for two reasons:

We want the signature of foldr1 to stay as close to the familiar signature of foldr as possible.
foldr is just one primitive that forces a delayed list; what about the other ones? Should we add an extra argument to all of them? This is not elegant.

Perhaps we could store the initial list together with the function we already have, [a] -> Maybe (b, [a]):

data List a b = List ([a] -> Maybe (b, [a])) [a]

We should remember, though, that we want to pass that list unchanged until we want to “force” its consumption:

map1 :: (a -> b) -> List s a -> List s b
map1 g (List f s) = List h s
--             ^           ^
--             |  “as is”  |
--             +-----------+
  where
    h s' = case f s' of
      Nothing       -> Nothing
      Just (x, s'') -> Just (g x, s'')

foldr1 :: (a -> b -> b) -> b -> List s a -> b
foldr1 g b (List f s) = go b s
  where
    go b' s' = case f s' of
      Nothing       -> b'
      Just (x, s'') -> go (g x b') s''

Now that we store the initial list in List itself, we can write a function that converts a normal list to a delayed one:

fromLinkedList :: [a] -> List a a
fromLinkedList = List uncons

And just for the sake of completeness, here is how to get it back:

toLinkedList :: List a b -> [b]
toLinkedList (List f s) = unfoldr f s

unfoldr comes from Data.List:

unfoldr :: (s -> Maybe (a, s)) -> s -> [a]
unfoldr f s = case f s of
  Nothing      -> []
  Just (x, s') -> x : unfoldr f s'

unfoldr takes an initial state, passes it to a given function, and gets back one element of the final list along with a new state. It continues until Nothing is returned.

Finally, we can build fused1 that solves the same problem of summing up a list of squared numbers:

fused1 :: [Int] -> Int
fused1 = foldr1 (+) 0 . map1 sqr . fromLinkedList

Elegance and composability: check. Let’s benchmark it:

benchmarking fused1
time                 3.422 ms   (3.412 ms .. 3.433 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.432 ms   (3.427 ms .. 3.440 ms)
std dev              19.74 μs   (14.15 μs .. 29.65 μs)

Case                 Bytes  GCs  Check
fused1          80,000,016  153  OK

It is the fastest implementation so far! What’s wrong with manuallyFused, though? Shouldn’t it be the fastest? Well, it’s not tail-recursive, but we can rewrite it like this:

manuallyFused' :: [Int] -> Int
manuallyFused' = go 0
  where
    go !n []     = n
    go !n (x:xs) = go (n + x * x) xs

And then it wins:

benchmarking manuallyFused'
time                 3.206 ms   (3.202 ms .. 3.210 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.213 ms   (3.210 ms .. 3.217 ms)
std dev              11.28 μs   (7.599 μs .. 17.46 μs)

Case                  Bytes  GCs  Check
manuallyFused'   80,000,016  153  OK

Returning to List, one thing we would like to do is remove the type of the elements it consumes. That is, if you have a list of a elements, shouldn’t it be a List a? Let’s look at the definition of List again:

data List a b = List ([a] -> Maybe (b, [a])) [a]

[a] here never really changes, in keeping with our idea of not touching it. Its type should be just the same as the type of the argument that its companion function [a] -> Maybe (b, [a]) consumes. We could then hide it using existential quantification:

data List b = forall a. List ([a] -> Maybe (b, [a])) [a]
-- or
data List a = forall s. List (s -> Maybe (a, s)) s

With this we get the following signatures (implementations stay the same):

fromLinkedList :: [a] -> List a
toLinkedList   :: List a -> [a]
map1           :: (a -> b) -> List a -> List b
foldr1         :: (a -> b -> b) -> b -> List a -> b

Much better!

This section has demonstrated that fusion is doable and pleasant without rewrite rules. In the next section we will explore so-called fusion systems.

`build`/`foldr` fusion system

Another approach to avoiding intermediate results can be summarized as follows: we can use functions that operate on normal lists, arrays, vectors, etc., and let GHC rewrite combinations of these functions so that we still get one tight loop in the end.

Here is where rewrite rules come into play. There is one problem with this approach, though—too many functions to account for. The standard vocabulary of a functional programmer includes quite a few list-specific functions: map, filter, (++), foldr, foldl, dropWhile, etc. Let’s say we want to be able to work with 10 functions so that they all play nicely together and get rewritten into high-performance code by GHC. Then we need to account for (at least!) 10 × 10 = 100 combinations of these functions. And remember, we have to verify that every transformation is correct, confluent, and terminating. Do you feel lucky?

Fusion with many different functions is hard. Instead, we would like to do the following:

Rewrite the given function as a combination of a very few selected, general functions that form a fusion system.
Transform these functions and simplify their combinations, often using just one rewrite rule.

In this section we will consider the build/foldr fusion system. It is used in the base package and powers all the list functions we take for granted.

foldr is a familiar function, but what is build? It looks like this:

build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []

The purpose of build is to keep a list in delayed form by abstracting over the (:) operation and the empty list []. The argument of the function is another function that takes a cons-like operation (a -> b -> b) and a nil-like starting point b. The g function produces something of type b. This is a generalization of functions that produce list-like constructions.

build gives (:) to g for consing and [] as the starting point. This way we get our list back. The following example is taken from Duncan Coutts’ thesis, Stream Fusion: Practical shortcut fusion for coinductive sequence types:

build l == [1,2,3]
  where
    l cons nil = 1 `cons` (2 `cons` (3 `cons` nil))

The fusion system with build and foldr has only one rule:

foldr f z (build g) = g f z

How does it help eliminate intermediate lists? Let’s see: build g builds some list, while foldr f z goes through the list “replacing” (:) applications with f and the empty list with z. In fact, this is a popular explanation of what foldr does:

foldr f z [1,2,3] = 1 `f` (2 `f` (3 `f` z))

With that in mind, g is perfectly prepared to receive f and z directly to deliver exactly the same result!

Let’s rewrite our example using the build/foldr fusion system:

map2 :: (a -> b) -> [a] -> [b]
map2 _ []     = []
map2 f (x:xs) = f x : map2 f xs
{-# NOINLINE map2 #-}

{-# RULES
"map2"     [~1] forall f xs. map2 f xs               = build (\c n -> foldr2 (mapFB c f) n xs)
"map2List" [1]  forall f.    foldr2 (mapFB (:) f) [] = map2 f
"mapFB"    forall c f g.     mapFB (mapFB c f) g     = mapFB c (f . g)
  #-}

mapFB :: (b -> l -> l) -> (a -> b) -> a -> l -> l
mapFB c f = \x ys -> c (f x) ys
{-# INLINE [0] mapFB #-}

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

{-# RULES
"build/foldr2" forall f z (g :: forall b. (a -> b -> b) -> b -> b). foldr2 f z (build g) = g f z
  #-}

fused2 :: [Int] -> Int
fused2 = foldr2 (+) 0 . map2 sqr

We need NOINLINE on map2 to silence the warning that "map2" may never fire because map2 may be inlined first. map2 will not be inlined because it is self-recursive, but GHC can’t figure that out (yet).
mapFB is a helper function that takes a consing function c and the function f that we want to apply to the new head of the list. The head of the lambda inside binds the new head of the list x (which f is applied to) and ys, which is the rest of the list. The function’s LHS has only two arguments to facilitate inlining. We want it to be inlined, but only at the end, because some rules match on it and they would be broken if it were inlined too early.
Inlining is essential because it brings together otherwise separate pieces of code and lets GHC manipulate them as a whole.
We are already familiar with the "map2" and "build/foldr2" rewrite rules. "mapFB" is rather trivial. As noted previously, we have here what is called pair rules. The "map2List" rule rewrites back to map2 if by phase 1 fusion did not happen. This is also why we have the normal definition for map2, rather than a build (…) one—if fusion doesn’t happen, the build/foldr implementation actually performs worse.

Let’s see how fused2 performs:

benchmarking fused2
time                 107.5 ms   (103.8 ms .. 110.2 ms)
                     0.998 R²   (0.995 R² .. 1.000 R²)
mean                 107.3 ms   (104.6 ms .. 109.8 ms)
std dev              3.768 ms   (2.519 ms .. 6.098 ms)

Case                  Bytes  GCs  Check
fused2          161,259,568  310  OK

It is better than the version without fusion, but still far from the fastest implementations we have seen. What’s the problem?

Inlining is essential for fusion. Notice that foldr2 is self-recursive, so it will not be inlined, and it will not be rewritten either (unlike map2). Let’s make it non-recursive and inlineable:

foldr2 :: (a -> b -> b) -> b -> [a] -> b
foldr2 f z = go
  where
    go []     = z
    go (y:ys) = y `f` go ys
{-# INLINE [0] foldr2 #-}

We specify phase 0 because we want GHC to inline it, but only after fusion has happened (remember that if we inlined it too early, it would break our fusion rules and they wouldn’t fire).

Let’s give it another shot:

benchmarking fused2
time                 17.87 ms   (17.48 ms .. 18.33 ms)
                     0.996 R²   (0.992 R² .. 0.998 R²)
mean                 17.94 ms   (17.61 ms .. 18.42 ms)
std dev              962.6 μs   (689.0 μs .. 1.401 ms)

Case                  Bytes  GCs  Check
fused2           96,646,160  153  OK

In fact, this is the same result we would get if we used map and foldr directly from the base package.

Indeed, most functions can be rewritten via foldr and build. Most, but not all. In particular, foldl and zip cannot be fused efficiently when written via build and foldr. Unfortunately, we don’t have the space to cover all the details here. Duncan Coutts’ thesis is a wonderful read if you want to know more about the subject.

Stream fusion

Now we know what fusion is, but you may have heard of stream fusion. Stream fusion is a fusion technique that fuses streams. What is a stream? I think it’s fair to describe a stream as a list, but without the overhead that is normally associated with linked lists.

Stream fusion without skip

In fact, while trying to fuse operations on lists, we have already developed a stream fusion system! Remember our definition of a delayed list:

data List a = forall s. List (s -> Maybe (a, s)) s

List represents what’s called a stream without skip. That is, with this model we can either get an element or finish processing—there is no third option. We will return to the skip problem later in this section.

Let’s rewrite the definition in a more common form before we continue:

data Stream a = forall s. Stream (s -> Step a s) s

data Step a s
  = Yield a s
  | Done

Nothing has really changed here; we just introduced the Step data type, which is the same as Maybe (a, s).

What can we do with this approach now? One thing we can attempt is to write functions that have familiar signatures involving linked lists and add rewrite rules to make them run fast.

The rewrite rule we want to use is simpler than the build/foldr rule. Remember that we can turn a list into a stream like this:

stream :: [a] -> Stream a -- aka fromLinkedList
stream = Stream f
  where
    f []     = Done
    f (x:xs) = Yield x xs

and we can get our list back:

unstream :: Stream a -> [a] -- aka toLinkedList
unstream (Stream f s) = go s
  where
    go s' = case f s' of
      Done        -> []
      Yield x s'' -> x : go s''

Then it should make sense that:

stream (unstream s) = s

Converting from a stream to a list and back to a stream doesn’t change anything. If we write our functions as functions on streams and wrap them in the stream/unstream pair of functions, we should get functions that operate on lists:

map3 :: (a -> b) -> [a] -> [b]
map3 f = unstream . map3' f . stream

map3' :: (a -> b) -> Stream a -> Stream b
map3' g (Stream f s) = Stream h s
  where
    h s' = case f s' of
      Done        -> Done
      Yield x s'' -> Yield (g x) s''

foldr3 :: (a -> b -> b) -> b -> [a] -> b
foldr3 f z = foldr3' f z . stream

foldr3' :: (a -> b -> b) -> b -> Stream a -> b
foldr3' g b (Stream f s) = go b s
  where
    go b' s' = case f s' of
      Done        -> b'
      Yield x s'' -> go (g x b') s''

And at the same time, with this rewrite rule:

{-# RULES
"stream/unstream" forall (s :: Stream a). stream (unstream s) = s
  #-}

GHC will make intermediate conversions to and fro shrink:

fused3 :: [Int] -> Int
fused3 = foldr3 (+) 0 . map3 sqr
--       foldr3' (+) 0 . stream . unstream . map3' sqr . stream
--                       ^               ^
--                       | nuked by rule |
--                       +---------------+
--       foldr3' (+) 0 . map3' sqr . stream

(.) will be inlined, so the rules will start to match and we will get exactly this code.

As we already know, this is fast:

benchmarking fused3
time                 3.450 ms   (3.440 ms .. 3.459 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.459 ms   (3.450 ms .. 3.474 ms)
std dev              34.64 μs   (23.78 μs .. 52.99 μs)

Case                  Bytes  GCs  Check
fused3           80,000,016  153  OK

Now we have functions that work on normal lists, and yet their combinations are very fast. Note that this is exactly the approach used in popular libraries like vector and text.

Stream fusion with skip

The fusion system without skip works, but it’s not powerful enough for all the functions we may want to use, such as filter. Let’s try to write filter3 to find out why. There is probably only one way to write filter3 given the limitations of the framework we have developed:

filter3 :: (a -> Bool) -> [a] -> [a]
filter3 f = unstream . filter3' f . stream

filter3' :: (a -> Bool) -> Stream a -> Stream a
filter3' p (Stream f s) = Stream g s
  where
    g s' = case f s' of
      Done -> Done
      Yield x s'' ->
        if p x
          then Yield x s''
          else g s''

fusedFilter :: [Int] -> Int
fusedFilter = foldr3 (+) 0 . filter3 even . map3 sqr

The problem here is that if we need to skip a value, the only thing we can do is call g recursively, which is not good, as the compiler can’t flatten, inline, and further optimize recursive functions.

benchmarking fusedFilter
time                 10.79 ms   (10.76 ms .. 10.82 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 10.81 ms   (10.79 ms .. 10.84 ms)
std dev              69.54 μs   (47.87 μs .. 118.8 μs)

Case                    Bytes  GCs  Check
fusedFilter       100,000,056  192  OK

If we introduce Skip, g ceases to be self-recursive (the adjustments to the other functions are not shown here):

-- <…>

data Step a s
  = Yield a s
  | Skip s
  | Done

-- <…>

filter3' :: (a -> Bool) -> Stream a -> Stream a
filter3' p (Stream f s) = Stream g s
  where
    g s' = case f s' of
      Done -> Done
      Skip    s'' -> Skip s''
      Yield x s'' ->
        if p x
          then Yield x s''
          else Skip s''

This results in some speed and space improvements:

benchmarking fusedFilter
time                 8.904 ms   (8.880 ms .. 8.926 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 8.923 ms   (8.906 ms .. 8.941 ms)
std dev              50.94 μs   (36.94 μs .. 74.59 μs)

Case                   Bytes  GCs  Check
fusedFilter       80,000,016  153  OK

The introduction of Skip promised fame and fortune, but it’s not much of an improvement in this case.

Conclusion

Writing fast Haskell is predicated on understanding what GHC does with your code. The pragmas from the first half of this tutorial and the rewrite rule machinery are the tools you use to guide the compiler, and fusion is what those tools make possible: a way to eliminate intermediate data structures so that a pipeline of transformations runs in a single pass with no allocation in between.

The takeaways worth remembering:

Reach for benchmarking (criterion) and allocation measurement (weigh) before optimizing. Guessing at performance is unreliable; GHC’s behavior is easy to confirm and often surprising.
Rewrite rules are not checked for correctness—it is on you to ensure that the two sides are equivalent, that your rules are confluent, and that phase control lets them fire in the right order.
Fusion frameworks such as stream fusion are already implemented for you in libraries like vector and text. Most of the time the right move is to use them rather than roll your own.