η-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..]