5.6 Functions on Lists

Armed with an understanding of (1) the core computational model in Lisp— λ-calculus; (2) the recursive specifications of data structures and recursive definitions of algorithms; and (3) the representation of lists in memory, we are prepared to develop functions that operate on data structures.

5.6.1 A List length Function

Consider the following function length1,⁸ which given a list, returns the length of the list:

The built-in Scheme predicate null? returns true if its argument is an empty list and false otherwise. The built-in Scheme predicate empty? can be used for this purpose as well.

Notice that the pattern of the recursion in the preceding function is similar to that used in the pow function in Section 5.4.1. Defining functions in Lisp can be viewed as pattern application—recognizing the pattern to which a problem fits, and then adapting that pattern to the details of the problem (Friedman and Felleisen 1996a).

5.6.2 Run-Time Complexity: append and reverse

A built-in Scheme function that is helpful for illustrating issues of efficiency with lists is append:⁹

Intuitively, append works by recursing through the first list and consing the car of each progressively smaller, first list to the appendage of the cdr of each progressively smaller list with the second list. Recall that the cons function is a constant operation—it allocates space for two pointers and copies the pointers of its two arguments into those fields—and recursion is not involved. The append function works differently: It deconstructs the first list and creates a new cons cell for each element. In other words, append makes a complete copy of its first argument. Therefore, the run-time complexity of append is linear [or ] in the size of the first list. Unlike the first list, which is not contained in the resulting list (i.e., it is automatically garbage collected), the cons cell of the second list remains intact and is present in the resulting appended list—it is the cdr of the list whose car is the last element of the first list. To reiterate, cons and append are not the same function. To construct a proper list, cons accepts an atom and a list. To do the same, append accepts a list and a list.

While the running time of append is not constant like that of cons, it is also not polynomial [e.g., ]. However, the effect of the less efficient append function is compounded in functions that use append where the use of cons would otherwise suffice. For instance, consider the following reverse¹⁰ function, which accepts a list and returns the list reversed:

Using the strategy discussed previously for developing recursive solutions to problems, we know that the reverse of the empty list is the empty list. To extend the reverse of a list of items to that of n items, we append the remaining item as a list to the reversed list of items. For instance, if we want to reverse a list , we assume we have the reversed cdr of the original list [i.e., the list ] and we append the car of the original list as a list [i.e., ] to that list [i.e., resulting in ]. The following example illustrates how, in reversing the list , the expression in the else clause is expanded (albeit implicitly on the run-time stack):

Notice that rotating this expansion 90 degrees left forms a parabola showing how the run-time stack grows until it reaches the base case of the recursion (line 6) and then shrinks. This is called recursive-control behavior and is discussed in more detail in Chapter 13.

As this expansion illustrates, reversing a list of n items requires calls to append. Recall that the running time of append is linear, . Therefore, the run-time complexity of this definition of reverse1 is , which is unsettling. Intuitively, to reverse a list, we need pass through it only once; thus, the upper bound on the running time should be no worse than . The difference in running time between cons and append is magnified when append is employed in a function like reverse1, where cons would suffice. This suggests that we should never use append where cons will suffice (see Design Guideline 3: Efficient List Construction). We rewrite reverse1 using only cons and no appends in a later example. Before doing so, however, we make some instructional observations on this initial version of the reverse1 function.

• The expression in the previous definition of append can be replaced by without altering the semantics of the function:

  

  The list function accepts an arbitrary number of arguments and creates a list of those arguments. The list function is not the same as the append function:

  

  The function append accepts only arguments that are proper lists. In contrast, the function list accepts any values as arguments (atoms or lists). The list function is not to be confused with the built-in Scheme predicate list?, which returns true if its argument is a proper list and false otherwise:

  

  

  Furthermore, the list? predicate is not to be confused with the pair? predicate, which returns true if its argument is a cons cell, even if not a proper list, and false otherwise:

  

• Scheme uses the pass-by-value parameter-passing mechanism (sometimes called pass-by-copy). This is the same parameter-passing mechanism used in C, with which readers may be more familiar. The following session illustrates the use of pass-by-value in Scheme:

  

  A consequence of pass-by-value semantics for the reverse1 function is that after the function returns, the original list remains unchanged; in other words, it has the same order it had before the function was called. Parameter-passing mechanisms are discussed in detail in Chapter 12.

• A consequence of the typeless nature of Lisp is that most functions are polymorphic, without explicit operator overloading. Therefore, not only can the reverse1 function reverse a list of numbers or strings, but it can also reverse a list of employee records or pixels, or reverse a list involving a combination of all four types. It can even reverse a list of lists.

5.6.3 The Difference Lists Technique

If we examine the pattern of recursion used in the definition of our reverse1 function, we notice that the function mirrors both the recursive specification of the problem and the recursive definition of a reversed list. We were able to follow our guidelines for developing recursive algorithms in defining it. Improving the run-time complexity of reverse1 involves obviating the use of append through amethodcalledthe difference lists technique (see Design Guideline 7: Difference Lists Technique). (We revisit the difference lists technique in Section 13.7, where we introduce the concept of tail recursion.) Using the difference lists technique compromises the natural correspondence between the recursive specification of a problem and the recursive solution to it. Compromising this correspondence and, typically, the readability of the function, which follows from this break in symmetry, for the purposes of efficiency of execution is a theme that recurs throughout this text. We address this trade-off in more detail in Chapter 13, where a reasonable solution to the problem is presented.

In the absence of side effects, which are contrary to the spirit of functional programming, the only ways for successive calls to a recursive function to share and communicate data is through return values (as is the case in the reverse1 function) or parameters. The difference lists technique involves using an additional parameter that represents the solution (e.g., the reversed list) computed thus far. A solution to the problem of reversing a list using the difference lists technique is presented here:

Notice that this solution involves the use of a helper function rev, which ensures that the signature of the original function reverse1 remains unchanged. The additional parameter is rl, which stands for reversed list. When rev is first called on line 5, the reversed list is empty. On line 11, we grow that reversed list by consing each element of the original list into rl until the original list l is empty (i.e., the base case on line 10), at which point we simply return rl because it is the completely reversed list at that point. Thus, the reversed list is built as the original list is traversed. Notice that append is no longer used.

Conducting a similar run-time analysis of this version of reverse1 as we did with the prior version, we see:

Now the running time of the function is linear [i.e., ] in the size of the list to be reversed. Notice also that, unlike in the original function, when the expansion is rotated 90 degrees left, a rectangle is formed, rather than a parabola. Thus, the improved version of reverse1 is more efficient not only in time, but also in space. An unbounded amount of memory (i.e., stack) is required for the first version of reverse1. Specifically, we require as many frames on the run-time stack as there are elements in the list to be reversed. Unbounded memory is required for the first version because each function call in the first version must wait (on the stack) for the recursive call it invokes to return so that it can complete the computation by to the intermediate result that is returned:

The same is not true for the second version. The second version only requires a constant memory size because no pending computations are waiting for the recursive call to return:

Formally, this is because the recursive call to rev is in tail position or is a tail call, and the difference lists version of reverse1 is said to use tail recursion (Section 13.7).

While working through these examples in the Racket interpreter, notice that the functions can be easily tested in isolation (i.e., independently of the rest of the program) with the read-eval-print loop. For instance, we can test rev independently of reverse1. This fosters a convenient environment for debugging, and facilitates a process known as interactive or incremental testing. Compiled languages, such as C, in contrast, require test drivers in main (which clutter the program) to achieve the same.

Programming Exercises for Section 5.6

Exercise 5.6.1 Define a Scheme function member1? that accepts only an atom a and a list of atoms lat, in that order, and returns #t if the atom is an element of the list and #f otherwise.

Exercise 5.6.2 Define a Scheme function remove that accepts only a list and an integer i as arguments and returns another list that is the same as the input list, but with the ith element of the input list removed. If the length of the input list is less than i, return the same list. Assume that i = 1 refers to the first element of the list.

Examples:

Exercise 5.6.3 Define a Scheme function called makeset that accepts only a list of integers as input and returns the list with any repeating elements removed. The order in which the elements appear in the returned list does not matter, as long as there are no duplicate elements. Do not use any user-defined auxiliary functions, except the built-in Scheme member function.

Examples:

Exercise 5.6.4 Define a Scheme function cycle that accepts only a list and an integer i as arguments and cycles the list i times. Do not use any user-defined auxiliary functions and do not use the difference lists technique (i.e., you may use append).

Examples:

Exercise 5.6.5 Redefine the Scheme function cycle from Programming Exercise 5.6.4 using the difference lists technique. You may use append, but only in a base so that it is only ever applied once.

Exercise 5.6.6 Define a Scheme function transpose that accepts a list of atoms as its only argument and returns that list with adjacent elements transposed. Specifically, transpose accepts an input list of the form and returns a list of the form as output. If n is odd, e_n will continue to be the last element of the list. Do not use any user-defined auxiliary functions and do not use append.

Examples:

Exercise 5.6.7 Define a Scheme function oddevensum that accepts only a list of integers as an argument and returns a pair consisting of the sum of the odd and even positions of the list. Do not use any user-defined auxiliary functions.

Examples:

Exercise 5.6.8 Define a Scheme function intersect that returns the set intersection of two sets represented as lists. Do not use any built-in Scheme functions or syntactic forms other than cons, car, cdr, or, null?, and member.

Examples:

Exercise 5.6.9 Consider the following description of a function mystery. This function accepts a non-empty list of numbers in which no number is greater than its own index (first element is at index 1), and returns a list of numbers of the same length. Each number in the argument is treated as a backward index starting from its own position to a point earlier in the list of numbers. The result at each position is found by counting backward from the current position according to the index.

Examples:

Define the mystery function in Scheme.

Exercise 5.6.10 Define a Scheme function reverse* that accepts only an S-list as an argument and returns not only that S-list reversed, but also all sublists of that S-list reversed as well, and sublists of sublists, reversed, and so on.

Examples:

8. When defining a function in Scheme with the same name as a built-in function (e.g., length), we use the name of the built-in function with a 1 appended to the end of it as the name of the user-defined function (e.g., length1), where appropriate, to avoid any confusion and/or clashes (in the interpreter) with the built-in function.

9. The function append is built into Scheme and accepts an arbitrary number of arguments, all of which must be proper lists. The version we define is named append1.

10. The function reverse is built into Scheme. The version we define is named reverse1.