function(groovy) #5
If all you have is a hammer, everything looks like a nail.
Abstract: One of the
challenges of a new paradigm is learning to think in an entirely new way. The ability
to pass code as a parameter introduces a new style to the imperative
programmer. A declarative style abstracts out generic pieces of machinery and
customizes them via higher-order functions.
Ken Barclay
kenbarc@googlemail.com
Previous: The iterator methods
Resources: Chapter 12 Higher Order Functions
The iterator functions
Many
functions to perform functional style List
manipulation are defined as static methods and closures in the companion class GListF. The class is defined as abstract so there is no intention
of creating an instance. It simply acts as a repository for these useful
functions. The arrangement is not unlike the latest Groovy extension methods.
For example, this class defines the function map that transforms a list of values in
the manner of the GDK's collect
method using a function as its transformer. The map function is provided in two flavors: a curried form and an
uncurried form. Of course, the function C
is used to define the curried version from its uncurried version. The curried
version is given the suffix C in its name:
/**
* Function map takes two parameters: a
function and a list. Function map
*
applies the function parameter to each item in the list, delivering
* a
new list.
*
* map:: (X -> Y) * [X] -> [Y]
* mapC:: (X -> Y) -> [X] -> [Y]
*
* @param fxy pure function:: X -> Y
* @param ys existing list
* @return new list of transformed values
*/
private
static final <X, Y> List<Y> _map(final Closure<Y> f, final
List<X> xs) { xs.collect(f) }
public
static final map = GListF.&_map
public
static final mapC = C(map)
For most applications function map will suffice. However, in some advanced examples we will find
we wish to call mapC with its single
function parameter.
Observe how the behavior is first defined with the _map method. The closures map and mapC are defined from it. The &.
operator is used to get a reference to a
method, and from it create a reference to a closure. The aim of this scheme is
to define the _map method with the
generic type parameters X and Y. Including both the parameter type
and result type fully documents the values involved in using this method.
Groovy does not support generic type parameters when defining closures and so
this approach circumvents this limitation. A Groovy static type checker would
assist greatly.
All the methods/closures defined in
GListF present the Groovy list with
an immutable interface. As a consequence, some of the operations are not
especially efficient. This issue is revisited in a later blog where we
implement a more efficient immutable list. Notwithstanding this, we can begin
presenting solutions that are more declarative than would be possible using
Groovy lists directly.
Mapping
The
GDK's collect iterator method is used
to iterate through the elements of the receiving list object and transforms each element into a new value
using the closure parameter as a transformer, returning a list of transformed values.
A
pictorial representation of how map behaves is shown in
Figure 5.1. On the left we show some function (closure) f which when applied to a single parameter
(represented by the circle) delivers a value (the square). Now, if we have a list of values of type circle,
then map f list delivers a list of values of type square
produced by applying f to each of the originals.
Figure 5.1: Application
of map
As
we noted, the companion class GListF
contains a rich selection of functions (static closure definitions) for
processing lists. Example 5.1 revisits the previous example, this time using
the mapC function from GListF.
Example 5.1: Curried
map
import static
com.adt.groovy.data.immutable.list.GListF.mapC
// multiply:: Integer * Integer ->
Integer
final multiply = {
final int x, final int y -> x * y}
// twice:: Integer -> Integer
final twice =
multiply.curry(2)
// quadruple:: Integer -> Integer
final quadruple =
multiply.curry(4)
// twiceAll:: [Integer] -> [Integer]
final twiceAll =
mapC(twice)
// quadrupleAll:: [Integer] -> [Integer]
final quadrupleAll =
mapC(quadruple)
final
List<Integer> numbers = [1, 2, 3, 4]
assert
twiceAll(numbers) == [2, 4, 6, 8]
assert
quadrupleAll(numbers) == [4, 8, 12, 16]
It
is relatively easy to prove that map(f ● g, xs) = (map f ● map g)(xs), where ● represents function composition. Applying f ● g to every element of a
list is the same as applying g to every member of the list and then applying f
to every member of the resulting list. The equality demonstrates how we might refactor our code to make it more
efficient. If our code includes (map f ● map g) then we optimize it with map(f ● g). The former makes one
pass across the initial list then a second pass across the result list. The
latter makes only a single pass across the initial list reducing the amount of
work to be done. This equality is demonstrated in Example 5.2.
Example 5.2: Map
composition equality
import static
com.adt.groovy.data.immutable.list.GListF.mapC
import static
com.adt.groovy.data.immutable.list.GListF.map
// twice:: Integer -> Integer
final twice = { final
int x -> 2 * x}
// successor:: Integer -> Integer
final successor = {
final int x -> 1 + x}
// composeTwiceSuccessor:: Integer ->
Integer
final
composeTwiceSuccessor = twice >> successor
// composeMapTwiceMapSuccessor:: [Integer]
-> [Integer]
final composeMapTwiceMapSuccessor
= mapC(twice) >> mapC(successor)
final
List<Integer> numbers = [1, 2, 3, 4]
assert
map(composeTwiceSuccessor, numbers) == composeMapTwiceMapSuccessor(numbers)
The
function composeTwiceSuccessor
transforms an Integer into another Integer. The left side of the assert applies this transformation to
the list of numbers. On the right side of the assert the function composeMapTwiceMapSuccessor
first doubles the values in the numbers
list, then increments by one the values in the resulting list.
Filtering
It
is also common to select all the elements from a list with some given property.
For example we might wish to choose only those overdrawn bank accounts from a
list of accounts. We usually describe this as filtering. Example 5.3 introduces the higher order function filter in which the selection
criterion is specified by the function parameter. The selection function is
sometimes known as a predicate ― a
function returning a Boolean value which describes whether the criterion has
been met.
Example 5.3: The filter
function
import static
com.adt.groovy.data.immutable.list.GListF.filter
// isEven:: Integer -> Boolean
final isEven = { final
int x -> (x % 2 == 0)}
final
List<Integer> numbers = [11, 12, 13, 14]
assert filter(isEven,
numbers) == [12, 14]
assert filter(isEven,
[]) == []
def bk1 = new
Book(title: 'Groovy Programming', author: 'Barclay', price: 22.90, category:
'CompSci')
def bk2 = new
Book(title: 'Groovy in Action', author: 'Konig', price: 32.00, category:
'CompSci')
def bk3 = new
Book(title: 'Grails', author: 'Rocher', price: 29.00, category: 'CompSci')
def bk4 = new
Book(title: 'Thinking in Java', author: 'Eckel', price: 24.50, category:
'CompSci')
def List<Book>
books = [bk1, bk2, bk3, bk4]
assert filter({bk
-> (bk.price < 25.00)}, books) == [bk1, bk4]
The GDK's iterator method findAll
is used to implement the filter
function.
Earlier we showed how proving equality of two
mappings can lead to more efficient programs. We can also show that:
filter p ● map f = map
f ● filter(p ● f)
The
equation says that a map followed by
a filter can be replaced by a filter followed by a map. The right side is potentially more
efficient than the left since the map
could be applied to a shorter list. This is demonstrated by Example 5.4.
Example 5.4: Maps and
filters
import static
com.adt.groovy.data.immutable.list.GListF.filterC
import static
com.adt.groovy.data.immutable.list.GListF.mapC
// isWrittenBy:: String -> Book ->
Boolean
final isWrittenBy = {
final String auth -> { final Book book -> (book.author == auth)}}
// priceIncrease:: BigDecimal -> Book
-> Book
final priceIncrease =
{ final BigDecimal amount -> { final Book book -> new Book(title: book.title,
author: book.author, price: book.price + amount, category: book.category)}}
final mapThenFilter =
mapC(priceIncrease(2.00)) >> filterC(isWrittenBy('Ken Barclay'))
final filterThenMap =
filterC(priceIncrease(2.00) >> isWrittenBy('Ken Barclay')) >>
mapC(priceIncrease(2.00))
final book1 = new
Book(title: 'Groovy Programming', author: 'Ken Barclay', price: 20.45,
category: 'CompSci')
final book2 = new
Book(title: 'Groovy in Action', author: 'Dierk Konig', price: 32.00, category:
'CompSci')
final book3 = new
Book(title: 'Object Oriented Design', author: 'Ken Barclay', price: 25.50,
category: 'CompSci')
final book4 = new
Book(title: 'Programming Groovy', author: 'Venkat Subramaniam', price: 29.50,
category: 'CompSci')
final List<Book>
books = [book1, book2, book3, book4]
assert
mapThenFilter(books) == filterThenMap(books)
Figure 5.2 describes the filter closure. If p represents some predicate function (closure, returning a boolean
value), then when applied to a triangle it delivers true and when applied to a
square it produces false. Now filter p list delivers a new list containing only
those triangles that satisfy the predicate.
Figure 5.2:
Application of filter
Folding
It
is also common to reduce a collection to a single value. For example we might
wish to sum or multiply all the elements in a list. This
is the basis for a particular kind of higher order function called folding. Folding is used to fold a
function (such as a summation) into a list of values.
The
fold function reduces a list to a single value by "folding" a
binary operator between successive elements of the list. For example, consider
we have the list [x1, x2, x3, ..., xn], an initial value e, and the binary
operator □, then:
fold □ e [x1, x2, x3, ..., xn] = e □ x1 □ x2 □ x3 □ ... □ xn
The fold function takes a binary function □, together with an initial
value e and a list. Notice that the version of fold above is left-associative.
In other words, the result it produces is equivalent to doing:
( ... (((e □ x1) □ x2) □ x3) ... □
xn)
Example
5.5 introduces the function foldLeft implemented using the
GDK's each iterator method.
It has three parameters: the binary function to be folded in, the initial value
when starting the folding, and the list of values. The type signature for the
function given as:
/**
* foldLeft is a higher-order
function that folds a binary function into a
* list of values. Effectively:
*
* foldLeft(f, e, [x1, x2, ..., xn]) = (...((e
f x1) f x2) f...) f xn
*
* foldLeft:: (Y -> X -> Y)
* Y * [X] -> Y
* foldLeftC:: (Y -> X -> Y)
-> Y -> [X] -> Y
*
* @param f pure binary function:: Y -> X -> Y
* @param e initial value
* @param xs existing list
* @return folded result
*/
private static final <X, Y> Y _foldLeft(final Closure<Y> f,
final Y e, final List<X> xs) {
Y res = e
xs.each{ x -> res = f(res)(x)
}
return res
}
public static final foldLeft = GListF.&_foldLeft
public static final foldLeftC = C3(foldLeft)
Note
that the function parameter is expected in its curried form. The function
parameter combines a Y and an X to produce a Y. The initial value for foldLeft is of type Y and is combined
with the first member of the list. The result of type Y is then combined with
the second member of the list, and so on. Ultimately, a Y value is delivered.
The companion class GListF includes
the two variants foldLeft and foldLeftC.
Example 5.5:
The foldLeft function
import static com.adt.groovy.fp.FunctionF.C
import static
com.adt.groovy.data.immutable.list.GListF.appendC
import static
com.adt.groovy.data.immutable.list.GListF.foldLeft
// add::
Integer * Integer -> Integer
final add = { final int x -> { final int y ->
x + y }}
final List<Integer> numbers = [11, 12, 13,
14]
final int sum = foldLeft(add, 0, numbers)
assert sum == 50
//
logicalAnd:: Boolean -> Boolean -> Boolean
final logicalAnd = { final boolean x -> { final
boolean y -> x && y }}
final List<Boolean> truthful = [true, true,
true]
final boolean allTruthful = foldLeft(logicalAnd,
true, truthful)
assert allTruthful == true
final List<Integer> flatten =
foldLeft(appendC, [], [[1, 2, 3], [4, 5], [6]])
assert flatten == [1, 2, 3, 4, 5, 6]
Folding is a surprisingly fundamental operation.
Its generality allows us to define many standard list processing operations.
Example 5.6 defines the primitive operation reverse in terms of a left fold. The initial value given to foldLeft is the empty list [] into
which the reversed list is assembled. The binary function required by foldLeft must then have the signature
[X] -> X -> [X] where the second parameter is prepended on to the list
first parameter. Of course consC
does just this but has its parameter in the opposite order. Functions flip and flipC performs the necessary transformation, converting the
function X -> Y -> Z to Y -> X -> Z.
Example 5.6: Folding and
primitive operations
import static com.adt.groovy.fp.FunctionF.flipC
import static com.adt.groovy.data.immutable.list.GListF.consC
import static com.adt.groovy.data.immutable.list.GListF.foldLeft
// reverse:: [A] -> [A]
final reverse = {xs -> foldLeft(flipC(consC), [], xs)}
assert reverse([1, 2, 3, 4]) == [4, 3, 2, 1]
assert reverse(['Ken', 'John', 'Jessie']) == ['Jessie', 'John', 'Ken']
These examples illustrate how the functional style
gives us new and different building blocks. Some of the examples used the
curried variants mapC and filterC to produce specialist
processing functions. No new code had to be developed other than the closure
parameters. The curried forms are our factories for functions.
The examples also show a reduced use of control
flow such as for statements. This offers many advantages. First, the code is
easier to read and write. That means it will be easier to reason about its
correctness. Control flow statements are usually accompanied by state variables
that are updated. In its place we see code in which we sequentially bind
results to identifiers then finish the code with the resulting expression.
These extension methods are not, in some cases.
especially efficient. For example, the concatenate
method produces a new list by joining together two existing lists. Immutable
data structures, the subject of the next blog, can offer a solution.
