Loops and Iterators

5.3.5

Loops and Iterators

Outline 16

What is a loop
Understanding the fold loops
Java implementation of the fold loops
Iterator vs. Iterable
Designing loop methods using the Iterator
Variety of loop controls: for, while, do-while, for-each

What is a loop?

The key components of programs that describe the actions the program should take are known by three different names, depending on the programming language we use and the nature of the computation performed.

The name function is typically used for a mutation-free computation that consumes as arguments some data and produces new values (new objects or data of primitive type) upon completion of the computation. Most of the computation you have seen in DrRacket teaching languages are of this type.

The name procedure is typically used for computations that are mainly concerned with side-effects (mutation, change of state) and in most cases do not result in any new value. Our void methods would fit this description.

In the context of object-oriented languages, the functions and procedures that are defined within a class are called methods and can represent either the classical mutation-free functions or the mutating procedures, or a combination of these, i.e. computations that both impact the state of the program via side-effects, and produce a new value upon completion.

A loop is a function or a procedure (or a method) that consumes as one of its arguments an object that represents a collection of data items and performs some operation on all items in the given collection.

There are two independent design problems that a designer of a loop needs to consider: the actions to be performed on each item in the collection, and the mechanism used to consume the elements of the collection, one at a time.

To help the programmer, many programming languages contain statements or other constructs that help the programmer in designing the traversal through the elements of a collection.

For recursively-defined lists we have studied in detail the traversal is hidden in the natural decomposition of the list into its first element and the rest of the list. Because traversing lists is such a natural operation, functional programming languages such as Scheme and DrRacket define a number of commonly used loop functions such as map, ormap, andmap, filter, as well as the most general ones, foldl and foldr.

Understanding the fold loops

The foldr and foldl functions make it clear what one needs to consider when designing the loop actions. Here is the contract and purpose for these two functions:

;; foldr : (X Y -> Y) Y (listof X) -> Y

;; (foldr f base (list x-1 x-2 ... x-n)) = (f x-1 ... (f x-n base)...)

(define (foldr f base alox) ...)

;; foldl : (X Y -> Y) Y (listof X) -> Y

;; (foldl f base (list x-1 x-2 ... x-n)) = (f x-n ... (f x-1 base)...)

(define (foldl f base alox) ...)

The function applies the given function of two arguments to the next item in the list and the accumulated result from the earlier applications, starting with some base value. The difference between these two loops is in the order in which the list elements are processed. While the first one (foldr) is the loop derived naturally by using the Design Recipe, the second one consumes the list elements in the order in which they are first seen, eliminating the need to wait until the whole list unfolds before the computation begins.

Use the Stepper to trace the evaluation of the following two loops:

(define (sum-right alon base)

(cond [(empty? alon) base]

[else (+ (first alon) (sum-right (rest alon) base))]))

(define (sum-left alon base)

(cond [(empty? alon) base]

[else (sum-left (rest alon) (+ (first alon) base))]))

(sum-right (list 3 4 5) 0)

(sum-left (list 3 4 5) 0)

We see first (when tracing sum-right:

(cond

((empty? empty) 0)

(else

(first empty)

(sum-right

(rest empty)

0)))))))

i.e., no computation is done until we reach the end of the list, while tracing of sum-left starts with:

((lambda (alon base)

(cond

((empty? alon) base)

(else

(sum-left

(rest alon)

(+ (first alon) base)))))

(list 4 5)

(+ 3 0))

i.e. adding 3 to the base value 0, then adding 4 to the carried value of the accumulator, and finally adding 5 to the accumulator and immediately returning the result.

The loop action is defined by the function that consumes the value accumulated during the traversal of the list, as well as the current list element, and produces a new value that includes the effect of the latest list element on the final result.

For a loop that computes the sum, the accumulated value is the running sum of elements already seen, for a filter loop, the accumulated value is the list of already selected items.

When the fold is applied to an empty list, it returns the base value. When computing the sum, the base value is zero, when applying the filter to a list, the base value is an empty list.

But note, that foldl starts using the base value when it sees the first element of the list, so that by the time the last element is seen, the base paramtere represents the desired accumulated value of the result.

Java implementation of fold

We can implement the foldl and the foldr functions in Java, in the context of the recursively defined lists as shown in the ExamplesListLoops.java program.

The methods foldr and foldl defined for lists of type T consume two arguments, a function object that represents a function f: T R -> R and the accumulator of the type R, and produces a value of the type R.

In the case of the empty list both methods just return the value of the accumulator. For the foldr variant we name the argument base, but we change the name for the second variant to acc to highlight the fact that by the time we reach the empty list, the resulting accumulated value is already known and saved in the acc parameter.

The difference between the two versions is apparent in the method body for the ConsLo class:

/**

* Apply the given update function to all elements of this list,

* starting with the last one, and ending with the first one.

* (Apply the update function to the current element of the list,

* and the result of <code>foldr</code> applied to the rest of the list.)

* @param f the function that computes the updated accumulator

* value from the current list element and the current

* value of the accumulator

* @param acc initial (and accrued) value of the accumulator

* @return the updated value of the accumulator

public <R> R foldr(FunTR2R<T,R> f, R base){

return f.apply(this.first, this.rest.foldr(f, base));

}

/**

* Apply the given update function to all elements of this list,

* starting with the first one, and ending with the last one.

* (Invoke <code>foldl</code> on the rest of the list

* and the accumulator updated with the current element of the list.)

* @param f the function that computes the updated accumulator

* value from the current list element and the current

* value of the accumulator

* @param acc initial (and accrued) value of the accumulator

* @return the updated value of the accumulator

public <R> R foldl(FunTR2R<T,R> f, R acc){

return this.rest.foldl(f, f.apply(this.first, acc));

}

The detailed comments explain the differences. Of course, the actual work is done in the update function objects. We show four examples that represent the sum, ormap, andmap and finally a concat-style function that illustrates the order in which the list elements are processed.

Here is the definition of the update function object, with its four implementations:

/**

* to represent a function that consumes an object

* of the type <code>T</code> and an object of the

* type <code>R</code> and produces a new accumulated

* value of the type <code>R</code>

* @param <T> the type <code>T</code> of the first argument

* @param <R> the type <code>R</code> of the second argument

* and of the result

interface FunTR2R<T, R>{

/**

* Apply this function to the given element and accumulator

* producing an updated accumulator value

* @param t the given element

* @param r the given accumulator

* @return an updated accumulator value

public R apply(T t, R r);

}

/**

* to represent an update function that sums up the lengths of all

* <code>String</code>-s in the list

class TotLength implements FunTR2R<String, Integer>{

/** add the length of the given String to the accumulated length */

public Integer apply(String s, Integer acc){

return acc + s.length();

}

/**

* to represent an update function that checks if any

* <code>String</code>-s in the list is shorter than the given limit

class HasShort implements FunTR2R<String, Boolean>{

int limit;

HasShort(int limit){

this.limit = limit;

}

/** acc = have seen a short String or the given one is short */

public Boolean apply(String s, Boolean acc){

return acc || (s.length() < this.limit);

}

/**

* to represent an update function that checks if all

* <code>String</code>-s in the list are shorter than the given limit

class AllShort implements FunTR2R<String, Boolean>{

int limit;

AllShort(int limit){

this.limit = limit;

}

/** acc = all Strings so far were short and the given one is too */

public Boolean apply(String s, Boolean acc){

return acc && (s.length() < this.limit);

}

/**

* to represent an update function that combines all

* <code>String</code>-s in the list into one long <code>String</code>

class Append implements FunTR2R<String, String>{

/** acc = concat of all Strings so far plus the given one */

public String apply(String s, String acc){

return acc.concat(s);

}

We then make examples of the instances of these four function objects:

/** function object: add up lengths of given <code>String</code>-s */

FunTR2R<String, Integer> totLength = new TotLength();

/** function object: check if all given String-s are shorter than 4 */

FunTR2R<String, Boolean> allShort = new AllShort(4);

/** function object: check if any given String is shorter than 4 */

FunTR2R<String, Boolean> hasShort = new HasShort(4);

/** function object: combine all given <code>String</code>-s into one */

FunTR2R<String, String> append = new Append();

We define sample lists to use in tests:

/** a sample lists of <code>String</code>-s of mixed length */

ILo<String> slistMix =

new ConsLo<String>("hello",

new ConsLo<String>("hi",

new ConsLo<String>("arrivederci",

new ConsLo<String>("bye", new MtLo<String>()))));

/** a sample lists of only short <code>String</code>-s */

ILo<String> slistShort =

new ConsLo<String>("hi",

new ConsLo<String>("bye", new MtLo<String>()));

/** a sample lists of only long <code>String</code>-s */

ILo<String> slistLong =

new ConsLo<String>("hello",

new ConsLo<String>("ciao",

new ConsLo<String>("arrivederci",

new ConsLo<String>("aloha", new MtLo<String>()))));

and finally test the implementation of the two methods for these four variants:

/**

* Test using fold to implement sum of lengths of all

* <code>String</code>-s

void testSumLengths(Tester t){

t.checkExpect(this.slistMix.foldl(totLength, 0), 21);

t.checkExpect(this.slistShort.foldl(totLength, 0), 5);

t.checkExpect(this.slistLong.foldl(totLength, 0), 25);

t.checkExpect(this.slistMix.foldr(totLength, 0), 21);

t.checkExpect(this.slistShort.foldr(totLength, 0), 5);

t.checkExpect(this.slistLong.foldr(totLength, 0), 25);

}

/**

* Test using fold to check that a list has a short

* <code>String</code>

void testHasShort(Tester t){

t.checkExpect(this.slistMix.foldl(hasShort, false), true);

t.checkExpect(this.slistShort.foldl(hasShort, false), true);

t.checkExpect(this.slistLong.foldl(hasShort, false), false);

t.checkExpect(this.slistMix.foldr(hasShort, false), true);

t.checkExpect(this.slistShort.foldr(hasShort, false), true);

t.checkExpect(this.slistLong.foldr(hasShort, false), false);

}

/**

* Test using fold to check that all <code>String</code>-s in a list

* are short

void testAllShort(Tester t){

t.checkExpect(this.slistMix.foldl(allShort, true), false);

t.checkExpect(this.slistShort.foldl(allShort, true), true);

t.checkExpect(this.slistLong.foldl(allShort, true), false);

t.checkExpect(this.slistMix.foldr(allShort, true), false);

t.checkExpect(this.slistShort.foldr(allShort, true), true);

t.checkExpect(this.slistLong.foldr(allShort, true), false);

}

/**

* Test using fold to append together all <code>String</code>-s

* in a list of <code>String</code>-s

// using fold to append together all Strings in a list of Strings

void testAppend(Tester t){

// foldl

t.checkExpect(this.slistMix.foldl(append, ""),

"hellohiarrivedercibye");

t.checkExpect(this.slistShort.foldl(append, ""),

"hibye");

t.checkExpect(this.slistLong.foldl(append, ""),

"hellociaoarrivedercialoha");

t.checkExpect(this.slistMix.foldr(append, ""),

"byearrivedercihihello");

t.checkExpect(this.slistShort.foldr(append, ""),

"byehi");

t.checkExpect(this.slistLong.foldr(append, ""),

"alohaarrivederciciaohello");

}

Java for-each loop control

We now want to design loop methods that work for other collections of data, specifically for the Java ArrayList. We cannot add to the definition of the ArrayList class, and so our method will have to consume the ArrayList that we wish to traverse. Otherwise, the method should behave just like before: updating the value of the accumulator every time another element of the ArrayList is given, and return the final value of the accumulator at the end.

Java provides for all classes that represent collections of data elements a mechanism for generating all elements of the collection, one at a time, as well as the language constructs (statements) that traverse over the generated elements.

Here is the definition of this variant of fold:

/**

* Apply the given update function to all elements of the given

* <code>ArrayList</code>.

* For the empty list just return the given base value.

* @param f the function that computes the updated accumulator

* value from the current <code>ArrayList</code> element and

* the current value of the accumulator

* @param base the initial value of the accumulator

* @return the updated value of the accumulator

static <R, T> R fold(ArrayList<T> arlist, FunTR2R<T, R> f, R base){

R acc = base;

for (T t: arlist){

acc = f.apply(t, acc);

}

return acc;

}

We have to define this method in some class - we will call it Algorithms. But the method does not use any properties of an instance of this class. Methods of this type (you can tell by the fact that the word this does not appear in the purpose statement) that do not rely on any properties of the class instance are usually declared as static. These methods are then invoked by specifying only their enclosing class, in this case it would be Algorithms.fold(...).

The traversal is defined by the for statement. For each generated element t in the given ArrayList the program executes the action defined in the statement block enclosed by braces { } that immediately follows the for clause. When all elements of the ArrayList have been processed, the program execution continues with the next statement.

We define sample ArrayLists similar to those used int the earlier examples:

/** an <code>ArrayList</code> of <code>String</code>-s of mixed lengths */

ArrayList<String> arlistMix = new ArrayList<String>(

Arrays.asList("hello", "hi", "arrivederci", "bye"));

/** an <code>ArrayList</code> of only short <code>String</code>-s */

ArrayList<String> arlistShort = new ArrayList<String>(

Arrays.asList("hi", "bye"));

/** an <code>ArrayList</code> of only long <code>String</code>-s */

ArrayList<String> arlistLong = new ArrayList<String>(

Arrays.asList("hello", "ciao", "arrivederci", "aloha"));

and rewrite the tests from before, applying our new version of the fold method:

t.checkExpect(Algorithms.fold(arlistMix, totLength, 0), 21);

t.checkExpect(Algorithms.fold(arlistShort, totLength, 0), 5);

t.checkExpect(Algorithms.fold(arlistLong, totLength, 0), 25);

t.checkExpect(Algorithms.fold(arlistMix, hasShort, false), true);

t.checkExpect(Algorithms.fold(arlistShort, hasShort, false), true);

t.checkExpect(Algorithms.fold(arlistLong, hasShort, false), false);

t.checkExpect(Algorithms.fold(arlistMix, allShort, true), false);

t.checkExpect(Algorithms.fold(arlistShort, allShort, true), true);

t.checkExpect(Algorithms.fold(arlistLong, allShort, true), false);

t.checkExpect(Algorithms.fold(arlistMix, append, ""),

"hellohiarrivedercibye");

t.checkExpect(Algorithms.fold(arlistShort, append, ""),

"hibye");

t.checkExpect(Algorithms.fold(arlistLong, append, ""),

"hellociaoarrivedercialoha");

We see from the last example that the objects are generated in the order they appear in the given ArrayList, i.e. starting with the element at index 0 and ending with the element at the index arlist.size() - 1.

Iterator vs. Iterable

For the for statement to work the object that represents the collection of data elements must be defined in a class that implements the Iterable interface defined as follows:

interface Iterable<T>{

/** produce an <code>Iterator> for this collection */

Iterator<T> iterator();

}

Well, this does not help us much, as we now need to see what is an Iterator. In general the word iterator means an object that can generate the elements of a collection, and signal when the traversal has been completed. In Java, the Iterator interface is defined as follows:

interface Iterator<T>{

/**

* produce the current element of this collection

* and advance to look at the next element (if any)

T next();

/**

* produce <code> true</code> if an element is available

boolean hasNext();

/**

* an optional method that removes the element just generated

* by <code>next</code> that cvan be used only once after each

* invocation of <code>next</code> (not used here)

void remove();

}

Every element is generated only once, and once the traversal has been completed, the Iterator object is useless. If we want to traverse over the collection again, we need to create a new Iterator.

We can have several Iterators active at the same time, but we are not allowed to make any changes to the ArrayList we are traversing. Should we do so, the program will throw the ConcurrentModificationException.

We can design an Iterator for the ArrayList collection as follows:

/**

* A class that illustrates how iterators are built and how the

* <ode>iterator()</code> method can be implemented.

class ArrayListIterator<T> implements Iterator<T>, Iterable<T>{

ArrayList<T> arlist;

int current;

/** Initialize the iterator with the data set and index = 0 */

ArrayListIterator(ArrayList<T> arlist){

this.arlist = arlist;

this.current = 0;

}

/** check if the index has reached the end of the data set */

public boolean hasNext(){

return this.current < this.arlist.size();

}

/** get the next element and advance - throw exception if out-of-bounds */

public T next(){

T t = this.arlist.get(current);

this.current = this.current + 1;

return t;

}

/** unimplemented */

public void remove(){

}

/** produce a fresh iterator for the same data set every time it is called */

public Iterator<T> iterator(){

return new ArrayListIterator<T>(arlist);

}

We can modify our fold method so that it consumes an arbitrary Iterable collection of data:

/**

* Apply the given update function to all elements of the given

* <code>Iterable</code> collection.

* For the empty data set just return the given base value.

* @param f the function that computes the updated accumulator

* value from the current <code>ArrayList</code> element and

* the current value of the accumulator

* @param base the initial value of the accumulator

* @return the updated value of the accumulator

static <R, T> R foldIter(Iterable<T> iterlist, FunTR2R<T, R> f, R base){

R acc = base;

for (T t: iterlist){

acc = f.apply(t, acc);

}

return acc;

}

It does not differ much from the origonal one. We can now make examples of our ArrayListIterators and rerun the same tests as follows.

Examples of iterators:

/** an iterator for the <code>ArrayList</code> of

* <code>String</code>-s of mixed lengths */

ArrayListIterator<String> arlistMixIter =

new ArrayListIterator<String>(this.arlistMix);

/** an iterator for the <code>ArrayList</code> of

* <code>String</code>-s of mixed lengths */

ArrayListIterator<String> arlistShortIter =

new ArrayListIterator<String>(this.arlistShort);

/** an iterator for the <code>ArrayList</code> of

* <code>String</code>-s of mixed lengths */

ArrayListIterator<String> arlistLongIter =

new ArrayListIterator<String>(this.arlistLong);

and the corresponding tests:

t.checkExpect(Algorithms.foldIter(arlistMixIter, totLength, 0), 21);

t.checkExpect(Algorithms.foldIter(arlistShortIter, totLength, 0), 5);

t.checkExpect(Algorithms.foldIter(arlistLongIter, totLength, 0), 25);

t.checkExpect(Algorithms.foldIter(arlistMixIter, hasShort, false), true);

t.checkExpect(Algorithms.foldIter(arlistShortIter, hasShort, false), true);

t.checkExpect(Algorithms.foldIter(arlistLongIter, hasShort, false), false);

t.checkExpect(Algorithms.foldIter(arlistMixIter, allShort, true), false);

t.checkExpect(Algorithms.foldIter(arlistShortIter, allShort, true), true);

t.checkExpect(Algorithms.foldIter(arlistLongIter, allShort, true), false);

t.checkExpect(Algorithms.foldIter(arlistMixIter, append, ""),

"hellohiarrivedercibye");

t.checkExpect(Algorithms.foldIter(arlistShortIter, append, ""),

"hibye");

t.checkExpect(Algorithms.foldIter(arlistLongIter, append, ""),

"hellociaoarrivedercialoha");

Let us summarize what are the tasks that iterators perform: they give us access to one element of the collection at a time, they allow us to detect when the collection is empty (has no more elements to process), and has some internal mechanism that advances to the next element of the collection, once the current element has been processed.

The for loop control statment that uses the Iterator to traverse over a collection of data is one of several loop conrol statements in Java. Colloquially, it is known as for-each loop control and has not been a part of original version of Java.

Other Java loop control statements

So far the loop method were only allowed to traverse the given collection of data elments, but were not allowed to make any changes. At times we need to do that. For example, we will learn how to modify the given ArrayList so that its elements end up sorted, without using any other auxilliary data structure. We may want to look for an element with the given property and remove it from the data set.

Java allows us to design this type of methods by providing additional control statement for traversing data sets or repeating the execution of specific code segments.

Each loop control statement allows the programmer to initialize the controls of the loop, control whether the body of the loop (the statement following the control part) should be performed (for example, if the data set the loop was designed to process is empty, or depleted), and allows for modifying some values prior to the next execution of the loop body (typically used for advancing to the next element of the data set).

Java loop controls: for statement

The basic for loop control statement consists of three parts, each of them a statement itself. The first statement is initializer that initalizes some values used in the loop body. The second statement is the continuation condition, a boolean expression that is evaluated before the execution of the loop body is allowed. If the condition fails, the loop statement terminates. The third statement is the advance statement. It is performed after the completion of the execution of the body of the loop, and before the continuation condition is evaluated, and is typically used to advance to the next item that the loop should process.

This all looks very confusing, so let us see an example, a method that computes the sum of all elements in an ArrayList<Integer>:

// compute the sum of all intergers in the given list

int sumAll(ArrayList<Integer> arlist){

int result = 0; // we start with the base value

for (int index = 0; // traverse the arlist starting at index 0

index < arlist.size() // stop when all elements have been seen

index = index + 1){ // advance to the next element

result = result + arlist.get(index); // update the current sum

}

return result; // return the final sum

}

We see that the structure of this method is very similar to our loop methods discussed earlier, one just has to understand where to locate all the relevant parts. The base value is 0, the update function is just plain addition, we start to traverse the given ArrayList at the index = 0, the continuation condition checks whether the index is still valid, and the advance statement adds one to the index, thus pointing to the next element of the ArrayList.

Let us summarize the key components of loop methods:

the BASE value -> the value that should be produced if the given data set is empty
the UPDATE method -> the computation that consumes the current accumulated value and the current element of the data set and produces the updated accumulated value
the INITIALIZATION OF TRAVERSAL that provides a control over the loop iterations (typically sets up access to the first element to be processed.
the CONTINUATION CONDITION that determines whether the loop body should be executed, or whether the loop should proceed to returning the final result
the ADVANCE the clause, technique, or statement that typically advances the access to the next element to be processed.

To better illustrate the use of the for loop construct, here is a version of the fold method that consumes an ArrayList and accesses directly the elements of the ArrayList. Using this method we can make changes to the contents of the ArrayList. However, we should be very careful, if the changes involve removing or adding elements to the ArrayList, as that affects what element is referenced by the current value of the index.

/**

* Apply the given update function to all elements of the given

* <code>ArrayList</code>.

* For the empty list just return the given base value.

* @param f the function that computes the updated accumulator

* value from the current <code>ArrayList</code> element and

* the current value of the accumulator

* @param base the initial value of the accumulator

* @returnurn the updated value of the accumulator

static <R, T> R foldForArList(ArrayList<T> arlist, FunTR2R<T, R> f, R base){

R acc = base;

T t; // local variable to hold the current element

for (int index = 0; index < arlist.size(); index = index + 1){

t = arlist.get(index); // retrieve the current element

acc = f.apply(t, acc);

}

return acc;

}

We do not show all the tests, just the last set, as nothing changes in the method invocation or the expected results:

t.checkExpect(Algorithms.foldForArList(arlistMix, append, ""),

"hellohiarrivedercibye");

t.checkExpect(Algorithms.foldForArList(arlistShort, append, ""),

"hibye");

t.checkExpect(Algorithms.foldForArList(arlistLong, append, ""),

"hellociaoarrivedercialoha");

Here is a problem that could not be implemented using the for-each loop control that relies on the use of the Iterator:

// EFFECT: Change every String in the given ArrayList to lower case

void mapToLOwerCase(ArrayList<String> arlist){

String s;

for(int index = 0; index < arlist.size(); index = index + 1){

s = arlist.get(index);

arlist.set(index, s.toLowerCase());

}

and here is the test for it:

/** an <code>ArrayList</code> of <code>String</code>-s of mixed lengths */

ArrayList<String> arlistMix = new ArrayList<String>(

Arrays.asList("hello", "hi", "arrivederci", "bye"));

/** an <code>ArrayList</code> of <code>String</code>-s of mixed lengths */

ArrayList<String> arlistMixCase = new ArrayList<String>(

Arrays.asList("heLLo", "Hi", "ArriveDerci", "BYE"));

void resetArlistMixCase(){

arlistMixCase = new ArrayList<String>(

Arrays.asList("heLLo", "Hi", "ArriveDerci", "BYE"));

}

/**

* Test using map to mutate each <code>String</code>-s

* in a list of <code>String</code>-s

* @param t the <code>Tester</code> that runs the tests

void testMapToLowerCase(Tester t){

this.resetArlistMixCase();

Algorithms.mapToLowerCase(this.arlistMixCase);

t.checkExpect(this.arlistMixCase, this.arlistMix);

}

This method does not produce anything, its job is to mutate the existing data set. But when we use the Iterator we have no access to the element of the given ArrayList, we cannot replace it with another item.

Java loop controls: while statement

Another Java loop conrol statement is while loop. It performs the same tasks as the for loop, but the different parts that control the loop traversal are organized differently.

Here is our first example, the sum of all numbers, rewritten using the while loop control:

/**

* Apply the given update function to all elements of the given

* <code>ArrayList</code>.

* For the empty list just return the given base value.

* @param f the function that computes the updated accumulator

* value from the current <code>ArrayList</code> element and

* the current value of the accumulator

* @param base the initial value of the accumulator

* -return the updated value of the accumulator

static <R, T> R foldWhileArList(ArrayList<T> arlist, FunTR2R<T, R> f, R base){

R acc = base;

T t; // local variable to hold the current element

int index = 0; // the initial index value

while (index < arlist.size()){

t = arlist.get(index); // retrieve the current element

acc = f.apply(t, acc);

index = index + 1; // advance the index to the next element

}

return acc;

}

All the parts from the previous example are there. The three parts of the for loop control are no longer all in one place. The initialization statement that initializes the index to zero appears before the while loop control, the continuation condition is the same as before, but is the only clause of the while control, and the advance statement that increments the index by one is a standalone statement at the end of the body of the loop.

In some ways, it is easier to understand how the while loop control functions, but omitting the advance statement is a very common mistake programmers make.

Here is the classical orMap and andMap written using the while loop control. It uses a simpler function object than the earlier fold - the Predicate interface represents a method that consumes an object of the type T and produces a boolean result.

Here is the interface definition and a class that implements it:

/**

* to represent a predicate that verifies some property

* of the object of the type <code>T</code>

* @param <T>the type <code>T</code> of the given object

interface Predicate<T>{

public boolean select(T t);

}

/**

* to represent a predicate that determines whether the given

* <code>String</code> is shorter than the specified limit

class IsShort implements Predicate<String>{

/** the specified limit */

int limit;

IsShort(int limit){

this.limit = limit;

}

public boolean select(String s){

return s.length() < limit;

}

as well as an instance of this class we can use in out computations:

/** function object: check if the given String-s is shorter than limit */

Predicate<String> isShort = new IsShort(4);

Here are the definitions of the orMap and the andMap methods (defined again in our Algorithms class):

/**

* Is there a <code>String</code>-s in the given <code>ArrayList</code>

* that satisfies the given predicate?

* @param arlist the given <code>ArrayList</code>

* @param pred the given <code>Predicate<T></code>

* -return true if at least one element satisfies the predicate

static boolean orMap(ArrayList<String> arlist, Predicate<String> pred){

int index = 0;

while(index < arlist.size()){

if (pred.select(arlist.get(index)))

return true;

index = index + 1;

}

return false;

}

/**

* Does every <code>String</code>-s in the given <code>ArrayList</code>

* satisfy the given predicate?

* @param arlist the given <code>ArrayList</code>

* @param pred the given <code>Predicate<T></code>

* @return true if every element satisfies the predicate

static boolean andMap(ArrayList<String> arlist, Predicate<String> pred){

int index = 0;

while(index < arlist.size()){

if (!pred.select(arlist.get(index)))

return false;

index = index + 1;

}

return true;

}

and finally, the examples/tests using the same data as before:

t.checkExpect(Algorithms.orMap(arlistMix, isShort), true);

t.checkExpect(Algorithms.orMap(arlistShort, isShort), true);

t.checkExpect(Algorithms.orMap(arlistLong, isShort), false);

t.checkExpect(Algorithms.andMap(arlistMix, isShort), false);

t.checkExpect(Algorithms.andMap(arlistShort, isShort), true);

t.checkExpect(Algorithms.andMap(arlistLong, isShort), false);

Java loop controls: do-while statement

The last variant of loop conrtol statements that Java provides is do-while. It defers the testing of the continuation condition until after the loop bodey has been executed, guaranteeing that the body of the loop will be performed at least once. Here is an example of its use:

// compute the sum of all intergers in the given list

int sumAllDoWhile(ArrayList<Integer> arlist){

int result = 0; // we start with the base value

int index = 0; // traverse the arlist starting at index 0

if (arlist.size() > 0){

do{

result = result + arlist.get(index); // update the current sum

index = index + 1; // advance to the next element

// stop when all elements have been seen

} while(index < arlist.size());

}

return result; // return the final sum

}