GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

No menu could be recovered. Follow the blue links in the page.

This view

  • Original page
  • New address

GeezerVison is showing sicp.sourceacademy.org — 2.2.3 Sequences as Conventional Interfaces - SICP Comparison Edition

SICP — Scheme/JS Structure and Interpretation of Computer Programs — Comparison Edition
 
Foreword
Foreword to Structure and Interpretation of Computer Programs, 1984
Preface
Prefaces to Structure and Interpretation of Computer Programs, 1996 & 1984
Acknowledgments
➤ ▼ 1 Building Abstractions with Procedures Functions
➤ ▼ 1.1 The Elements of Programming
1.1.1 Expressions
1.1.2 Naming and the Environment
1.1.3 Evaluating Combinations Operator Combinations
1.1.4 Compound Procedures Functions
1.1.5 The Substitution Model for Procedure Function Application
1.1.6 Conditional Expressions and Predicates
1.1.7 Example: Square Roots by Newton's Method
1.1.8 Procedures Functions as Black-Box Abstractions
➤ ▼ 1.2 Procedures Functions and the Processes They Generate
1.2.1 Linear Recursion and Iteration
1.2.2 Tree Recursion
1.2.3 Orders of Growth
1.2.4 Exponentiation
1.2.5 Greatest Common Divisors
1.2.6 Example: Testing for Primality
➤ ▼ 1.3 Formulating Abstractions with Higher-Order Procedures Functions
1.3.1 Procedures Functions as Arguments
1.3.2 Constructing Procedures using Lambda Constructing Functions using Lambda Expressions
1.3.3 Procedures Functions as General Methods
1.3.4 Procedures Functions as Returned Values
➤ ▼ 2 Building Abstractions with Data
➤ ▼ 2.1 Introduction to Data Abstraction
2.1.1 Example: Arithmetic Operations for Rational Numbers
2.1.2 Abstraction Barriers
2.1.3 What Is Meant by Data?
2.1.4 Extended Exercise: Interval Arithmetic
➤ ▼ 2.2 Hierarchical Data and the Closure Property
2.2.1 Representing Sequences
2.2.2 Hierarchical Structures
2.2.3 Sequences as Conventional Interfaces
2.2.4 Example: A Picture Language
➤ ▼ 2.3 Symbolic Data
2.3.1 Quotation Strings
2.3.2 Example: Symbolic Differentiation
2.3.3 Example: Representing Sets
2.3.4 Example: Huffman Encoding Trees
➤ ▼ 2.4 Multiple Representations for Abstract Data
2.4.1 Representations for Complex Numbers
2.4.2 Tagged data
2.4.3 Data-Directed Programming and Additivity
➤ ▼ 2.5 Systems with Generic Operations
2.5.1 Generic Arithmetic Operations
2.5.2 Combining Data of Different Types
2.5.3 Example: Symbolic Algebra
➤ ▼ 3 Modularity, Objects, and State
➤ ▼ 3.1 Assignment and Local State
3.1.1 Local State Variables
3.1.2 The Benefits of Introducing Assignment
3.1.3 The Costs of Introducing Assignment
➤ ▼ 3.2 The Environment Model of Evaluation
3.2.1 The Rules for Evaluation
3.2.2 Applying Simple Procedures Functions
3.2.3 Frames as the Repository of Local State
3.2.4 Internal Definitions Declarations
3.2.5 CSE Machine
➤ ▼ 3.3 Modeling with Mutable Data
3.3.1 Mutable List Structure
3.3.2 Representing Queues
3.3.3 Representing Tables
3.3.4 A Simulator for Digital Circuits
3.3.5 Propagation of Constraints
➤ ▼ 3.4 Concurrency: Time Is of the Essence
3.4.1 The Nature of Time in Concurrent Systems
3.4.2 Mechanisms for Controlling Concurrency
➤ ▼ 3.5 Streams
3.5.1 Streams Are Delayed Lists
3.5.2 Infinite Streams
3.5.3 Exploiting the Stream Paradigm
3.5.4 Streams and Delayed Evaluation
3.5.5 Modularity of Functional Programs and Modularity of Objects
➤ ▼ 4 Metalinguistic Abstraction
➤ ▼ 4.1 The Metacircular Evaluator
4.1.1 The Core of the Evaluator
4.1.2 Representing Expressions Components
4.1.3 Evaluator Data Structures
4.1.4 Running the Evaluator as a Program
4.1.5 Data as Programs
4.1.6 Internal Definitions Declarations
4.1.7 Separating Syntactic Analysis from Execution
➤ ▼ 4.2 Variations on a Scheme: Lazy Evaluation
4.2.1 Normal Order and Applicative Order
4.2.2 An Interpreter with Lazy Evaluation
4.2.3 Streams as Lazy Lists
➤ ▼ 4.3 Variations on a Scheme: Nondeterministic Computing
4.3.1 Amb and Search Search and amb
4.3.2 Examples of Nondeterministic Programs
4.3.3 Implementing the Amb amb Evaluator
➤ ▼ 4.4 Logic Programming
4.4.1 Deductive Information Retrieval
4.4.2 How the Query System Works
4.4.3 Is Logic Programming Mathematical Logic?
4.4.4 Implementing the Query System
➤ ▼ 5 Computing with Register Machines
➤ ▼ 5.1 Designing Register Machines
5.1.1 A Language for Describing Register Machines
5.1.2 Abstraction in Machine Design
5.1.3 Subroutines
5.1.4 Using a Stack to Implement Recursion
5.1.5 Instruction Summary
➤ ▼ 5.2 A Register-Machine Simulator
5.2.1 The Machine Model
5.2.2 The Assembler
5.2.3 Generating Execution Procedures for Instructions Instructions and Their Execution Functions
5.2.4 Monitoring Machine Performance
➤ ▼ 5.3 Storage Allocation and Garbage Collection
5.3.1 Memory as Vectors
5.3.2 Maintaining the Illusion of Infinite Memory
➤ ▼ 5.4 The Explicit-Control Evaluator
5.4.1 The Core of the Explicit-Control Evaluator The Dispatcher and Basic Evaluation
5.4.2 Sequence Evaluation and Tail Recursion Evaluating Function Applications
5.4.3 Conditionals, Assignments and Definitions Blocks, Assignments, and Declarations
5.4.4 Running the Evaluator
➤ ▼ 5.5 Compilation
5.5.1 Structure of the Compiler
5.5.2 Compiling Expressions Components
5.5.3 Compiling Combinations Applications and Return Statements
5.5.4 Combining Instruction Sequences
5.5.5 An Example of Compiled Code
5.5.6 Lexical Addressing
5.5.7 Interfacing Compiled Code to the Evaluator
References
About the SICP JS Project
Permalink copied!
2.2.3 Sequences as Conventional Interfaces

In working with compound data, we've stressed how data abstraction permits us to design programs without becoming enmeshed in the details of data representations, and how abstraction preserves for us the flexibility to experiment with alternative representations. In this section, we introduce another powerful design principle for working with data structures—the use of conventional interfaces.

In section 1.3 we saw how program abstractions, implemented as higher-order procedures, functions, can capture common patterns in programs that deal with numerical data. Our ability to formulate analogous operations for working with compound data depends crucially on the style in which we manipulate our data structures. Consider, for example, the following procedure, function, analogous to the count-leaves count_leaves procedure function of section 2.2.2, which takes a tree as argument and computes the sum of the squares of the leaves that are odd:

Original JavaScript
(define (sum-odd-squares tree) (cond ((null? tree) 0) ((not (pair? tree)) (if (odd? tree) (square tree) 0)) (else (+ (sum-odd-squares (car tree)) (sum-odd-squares (cdr tree)))))) function sum_odd_squares(tree) { return is_null(tree) ? 0 : ! is_pair(tree) ? is_odd(tree) ? square(tree) : 0 : sum_odd_squares(head(tree)) + sum_odd_squares(tail(tree)); }
On the surface, this procedure function is very different from the following one, which constructs a list of all the even Fibonacci numbers ${\textrm{Fib}}(k)$, where $k$ is less than or equal to a given integer $n$:
Original JavaScript
(define (even-fibs n) (define (next k) (if (> k n) nil (let ((f (fib k))) (if (even? f) (cons f (next (+ k 1))) (next (+ k 1)))))) (next 0)) function even_fibs(n) { function next(k) { if (k > n) { return null; } else { const f = fib(k); return is_even(f) ? pair(f, next(k + 1)) : next(k + 1); } } return next(0); }

Despite the fact that these two procedures functions are structurally very different, a more abstract description of the two computations reveals a great deal of similarity. The first program

  • enumerates the leaves of a tree;
  • filters them, selecting the odd ones;
  • squares each of the selected ones; and
  • accumulates the results using +, +, starting with 0.
The second program
  • enumerates the integers from 0 to $n$;
  • computes the Fibonacci number for each integer;
  • filters them, selecting the even ones; and
  • accumulates the results using cons, pair, starting with the empty list.

A signal-processing engineer would find it natural to conceptualize these processes in terms of signals flowing through a cascade of stages, each of which implements part of the program plan, as shown in figure 2.13. figure 2.14. In sum-odd-squares, sum_odd_squares, we begin with an enumerator, which generates a signal consisting of the leaves of a given tree. This signal is passed through a filter, which eliminates all but the odd elements. The resulting signal is in turn passed through a map, which is a transducer that applies the square procedure function to each element. The output of the map is then fed to an accumulator, which combines the elements using +, +, starting from an initial 0. The plan for even-fibs even_fibs is analogous.

Original JavaScript
Figure 2.13 The signal-flow plans for the procedures sum-odd-squares (top) and even-fibs (bottom) reveal the commonality between the two programs.
Figure 2.14 The signal-flow plans for the functions sum_odd_squares (top) and even_fibs (bottom) reveal the commonality between the two programs.

Unfortunately, the two procedure definitions function declarations above fail to exhibit this signal-flow structure. For instance, if we examine the sum-odd-squares sum_odd_squares procedure, function, we find that the enumeration is implemented partly by the null? is_null and pair? is_pair tests and partly by the tree-recursive structure of the procedure. function. Similarly, the accumulation is found partly in the tests and partly in the addition used in the recursion. In general, there are no distinct parts of either procedure function that correspond to the elements in the signal-flow description. Our two procedures functions decompose the computations in a different way, spreading the enumeration over the program and mingling it with the map, the filter, and the accumulation. If we could organize our programs to make the signal-flow structure manifest in the procedures functions we write, this would increase the conceptual clarity of the resulting code. program.

Sequence Operations

The key to organizing programs so as to more clearly reflect the signal-flow structure is to concentrate on the signals that flow from one stage in the process to the next. If we represent these signals as lists, then we can use list operations to implement the processing at each of the stages. For instance, we can implement the mapping stages of the signal-flow diagrams using the map procedure function from section 2.2.1:

Original JavaScript
(map square (list 1 2 3 4 5)) (1 4 9 16 25) map(square, list(1, 2, 3, 4, 5)); list(1, 4, 9, 16, 25)

Filtering a sequence to select only those elements that satisfy a given predicate is accomplished by

Original JavaScript
(define (filter predicate sequence) (cond ((null? sequence) nil) ((predicate (car sequence)) (cons (car sequence) (filter predicate (cdr sequence)))) (else (filter predicate (cdr sequence))))) function filter(predicate, sequence) { return is_null(sequence) ? null : predicate(head(sequence)) ? pair(head(sequence), filter(predicate, tail(sequence))) : filter(predicate, tail(sequence)); }
For example,
Original JavaScript
(filter odd? (list 1 2 3 4 5)) (1 3 5) filter(is_odd, list(1, 2, 3, 4, 5)); list(1, 3, 5)

Accumulations can be implemented by

Original JavaScript
(define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))) function accumulate(op, initial, sequence) { return is_null(sequence) ? initial : op(head(sequence), accumulate(op, initial, tail(sequence))); }
Original JavaScript
(accumulate + 0 (list 1 2 3 4 5)) 15 accumulate(plus, 0, list(1, 2, 3, 4, 5)); 15
Original JavaScript
(accumulate * 1 (list 1 2 3 4 5)) 120 accumulate(times, 1, list(1, 2, 3, 4, 5)); 120
Original JavaScript
(accumulate cons nil (list 1 2 3 4 5)) (1 2 3 4 5) accumulate(pair, null, list(1, 2, 3, 4, 5)); list(1, 2, 3, 4, 5)

All that remains to implement signal-flow diagrams is to enumerate the sequence of elements to be processed. For even-fibs, even_fibs, we need to generate the sequence of integers in a given range, which we can do as follows:

Original JavaScript
(define (enumerate-interval low high) (if (> low high) nil (cons low (enumerate-interval (+ low 1) high)))) function enumerate_interval(low, high) { return low > high ? null : pair(low, enumerate_interval(low + 1, high)); }
Original JavaScript
(enumerate-interval 2 7) (2 3 4 5 6 7) enumerate_interval(2, 7); list(2, 3, 4, 5, 6, 7)
To enumerate the leaves of a tree, we can use[1]
Original JavaScript
(define (enumerate-tree tree) (cond ((null? tree) nil) ((not (pair? tree)) (list tree)) (else (append (enumerate-tree (car tree)) (enumerate-tree (cdr tree)))))) function enumerate_tree(tree) { return is_null(tree) ? null : ! is_pair(tree) ? list(tree) : append(enumerate_tree(head(tree)), enumerate_tree(tail(tree))); }
Original JavaScript
(enumerate-tree (list 1 (list 2 (list 3 4)) 5)) (1 2 3 4 5) enumerate_tree(list(1, list(2, list(3, 4)), 5)); list(1, 2, 3, 4, 5)

Now we can reformulate sum-odd-squares sum_odd_squares and even-fibs even_fibs as in the signal-flow diagrams. For sum-odd-squares, sum_odd_squares, we enumerate the sequence of leaves of the tree, filter this to keep only the odd numbers in the sequence, square each element, and sum the results:

Original JavaScript
(define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree))))) function sum_odd_squares(tree) { return accumulate(plus, 0, map(square, filter(is_odd, enumerate_tree(tree)))); }
For even-fibs, even_fibs, we enumerate the integers from 0 to $n$, generate the Fibonacci number for each of these integers, filter the resulting sequence to keep only the even elements, and accumulate the results into a list:
Original JavaScript
(define (even-fibs n) (accumulate cons nil (filter even? (map fib (enumerate-interval 0 n))))) function even_fibs(n) { return accumulate(pair, null, filter(is_even, map(fib, enumerate_interval(0, n)))); }

The value of expressing programs as sequence operations is that this helps us make program designs that are modular, that is, designs that are constructed by combining relatively independent pieces. We can encourage modular design by providing a library of standard components together with a conventional interface for connecting the components in flexible ways.

Modular construction is a powerful strategy for controlling complexity in engineering design. In real signal-processing applications, for example, designers regularly build systems by cascading elements selected from standardized families of filters and transducers. Similarly, sequence operations provide a library of standard program elements that we can mix and match. For instance, we can reuse pieces from the sum-odd-squares sum_odd_squares and even-fibs even_fibs procedures functions in a program that constructs a list of the squares of the first $n+1$ Fibonacci numbers:

Original JavaScript
(define (list-fib-squares n) (accumulate cons nil (map square (map fib (enumerate-interval 0 n))))) function list_fib_squares(n) { return accumulate(pair, null, map(square, map(fib, enumerate_interval(0, n)))); }
Original JavaScript
(list-fib-squares 10) (0 1 1 4 9 25 64 169 441 1156 3025) list_fib_squares(10); list(0, 1, 1, 4, 9, 25, 64, 169, 441, 1156, 3025)
We can rearrange the pieces and use them in computing the product of the squares of the odd integers in a sequence:
Original JavaScript
(define (product-of-squares-of-odd-elements sequence) (accumulate * 1 (map square (filter odd? sequence)))) function product_of_squares_of_odd_elements(sequence) { return accumulate(times, 1, map(square, filter(is_odd, sequence))); }
Original JavaScript
(product-of-squares-of-odd-elements (list 1 2 3 4 5)) 225 product_of_squares_of_odd_elements(list(1, 2, 3, 4, 5)); 225

We can also formulate conventional data-processing applications in terms of sequence operations. Suppose we have a sequence of personnel records and we want to find the salary of the highest-paid programmer. Assume that we have a selector salary that returns the salary of a record, and a predicate programmer? is_programmer that tests if a record is for a programmer. Then we can write

Original JavaScript
(define (salary-of-highest-paid-programmer records) (accumulate max 0 (map salary (filter programmer? records)))) function salary_of_highest_paid_programmer(records) { return accumulate(math_max, 0, map(salary, filter(is_programmer, records))); }
These examples give just a hint of the vast range of operations that can be expressed as sequence operations.[2]

Sequences, implemented here as lists, serve as a conventional interface that permits us to combine processing modules. Additionally, when we uniformly represent structures as sequences, we have localized the data-structure dependencies in our programs to a small number of sequence operations. By changing these, we can experiment with alternative representations of sequences, while leaving the overall design of our programs intact. We will exploit this capability in section 3.5, when we generalize the sequence-processing paradigm to admit infinite sequences.

Exercise 2.33 Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:
Original JavaScript
(define (map p sequence) (accumulate (lambda (x y) ??) nil sequence)) (define (append seq1 seq2) (accumulate cons ?? ??)) (define (length sequence) (accumulate ?? 0 sequence)) function map(f, sequence) { return accumulate((x, y) => $\langle{}$??$\rangle$, null, sequence); } function append(seq1, seq2) { return accumulate(pair, $\langle{}$??$\rangle$, $\langle{}$??$\rangle$); } function length(sequence) { return accumulate($\langle{}$??$\rangle$, 0, sequence); }
Original JavaScript
function map(f, sequence) { return accumulate((x, y) => pair(f(x), y), null, sequence); } function append(seq1, seq2) { return accumulate(pair, seq2, seq1); } function length(sequence) { return accumulate((x, y) => y + 1, 0, sequence); }
Exercise 2.34 Evaluating a polynomial in $x$ at a given value of $x$ can be formulated as an accumulation. We evaluate the polynomial \[ a_{n} x^n +a_{n-1}x^{n-1}+\cdots + a_{1} x+a_{0} \] using a well-known algorithm called Horner's rule, which structures the computation as \[ \left(\cdots (a_{n} x+a_{n-1})x+\cdots +a_{1}\right) x+a_{0} \] In other words, we start with $a_{n}$, multiply by $x$, add $a_{n-1}$, multiply by $x$, and so on, until we reach $a_{0}$.[3] Fill in the following template to produce a procedure function that evaluates a polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged in a sequence, from $a_{0}$ through $a_{n}$.
Original JavaScript
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) ??) 0 coefficient-sequence)) function horner_eval(x, coefficient_sequence) { return accumulate((this_coeff, higher_terms) => $\langle{}$??$\rangle$, 0, coefficient_sequence); }
For example, to compute $1+3x+5x^3+x^5$ at $x=2$ you would evaluate
Original JavaScript
(horner-eval 2 (list 1 3 0 5 0 1)) horner_eval(2, list(1, 3, 0, 5, 0, 1));
Original JavaScript
function horner_eval(x, coefficient_sequence) { return accumulate((this_coeff, higher_terms) => x * higher_terms + this_coeff, 0, coefficient_sequence); }
Exercise 2.35 Redefine count-leaves count_leaves from section 2.2.2 as an accumulation:
Original JavaScript
(define (count-leaves t) (accumulate ?? ?? (map ?? ??))) function count_leaves(t) { return accumulate($\langle{}$??$\rangle$, $\langle{}$??$\rangle$, map($\langle{}$??$\rangle$, $\langle{}$??$\rangle$)); }
Original JavaScript
function count_leaves(t) { return accumulate((leaves, total) => leaves + total, 0, map(sub_tree => is_pair(sub_tree) ? count_leaves(sub_tree) : 1, t)); }
Exercise 2.36 The procedure function accumulate-n accumulate_n is similar to accumulate accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure function to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences
Original JavaScript
((1 2 3) (4 5 6) (7 8 9) (10 11 12)) list(list(1, 2, 3), list(4, 5, 6), list(7, 8, 9), list(10, 11, 12))
then the value of (accumulate-n + 0 s) accumulate_n(plus, 0, s) should be the sequence (22 26 30). list(22, 26, 30). Fill in the missing expressions in the following definition of accumulate-n: accumulate_n:
Original JavaScript
(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init ??) (accumulate-n op init ??)))) function accumulate_n(op, init, seqs) { return is_null(head(seqs)) ? null : pair(accumulate(op, init, $\langle{}$??$\rangle$), accumulate_n(op, init, $\langle{}$??$\rangle$)); }
Original JavaScript
function accumulate_n(op, init, seqs) { return is_null(head(seqs)) ? null : pair(accumulate(op, init, map(x => head(x), seqs)), accumulate_n(op, init, map(x => tail(x), seqs))); }
Exercise 2.37 Suppose we represent vectors $v=(v_{i})$ as sequences of numbers, and matrices $m=(m_{ij})$ as sequences of vectors (the rows of the matrix). For example, the matrix \[ \left[ \begin{array}{llll} 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 6\\ 6 & 7 & 8 & 9\\ \end{array} \right] \]
Original JavaScript
is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). is represented as the following sequence: list(list(1, 2, 3, 4), list(4, 5, 6, 6), list(6, 7, 8, 9))
With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:
(dot-product $v$ $w$) dot_product($v$, $w$) returns the sum $\sum_{i}v_{i} w_{i}$;
(matrix-*-vector $m$ $v$) matrix_times_vector($m$, $v$) returns the vector $t$, where $t_{i} =\sum_{j}m_{ij}v_{j}$;
(matrix-*-matrix $m\ n$) matrix_times_matrix($m$, $n$) returns the matrix $p$, where $p_{ij}=\sum_{k} m_{ik}n_{kj}$;
(transpose )transpose($m$) returns the matrix $n$, where $n_{ij}=m_{ji}$.
We can define the dot product as[4]
Original JavaScript
(define (dot-product v w) (accumulate + 0 (map * v w))) function dot_product(v, w) { return accumulate(plus, 0, accumulate_n(times, 1, list(v, w))); }
Fill in the missing expressions in the following procedures functions for computing the other matrix operations. (The procedure function accumulate-n is defined in accumulate_n is declared in exercise 2.36.)
Original JavaScript
(define (matrix-*-vector m v) (map ?? m)) (define (transpose mat) (accumulate-n ?? ?? mat)) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map ?? m))) function matrix_times_vector(m, v) { return map($\langle{}$??$\rangle$, m); } function transpose(mat) { return accumulate_n($\langle{}$??$\rangle$, $\langle{}$??$\rangle$, mat); } function matrix_times_matrix(m, n) { const cols = transpose(n); return map($\langle{}$??$\rangle$, m); }
Original JavaScript
function matrix_times_vector(m, v) { return map(row => dot_product(row, v), m); } function transpose(mat) { return accumulate_n(pair, null, mat); } function matrix_times_matrix(n, m) { const cols = transpose(m); return map(x => map(y => dot_product(x, y), cols), n); }
Exercise 2.38 The accumulate accumulate procedure function is also known as fold-right, fold_right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, fold_left, which is similar to fold-right, fold_right, except that it combines elements working in the opposite direction:
Original JavaScript
(define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence)) function fold_left(op, initial, sequence) { function iter(result, rest) { return is_null(rest) ? result : iter(op(result, head(rest)), tail(rest)); } return iter(initial, sequence); }
What are the values of
Original JavaScript
(fold-right / 1 (list 1 2 3)) fold_right(divide, 1, list(1, 2, 3));
Original JavaScript
(fold-left / 1 (list 1 2 3)) fold_left(divide, 1, list(1, 2, 3));
Original JavaScript
(fold-right list nil (list 1 2 3)) fold_right(list, null, list(1, 2, 3));
Original JavaScript
(fold-left list nil (list 1 2 3)) fold_left(list, null, list(1, 2, 3));
Give a property that op op should satisfy to guarantee that fold-right fold_right and fold-left fold_left will produce the same values for any sequence.
  1. Original JavaScript
    1.5
  2. Original JavaScript
    0.16666666666666666
  3. Original JavaScript
    [1, [[2, [[3, [null, null]], null]], null]]
  4. Original JavaScript
    [[[null, [1, null]], [2, null]], [3, null]]
We can guarantee that fold_right and fold_left produce the same values for any sequence, if we require that op is commutative and associative. They also produce the same values, if op is just associative and the argument initial is a left and right neutral element with respect to op. fold_right(plus, 0, list(1, 2, 3)); fold_left(plus, 0, list(1, 2, 3));
Exercise 2.39 Complete the following definitions of reverse (exercise 2.18) in terms of fold-right fold_right and fold-left fold_left from exercise 2.38:
Original JavaScript
(define (reverse sequence) (fold-right (lambda (x y) ??) nil sequence)) function reverse(sequence) { return fold_right((x, y) => $\langle{}$??$\rangle$, null, sequence); }
Original JavaScript
(define (reverse sequence) (fold-left (lambda (x y) ??) nil sequence)) function reverse(sequence) { return fold_left((x, y) => $\langle{}$??$\rangle$, null, sequence); }
reverse(list(1, 4, 5, 9, 16, 25)); function reverse(sequence) { return fold_right((x, y) => append(y, list(x)), null, sequence); } function reverse(sequence) { return fold_left((x, y) => pair(y, x), null, sequence); }

Nested Mappings

We can extend the sequence paradigm to include many computations that are commonly expressed using nested loops.[5] Consider this problem: Given a positive integer $n$, find all ordered pairs of distinct positive integers $i$ and $j$, where $1\leq j < i\leq n$, such that $i +j$ is prime. For example, if $n$ is 6, then the pairs are the following: \[ \begin{array}{c|ccccccc} i & 2 & 3 & 4 & 4 & 5 & 6 & 6 \\ j & 1 & 2 & 1 & 3 & 2 & 1 & 5 \\ \hline i+j & 3 & 5 & 5 & 7 & 7 & 7 & 11 \end{array} \] A natural way to organize this computation is to generate the sequence of all ordered pairs of positive integers less than or equal to $n$, filter to select those pairs whose sum is prime, and then, for each pair $(i, j)$ that passes through the filter, produce the triple $(i, j, i+j)$.

Here is a way to generate the sequence of pairs: For each integer $i\leq n$, enumerate the integers $j < i$, and for each such $i$ and $j$ generate the pair $(i, j)$. In terms of sequence operations, we map along the sequence (enumerate-interval 1 n). enumerate_interval(1, n). For each $i$ in this sequence, we map along the sequence (enumerate-interval 1 (- i 1)). enumerate_interval(1, i - 1). For each $j$ in this latter sequence, we generate the pair (list i j). list(i, j). This gives us a sequence of pairs for each $i$. Combining all the sequences for all the $i$ (by accumulating with append) produces the required sequence of pairs:[6]

Original JavaScript
;; replace n below by the desired number (accumulate append nil (map (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n))) accumulate(append, null, map(i => map(j => list(i, j), enumerate_interval(1, i - 1)), enumerate_interval(1, n)));
The combination of mapping and accumulating with append is so common in this sort of program that we will isolate it as a separate procedure: function:
Original JavaScript
(define (flatmap proc seq) (accumulate append nil (map proc seq))) function flatmap(f, seq) { return accumulate(append, null, map(f, seq)); }
Now filter this sequence of pairs to find those whose sum is prime. The filter predicate is called for each element of the sequence; its argument is a pair and it must extract the integers from the pair. Thus, the predicate to apply to each element in the sequence is
Original JavaScript
(define (prime-sum? pair) (prime? (+ (car pair) (cadr pair)))) function is_prime_sum(pair) { return is_prime(head(pair) + head(tail(pair))); }
Finally, generate the sequence of results by mapping over the filtered pairs using the following procedure, function, which constructs a triple consisting of the two elements of the pair along with their sum:
Original JavaScript
(define (make-pair-sum pair) (list (car pair) (cadr pair) (+ (car pair) (cadr pair)))) function make_pair_sum(pair) { return list(head(pair), head(tail(pair)), head(pair) + head(tail(pair))); }
Combining all these steps yields the complete procedure: function:
Original JavaScript
(define (prime-sum-pairs n) (map make-pair-sum (filter prime-sum? (flatmap (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n))))) function prime_sum_pairs(n) { return map(make_pair_sum, filter(is_prime_sum, flatmap(i => map(j => list(i, j), enumerate_interval(1, i - 1)), enumerate_interval(1, n)))); }

Nested mappings are also useful for sequences other than those that enumerate intervals. Suppose we wish to generate all the permutations of a set $S$; that is, all the ways of ordering the items in the set. For instance, the permutations of $\{1, 2, 3\}$ are $\{1, 2, 3\}$, $\{ 1, 3, 2\}$, $\{2, 1, 3\}$, $\{ 2, 3, 1\}$, $\{ 3, 1, 2\}$, and $\{ 3, 2, 1\}$. Here is a plan for generating the permutations of $S$: For each item $x$ in $S$, recursively generate the sequence of permutations of $S-x$,[7] and adjoin $x$ to the front of each one. This yields, for each $x$ in $S$, the sequence of permutations of $S$ that begin with $x$. Combining these sequences for all $x$ gives all the permutations of $S$:[8]

Original JavaScript
(define (permutations s) (if (null? s) ; empty set? (list nil) ; sequence containing empty set (flatmap (lambda (x) (map (lambda (p) (cons x p)) (permutations (remove x s)))) s))) function permutations(s) { return is_null(s) // empty set? ? list(null) // sequence containing empty set : flatmap(x => map(p => pair(x, p), permutations(remove(x, s))), s); }
Notice how this strategy reduces the problem of generating permutations of $S$ to the problem of generating the permutations of sets with fewer elements than $S$. In the terminal case, we work our way down to the empty list, which represents a set of no elements. For this, we generate (list nil), list(null), which is a sequence with one item, namely the set with no elements. The remove remove procedure function used in permutations returns all the items in a given sequence except for a given item. This can be expressed as a simple filter:
Original JavaScript
(define (remove item sequence) (filter (lambda (x) (not (= x item))) sequence)) function remove(item, sequence) { return filter(x => ! (x === item), sequence); }

Exercise 2.40 Write a procedure function unique-pairs unique_pairs that, given an integer $n$, generates the sequence of pairs $(i, j)$ with $1\leq j < i\leq n$. Use unique-pairs unique_pairs to simplify the definition of prime-sum-pairs prime_sum_pairs given above.
Original JavaScript
function unique_pairs(n) { return flatmap(i => map(j => list(i, j), enumerate_interval(1, i - 1)), enumerate_interval(1, n)); } function prime_sum_pairs(n) { return map(make_pair_sum, filter(is_prime_sum, unique_pairs(n))); }
Exercise 2.41 Write a procedure function to find all ordered triples of distinct positive integers $i$, $j$, and $k$ less than or equal to a given integer $n$ that sum to a given integer $s$.
Original JavaScript
function unique_triples(n) { return flatmap(i => flatmap(j => map(k => list(i, j, k), enumerate_interval(1, j - 1)), enumerate_interval(1, i - 1)), enumerate_interval(1, n)); } function plus(x, y) { return x + y; } function triples_that_sum_to(s, n) { return filter(items => accumulate(plus, 0, items) === s, unique_triples(n)); }
Figure 2.15 A solution to the eight-queens puzzle.
Exercise 2.42 The eight-queens puzzle asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal). One possible solution is shown in figure 2.15. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed $k-1$ queens, we must place the $k$th queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place $k-1$ queens in the first $k-1$ columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the $k$th column. Now filter these, keeping only the positions for which the queen in the $k$th column is safe with respect to the other queens. This produces the sequence of all ways to place $k$ queens in the first $k$ columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.

We implement this solution as a procedure function queens, queens, which returns a sequence of all solutions to the problem of placing $n$ queens on an $n\times n$ chessboard. Queens The function queens has an internal procedure function queen-cols queens_cols that returns the sequence of all ways to place queens in the first $k$ columns of the board.

Original JavaScript
(define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size)) function queens(board_size) { function queen_cols(k) { return k === 0 ? list(empty_board) : filter(positions => is_safe(k, positions), flatmap(rest_of_queens => map(new_row => adjoin_position(new_row, k, rest_of_queens), enumerate_interval(1, board_size)), queen_cols(k - 1))); } return queen_cols(board_size); }
In this procedure function rest-of-queens rest_of_queens is a way to place $k-1$ queens in the first $k-1$ columns, and new-row new_row is a proposed row in which to place the queen for the $k$th column. Complete the program by implementing the representation for sets of board positions, including the procedure function adjoin-position, adjoin_position, which adjoins a new row-column position to a set of positions, and empty-board, empty_board, which represents an empty set of positions. You must also write the procedure function safe?, is_safe, which determines for a set of positions whether the queen in the $k$th column is safe with respect to the others. (Note that we need only check whether the new queen is safe—the other queens are already guaranteed safe with respect to each other.)

Original JavaScript
function adjoin_position(row, col, rest) { return pair(pair(row, col), rest); }
Original JavaScript
const empty_board = null;
Original JavaScript
function is_safe(k, positions) { const first_row = head(head(positions)); const first_col = tail(head(positions)); return accumulate((pos, so_far) => { const row = head(pos); const col = tail(pos); return so_far && first_row - first_col !== row - col && first_row + first_col !== row + col && first_row !== row; }, true, tail(positions)); }
Putting it all together:
Original JavaScript
// click here to see all solutions
Exercise 2.43 Louis Reasoner is having a terrible time doing exercise 2.42. His queens queens procedure function seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the $6\times 6$ case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the flatmap, flatmap, writing it as
Original JavaScript
(flatmap (lambda (new-row) (map (lambda (rest-of-queens) (adjoin-position new-row k rest-of-queens)) (queen-cols (- k 1)))) (enumerate-interval 1 board-size)) flatmap(new_row => map(rest_of_queens => adjoin_position(new_row, k, rest_of_queens), queen_cols(k - 1)), enumerate_interval(1, board_size));
Explain why this interchange makes the program run slowly. Estimate how long it will take Louis's program to solve the eight-queens puzzle, assuming that the program in exercise 2.42 solves the puzzle in time $T$.
Louis's program re-evaluates the application queen_cols(k - 1)) in each iteration of flatmap, which happens $n$ times for each $k$. That means overall Louis's program will solve the puzzle in a time of about $n^n T$ if the program in exercise 2.42 solves the puzzle in time $T$.

[1] This is, in fact, precisely the fringe fringe procedure function from exercise 2.28. Here we've renamed it to emphasize that it is part of a family of general sequence-manipulation procedures. functions.
[2] Richard Waters (1979) developed a program that automatically analyzes traditional Fortran programs, viewing them in terms of maps, filters, and accumulations. He found that fully 90 percent of the code in the Fortran Scientific Subroutine Package fits neatly into this paradigm. One of the reasons for the success of Lisp as a programming language is that lists provide a standard medium for expressing ordered collections so that they can be manipulated using higher-order operations. Many modern languages, such as Python, have learned this lesson.
[3] According to Knuth (1997b), this rule was formulated by W. G. Horner early in the nineteenth century, but the method was actually used by Newton over a hundred years earlier. Horner's rule evaluates the polynomial using fewer additions and multiplications than does the straightforward method of first computing $a_{n} x^n$, then adding $a_{n-1}x^{n-1}$, and so on. In fact, it is possible to prove that any algorithm for evaluating arbitrary polynomials must use at least as many additions and multiplications as does Horner's rule, and thus Horner's rule is an optimal algorithm for polynomial evaluation. This was proved (for the number of additions) by A. M. Ostrowski in a 1954 paper that essentially founded the modern study of optimal algorithms. The analogous statement for multiplications was proved by V. Y. Pan in 1966. The book by Borodin and Munro (1975) provides an overview of these and other results about optimal algorithms.
[4] This definition uses the extended version of map described in footnote 7. the function accumulate_n from exercise 2.36.
[5] This approach to nested mappings was shown to us by David Turner, whose languages KRC and Miranda provide elegant formalisms for dealing with these constructs. The examples in this section (see also exercise 2.42) are adapted from Turner 1981. In section 3.5.3, we'll see how this approach generalizes to infinite sequences.
[6] We're representing a pair here as a list of two elements rather than as a Lisp pair. an ordinary pair. Thus, the pair $(i, j)$ is represented as (list i j), list(i, j), not (cons i j). pair(i, j).
[7] The set $S-x$ is the set of all elements of $S$, excluding $x$.
[8] Semicolons in Scheme code are The character sequence // in JavaScript programs is used to introduce comments. Everything from the semicolon // to the end of the line is ignored by the interpreter. In this book we don't use many comments; we try to make our programs self-documenting by using descriptive names.
< Previous
Next >
2.2.3   Sequences as Conventional Interfaces
You are visitor 01402639 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.