η-reductions

Eta-reductions are one of the most common code transformations used in Haskell. Briefly, if we have code that looks like this:

\x -> M x

where M is an expression applied to x that doesn't include x, then we can rewrite this as just:

M

This often occurs in a sugared context, wherein both the left and right hand side of a definition consist of expressions in which a variable doesn't occur, applied to that variable, e.g.,

sum xs = foldr (+) 0 xs

is actually written in the standard Prelude as

sum = foldr (+) 0

reflecting the cancellation of the terminal xs's from both sides.

This can be understood as an ordinary η-reduction if we first de-sugar the definition as

sum = \xs -> foldr (+) 0 xs

and then η-reduce the right hand side as before to get

sum = foldr (+) 0

Oftentimes, we'll see definitions that we want to η-reduce, but where it's not exactly in the right form, e.g.,

sse xs = sum $ map square $ filter even xs

This looks as though we ought to be able to η-reduce it, but the syntax is misleading. This is not an application of sum $ map square $ filter even to x, because the first infix operator ($) is actually the top level combinator, and its arguments are sum and map square $ filter even xs. To set up for an η-reduction, we're going to need another transformation.

Composition

Recall the composition operator:

(f . g) x ≣ f (g x)

We can often use this equation in reverse, replacing a nested application by a composition applied to a argument.

sse xs = sum $ map square $ filter even xs

as

sse xs = (sum . map square . filter even) xs

setting ourselves up for an η-reduction:

sse = sum . map square . filter even

converting "ordinary" code into point-free code.

Sections

Sections are another bit of Haskell syntax that are often used, and often to set us up for an η-reduction or other code transformation. For example, consider

square x = x ^ 2 sumOfSquares x = sum (map square x)

We can simplify this by introducing a section:

square x = (^2) x

which is then η-reduced to

square = (^2)

at this point, we can simply replace the occurrence of square in the definition of sumOfSquares by its definition, obtaining

sumOfSquares x = sum (map (^2) x)

This can be transformed by introducing a composition on the right hand side:

sumOfSquares x = (sum . map (^2)) x

and followed by an η-reduction:

sumOfSquares = sum . map (^2)

A similar substitution can be used for

exp x = 2 ^ x sumOfPowers xs = sum (map exp x)

re-writing the definition of exp as:

exp x = (2^) x

and then

exp = (2^)

continuing as before, we end up at

sumOfPowers = sum . map (2^)

Flip

The flip function can often be used to move a variable into a position where we eliminate it by η-reduction, e.g., consider the following definition of a function that produces the list of natural numbers that satisfies a predicate p:

satisfies p = filter p [0..]

The flip function allows us to interchange the order of arguments to a binary function:

f x y = flip f y x

thus

satisfies p = flip filter [0..] p

which is η-reduction ready:

satisfies = flip filter [0..]