Figure 2.15 A solution to the eight-queens puzzle.

[1] This is, in fact, precisely the fringe fringe procedure function from exercise 2.29. 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.37.
[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.43) 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.
2.2.3   Sequences as Conventional Interfaces