Register

# 2.2. Functional Programming - Developing basic, recursive list-processing functions¶

## 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:

$\begin{split}\begin{eqnarray*} <list\_of\_ints> &::=& \epsilon \\ & | & <int> <list\_of-\_ints> \\ \end{eqnarray*}\end{split}$

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:

$\begin{split}\begin{eqnarray*} <list\_of\_ints> &::=& \epsilon \\ & | & <int> <list\_of\_ints> \\ \end{eqnarray*}\end{split}$

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.