Eta Reduction

The purpose of eta reduction (also written \(\eta\)-reduction) is to drop an abstraction over a function to simplify it. This is possible when there is nothing more that a function can do to its argument. For example, imagine that we have a simple function \( f\ x = g\ x \). Both \(g\) and \(f\) take the same argument, \(x\), and the function application function results in the same value (specified by the equality symbol). Since both \(f\) and \(g\) take the same argument and produce the same result, we can simplify the equation to just \(f = g\). In lambda calculus, this simplification is called \(\eta\)-reduction.

More precisely, \(\eta\)-reduction allows you to convert between \(\lambda x.(f\ x)\) and \(f\) whenever \(x\) is not a free variable in \(f\). That is, \(f = \lambda x(f\ x)\). Let’s look at a more practical example from the book PureScript by Example.

In functional languages based on lambda calculus, all functions take exactly one argument. PureScript is no different. For example, consider the function insertEntry that inserts an entry into an address book. This function takes an Entry and an AddressBook as a parameter, and returns a new AddressBook with the entry parameter inserted into it. This function has a type signature of insertEntry :: Entry -> AddressBook -> AddressBook, which specifies that the function insertEntry takes parameters of type Entry and AddressBook and returns a result of AddressBook.

We make some simplifying assumptions here by assuming that AddressBook is implemented as a simple list. We can therefore use concatenation (or list construction) to implement insertEntry by concatenating the entry to the address book using the concatenation function Cons. This results in the following type signature and implementation for insertEntry.

insertEntry :: Entry -> AddressBook -> AddressBook
insertEntry entry book = Cons entry book

This function is implemented by passing the book and entry parameters to the Cons function to concatenate them together. If we remove the parameter book from both sides of the function definition, we end up with a function insertEntry entry and a function Cons entry. Both of these functions can still be called with book as a parameter. Since these two functions are equivalent and they take the same parameter, we can use \(\eta\)-reduction to completely eliminate the parameter book from the function definition.

insertEntry :: Entry -> AddressBook -> AddressBook
insertEntry entry = Cons entry

By the same reasoning, we can further reduce the function to remove the entry argument. This results in the following function:

insertEntry :: Entry -> AddressBook -> AddressBook
insertEntry = Cons

We now have a very simple implementation for insertEntry — it is just Cons on a list.

comments powered by Disqus