2.2.1. Recursive List Processing (1)¶

In the previous section, we introduced three predicates that are part of the fp module -- isEq, isZero, and isNull. We will now introduce some additional predicates and arithmetic functions that we will then use to write recursive list-processing functions, including sum, isMember, removeFirst, and subst

First, to check whether something is a list or not, you must use the isList function:

> fp.isList( [ ] )
true
> fp.isList( [1,2,3] )
true
> fp.isList( 1 )
false

Second, the two helper functions add and sub perform the addition and subtraction, respectively, of their two integer arguments:

> fp.add(2,3)
5
> fp.sub(2,3)
-1

Third, the two predicates isLT and isGT test whether their first argument is less than or greater than their second argument, respectively:

> fp.isGT(2,3)
false
> fp.isLT(2,3)
true

We're now ready write a recursive sum function that takes in an integer list and returns the sum of all of the values in the input list.

> var fp = require('./fp')
> sum( [ 1, 2, 3 ] )
6
> sum( [ ] )
0
> sum( [ 1, -2, 3, -4] )
-2

When we design a recursive algorithm, we must keep in mind the recursive BNF definition of integer lists:

Following the two paths for a <list_of_ints> in this grammar -- one for the empty list and one for a non-empty list leads us to structure a sum function as:

var sum = function (ns) {
             if ( SOME TEST ) {
                return SOMETHING;
             } else {
                return SOMETHING ELSE;
             }
          }

Think about how to complete this function and then try the following review problem, which uses similar recursive list-processing logic. Note that this problem is randomized. You must solve it correctly three times in a row to earn the point associated with it.

2.2.2. Recursive List Processing (2)¶

Next consider a function isMember that takes in an integer and an integer list and returns true if and only if its first argument is a member of the second argument:

> var fp = require('./fp')
> isMember( 2, [ 1, 2, 3 ] )
true
> isMember( 4, [ 1, 2, 3 ] )
false
> isMember( 2, [ 1, [ 2, 3 ] ] )
false

Keep in mind the recursive definition of integer lists:

Following that recursive definition design a recursive algorithm for isMember using the template provided below:

var isMember = function (n,ns) {
                  if ( SOME TEST ) {
                     return SOMETHING;
                  } else {
                     return SOMETHING ELSE;
                  }
               }

Once you have the logic designed for isMember, design a similar list-processing function removeFirst that takes in an integer \(n\) and an integer list \(l\) and returns a list identical to \(l\) but with the first occurrence of \(n\) removed:

> var fp = require('./fp')
> removeFirst(3,[1,2,3])
[ 1, 2 ]
> removeFirst(4,[1,2,3])
[ 1, 2, 3 ]
> removeFirst(2,[1,2,3,2])
[ 1, 3, 2 ]

If you again follow the recursive BNF description for a <list_of_ints>, you will find that the appropriate template for your removeFirst function looks like:

var removeFirst = function (n,ns) {
                     if ( SOME TEST ) {
                        return SOMETHING;
                     } else {
                        DO A BIT MORE WORK;
                     }
               }

Once you have the correct logic for removeFirst, consider the following review problem, which asks you to slightly modify removeFirst.

2.2.3. Recursive List Processing (3)¶

As a final example in this section consider a function that takes in two integers \(n\) (for ’new’) and \(o\) (for ’old’) and an integer list \(l\) and returns a list identical to \(l\) except that all occurrences of \(o\) in \(l\) have been replaced by \(n\):

> var fp = require('./fp')
> subst(10,1,[1,2,3,2,1])
[ 10, 2, 3, 2, 10 ]
> subst(50,5,[1,2,3])
[ 1, 2, 3 ]
> subst(10,1,[[1,2],3])
[ [ 1, 2 ], 3 ]

Again the template for the subst function follows the pattern established by the BNF grammar for a <list_of_ints>:

var subst = function (n,ns) {
               if ( SOME TEST ) {
                  return SOMETHING;
               } else {
                  DO A BIT MORE WORK;
               }
            }

When you have established the correct logic for this template, consider the final review problem for this section, which asks you to slightly modify the subst function.