2.7.1. The Filtering Pattern¶

The filtering (or simply, filter) pattern is exemplified below. In the example on the right, JavaScript’s mod operator % is used to test whether or not an integer is even.

1 / 5 Settings

<<<>>>

Both keepPositive and keepEven use very similar patterns of computation. Given a list ns, they return a new list by applying a boolean-valued "filtering" function (i.e., isPos for keepPositive and isEven for keepEven) to every element of the given list. This is done by applying the filtering function to the head of the list and, if that value passes the filter test, then consing it onto what recursion returns from the tail of the list. This pattern is highlighted in red below.

1. -1
2. -8
3. 4
4. 3

ns

1. 4
2. 3

keepPositive

returns:

1. -8
2. 4

keepEven

returns:

The filtering abstraction

• var isPos = function (n) {
• return fp.isGT(n, 0);
• };
• var keepPositive = function (ns) {
• if (fp.isNull(ns))
• return [ ];
• else if (isPos(fp.hd(ns)))
• return fp.cons(fp.hd(ns),
• keepPositive(fp.tl(ns)));
• else
• return keepPositive(fp.tl(ns));
• };
• keepPositive( [-1, -8, 4, 3] );

• var isEven = function (n) {
• return fp.isZero(n % 2);
• };
• var keepEven = function (ns) {
• if (fp.isNull(ns))
• return [ ];
• else if (isEven(fp.hd(ns)))
• return fp.cons(fp.hd(ns),
• keepEven(fp.tl(ns)));
• else
• return keepEven(fp.tl(ns));
• };
• keepEven( [-1, -8, 4, 3] );

• var filter = function (pred,ns) {
• if (fp.isNull(ns))
• return [ ];
• else if (pred(fp.hd(ns)))
• return fp.cons(fp.hd(ns),
• filter(pred,fp.tl(ns)));
• else
• return filter(pred,fp.tl(ns));
• }
• filter(isPos, [-1, -8, 4, 3] );
• filter(function (n) { return fp.isZero(n % 2); },
• [-1, -8, 4, 3] );

Saving...
Server Error
Resubmit

Note that, with curry, we could use the filter function to actually create the functions keepPositive and keepEven.

> var keepPositive = fp.curry(filter)(function (n) { return fp.isGT(n,0); });
> var keepEven = fp.curry(filter)(function (n) { return fp.isZero(n % 2); });

This illustrates the function-creating powers of currying. It allows us to not only replicate the behavior of individual functions such as keepPositive and keepEven, but also to replicate the functions themselves without ever having to write their code.

The first problem below deals with the filtering pattern.

2.7.2. The Folding/Reduce Pattern¶

To discover our next pattern, recall that, in the section Using Helpers to Write reverse and split Functions, we used a helper function with an accumulator to perform a cons operation prior to making a recursive call instead of after returning from a recursive call. Keep that in mind as you look for the commonality in the following two examples.

1 / 5 Settings

<<<>>>

Both sum and reverse have helper functions with an accumulator that use a nearly identical pattern of computation. That helper function takes an operation (i.e., fp.add for sum and fp.cons for reverse) and updates the accumulator by applying the operation to the head of the list and the accumulator to create a "bigger" accumulator that is passed in to the recursive call. This pattern is highlighted in red below.

1. 3
2. 2
3. 4
4. 1

ns

1. 10

sum

returns:

1. 1
2. 4
3. 2
4. 3

reverse

returns:

The reduce abstraction

• var sum = function (ns) {
• var helper = function (ns,a) {
• if (fp.isNull(ns))
• return a;
• else
• return helper(fp.tl(ns),
• fp.add(a,fp.hd(ns)));
• };
• return helper(ns,0);
• };
• sum ( [3, 2, 4, 1] );

• var reverse = function (ns) {
• var helper = function (ns,a) {
• if (fp.isNull(ns))
• return a;
• else
• return helper(fp.tl(ns),
• fp.cons(fp.hd(ns),a));
• };
• return helper(ns,[]);
• };
• reverse ( [3, 2, 4, 1] );

• var reduce = function (f,ns,acc) {
• if (fp.isNull(ns))
• return acc;
• else
• return reduce(f,fp.tl(ns),
• f(acc,fp.hd(ns)));
• };
• var sum = function (ns) { return reduce(fp.add,ns,0); };
• var reverse = function (ns) {
• return reduce( // flip parameters
• function (a,n) {
• return fp.cons(n,a); },
• ns,
• []
• );
• };

Saving...
Server Error
Resubmit

The reduce function we have defined in the previous examples applies its helper function f to produce the accumulated value acc in left-to-right order as it works through the list. Moreover, it does this in what is known as tail-recursive fashion because the helper function f is applied within the arguments to the recursive call, not to the result being returned from the recursive call. This left-to-right order was essential for the definition of reverse to work correctly. For sum, it was inconsequential because of the commutative property of addition. We will return to a more extensive discussion of tail-recursive functions in the section on continuation passing style.

We could also define a similar function that applies the helper function in right-to-left order as it works through the list. This is illustrated in the next set of examples.

1 / 6 Settings

<<<>>>

Both subRt and append use a nearly identical pattern of computation. They apply an operation (i.e., fp.sub for subRt and fp.cons for append) to the head of the list and the result obtained from a recursive call on the tail of the list. This pattern is highlighted in red below.

1. 1
2. 3
3. 2

l1

1. 1
2. 2
3. 3

l2

1. 0

subRt(l1)

returns:

1. 2

subRt(l2)

returns:

1. 1
2. 3
3. 2
4. 1
5. 2
6. 3

append(l1,l2)

returns:

The reduceRight abstraction

• var subRt = function (ns) {
• if (fp.isNull(ns)) {
• return 0;
• } else {
• return fp.sub(fp.hd(ns),
• subRt(fp.tl(ns)));
• }
• };
• subRt(l1)
• subRt(l2)

• var append = function (l1,l2) {
• if (fp.isNull(l1)) {
• return l2;
• } else {
• return fp.cons(fp.hd(l1),
• append(fp.tl(l1), l2));
• }
• };
• append(l1, l2);

• var reduceRight = function (f,ns,acc) {
• if (fp.isNull(ns))
• return acc;
• else
• return f( fp.hd(ns),
• reduceRight(f,fp.tl(ns),acc) );
• };
• var subRt = function (ns) {
• return reduceRight(fp.sub, ns, 0); };
• var append = function (l1,l2) {
• return reduceRight(fp.cons, l1, l2); };

Saving...
Server Error
Resubmit

Note that the reduceRight function expects the function we pass in for the operation that “accumulates” values to have its first parameter represent the head of the list, that is, the “next” value to be accumulated. Its second parameter is consequently the accumulator. This is the opposite of reduce, which expected a function that had the first parameter playing the role of the accumulator, and its second being the “next value to be accumulated”. This emphasizes the right versus left associativity of the two patterns.

Also note that, because reduce captures the accumulation pattern as we described it in the section on helper functions, the accumulator has undergone all the computations necessary to achieve the final answer by the time the end of the list is reached. This is not true of reduceRight since it applies its function parameter f to the result of making the recursive call instead of applying recursion to the result of applying f. The acc parameter that reduce takes is a true accumulator, which builds up its values on the descent into recursion, so that all the necessary computation is completed by the time the base case is reached. The acc parameter that reduceRight takes is merely a starting point for the accumulation of values that must be computed as we recursively ascend from reaching the base level.

The following problem deals with the reduce patterns described above.

2.7.3. Practice with the Mapping and Reduce Patterns¶

The following problem uses both the mapping and the reduce patterns.

2.7.4. More Practice with the Reduce Pattern¶

The following problem will give you intensive practice with the reduce pattern. This problem is randomized and must be solved three times in a row.