Monday, June 4, 2012

function(groovy) #4


function(groovy) #4

If all you have is a hammer, everything looks like a nail.

Abstract: The iterator methods on the collection classes take a higher order closure as a parameter. But they achieve much more when we recognize that we are relinquishing control over iteration in return for a general mechanism for use with collection frameworks. Higher order functions allow us to raise the abstraction level at which we operate.

Ken Barclay
kenbarc@googlemail.com

Previous:           Advanced closure
Resources:        Chapter 11 Closures

The iterator methods

Table 4.1 lists some of the iterator methods that can be used with the collection classes such as List and Map. Excepting method inject, all these methods are effectively defined on the Groovy Object class. The inject method is defined in the Collection class. Not all of the iterator methods are illustrated. For details of these and other methods see the Groovy documentation.

Table 4.1: Iterator methods

Name
Signature/description
any
boolean    any(Closure predicate)
Iterates over every element of this collection, and check that the predicate is valid for at least one element.
collect
List    collect(Closure transformer)
Iterates through this collection transforming each element into a new value using the closure as a transformer, returning a new List of transformed values.
each
void    each(Closure action)
Iterate through this object and execute the closure.
eachWithIndex
void    eachWithIndex(Closure action)
Iterate through this object and execute the closure with a counter.
every
boolean    every(Closure predicate)
Iterates over every element of this collection, and check that the predicate is valid for all elements.
find
Object    find(Closure predicate)
Find the first value matching the condition defined by the predicate closure. If no match is found, then return null.
findAll
List    findAll(Closure predicate)
Find all the values matching the condition defined by the predicate closure. If no match is found, then return the empty List.
grep
List    grep(Object filter)
Iterate over every element of this collection and return each object that matches the given filter – calling the isCase() method.
inject
Object    inject(Collection collection, Object init, Closure closure)
Iterates through this collection, passing the init value to the closure along with the first item. On subsequent iterations pass the previous closure value and the next iterated item. Upon completion return with the final closure value.

This group of methods take a closure (or function) as parameter. They are usually referred to as higher order functions. This capability is important for a number reasons. Higher order functions means that you can make assumptions how language elements will compose. Through this you can eliminate entire categories of methods in a class hierarchy by building general mechanisms that traverse structures such as lists and apply one or more functions (closures) to each element. This is the subject of this blog, illustrated with some examples.

            Example 4.1 shows method collect used with collections of people and 2-dimensional points. Class Person is defined with name and age properties. Class Point is defined with x and y properties and an implementation for the method equals. It also defines the method moveBy that produces a new Point instance with coordinates moved by the displacement given as parameters.

Example 4.1: Method collect

final Person p1 = new Person(name: 'Ken', age: 25)
final Person p2 = new Person(name: 'John', age: 31)
final Person p3 = new Person(name: 'Jessie', age: 22)

final List<Person> people = [p1, p2, p3]

assert people.collect{ p -> p.name } == ['Ken', 'John', 'Jessie']

final Point pt1 = new Point(x: 2, y : 3)
final Point pt2 = new Point(x: 4, y : 5)
final Point pt3 = new Point(x: 8, y : 12)

final List<Point> points = [pt1, pt2, pt3]

assert points.collect{ p -> p.moveBy(1, 2) } == [new Point(x: 3, y: 5), new Point(x: 5, y: 7), new Point(x: 9, y:14)]
.
The collect method is better known by the name map in the functional world ─ map some function across the elements of a collection.

            The findAll method is used to obtain the elements from a List or Map that match some criteria. In either case a List of successes is returned. If no such elements are found, then [] is returned. The criterion is specified by a predicate function. For a Map, the predicate must be defined in terms of one parameter, representing the map entry. Example 4.2 contains short illustrations. In the functional world this is usually known as filter.

Example 4.2: The findAll method

final List<Integer> numbers = [11, 12, 13, 14]

assert numbers.findAll{ elem -> elem > 12 } == [13, 14]
assert numbers.findAll{ elem -> elem > 14 } == []

assert ['John', 'Ken', 'Jessie'].findAll{ elem -> elem == 'Ken'} == ['Ken']

final Map<String, Integer> staffTel = ['Ken' : 1234, 'John' : 5678, 'Jessie' : 9012]

assert staffTel.findAll{entry -> entry.value > 5000}.collect{ elem -> elem.key}.contains('Jessie')

The inject method iterates through a collection, passing the initial value to the closure along with the first item of the collection. On subsequent iterations pass the previous closure result and the next iterated item from the collection. Upon completion of the iteration, return with the final closure value. Figure 4.1 describes the effect. First, the init value is used to initialize the res formal parameter of the closure. At the same time the first element from the list initializes the elem parameter. The final closure expression returns a value that re-initializes the res parameter with the second list element initializing the elem parameter. The process continues until the final list element is processed and the return from the closure is returned as the result of the inject method.

Figure 4.1: Description of the inject method

Example 4.3 shows the method inject used with collections of people and points. The first assert uses method inject to sum the ages of the people. In the second assert method inject is used to create a Map of People instances indexed by their name. In the third assert a List of the x values from the List of Points is produced. In the final assert a List of the pairs of the x and y values from the Point instances is created. The pairs are presented as sub-lists of length 2.

Example 4.3: Collections of people and 2D points

final Person p1 = new Person(name: 'Ken', age: 25)
final Person p2 = new Person(name: 'John', age: 31)
final Person p3 = new Person(name: 'Jessie', age: 22)

final List<Person> people = [p1, p2, p3]

assert people.inject(0){ res, p -> res += p.age } == 78
assert people.inject([:]){ res, p -> res[p.name] = p; res} == ['Ken': p1, 'John': p2, 'Jessie': p3]

final Point pt1 = new Point(x: 2, y : 3)
final Point pt2 = new Point(x: 4, y : 5)
final Point pt3 = new Point(x: 8, y : 12)

final List<Point> points = [pt1, pt2, pt3]

assert points.inject([]){ res, p -> res += p.x } == [2, 4, 8]
assert points.inject([]){ res, p -> res.add([p.x, p.y]); res} == [[2, 3], [4, 5], [8, 12]]

As we have shown, higher order functions means we can eliminate entire categories of methods on a collection class hierarchy. We build a general mechanism that traverses a collection and applies a higher order function to each element. For example, the collect method expects a function parameter that describes how to transform the elements of the collection. The findAll method expects a predicate closure that identifies the elements to be selected.

By comparison, re-implementing the examples in an imperative style would mean deploying for statements or iterator controlled while loops to manage the iteration. Further, we would be coding each atomic step when implementing the algorithm, often with state.

Relinquishing control over low-level details has been a constant trend in software development. Memory management and garbage collection are now given over to the runtimes. A functional or declarative style continues this development, taking control over iteration as demonstrated. Introducing a functional or declarative style as presented by the examples means we spend less effort in solving a problem (the how) and more on the processes (the what).

No comments: