diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/ssch19/implement-hof.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch19/implement-hof.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch19/implement-hof.html | 604 |
1 files changed, 604 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch19/implement-hof.html b/js/games/nluqo.github.io/~bh/ssch19/implement-hof.html new file mode 100644 index 0000000..fb954da --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch19/implement-hof.html @@ -0,0 +1,604 @@ +<P> +<A NAME="polly"></A> +<P><P><CENTER><IMG SRC="../ss-pics/polly.jpg" ALT="figure: polly"></CENTER> +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 19: Implementing Higher-Order Functions</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 19</H2> +<H1>Implementing Higher-Order Functions</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../simply.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/ssch19.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../ssch18/trees.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch20/part6.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT +Press web page for <CITE>Simply Scheme</CITE></A> +</TABLE></TABLE> + +<HR> + + +<P>This chapter is about writing <EM><A NAME="g1"></A>higher-order procedures—</EM>that is, procedures that implement +<A NAME="g2"></A><A NAME="g3"></A>higher-order functions. We are going to study the implementation +of <CODE>every</CODE>, <CODE>keep</CODE>, and so on. + +<P>Really there are no new techniques involved. You know how to write +recursive procedures that follow the <CODE>every</CODE> pattern, the <CODE>keep</CODE> +pattern, and so on; it's a small additional step to generalize those +<A NAME="g4"></A> +patterns. The truly important point made in this chapter is that you aren't +limited to a fixed set of higher-order functions. If you feel a need for a +new one, you can implement it. + +<P><H2>Generalizing Patterns</H2> + +<P>In Chapter 14, we showed you the procedures <CODE>square-sent</CODE> and <CODE>pigl-sent</CODE>, which follow the <CODE>every</CODE> pattern of recursion. In order to +write the general tool, <CODE>every</CODE> itself, we have to +<EM>generalize the pattern</EM> that those two have in common. + +<P>Before we get to writing higher-order procedures, let's look at a simpler +case of generalizing patterns. + +<P>Suppose we want to find out the areas of several different kinds of +shapes, given one linear dimension. A straightforward way would be to do it +like this: + +<P><PRE>(define pi 3.141592654) + +(define (<A NAME="g5"></A>square-area r) (* r r)) + +(define (<A NAME="g6"></A>circle-area r) (* pi r r)) + +(define (<A NAME="g7"></A>sphere-area r) (* 4 pi r r)) + +(define (<A NAME="g8"></A>hexagon-area r) (* (sqrt 3) 1.5 r r)) + +> (square-area 6) +36 + +> (circle-area 5) +78.53981635 +</PRE> + +<P>This works fine, but it's somewhat tedious to define all four of +these procedures, given that they're so similar. Each one returns the square +of its argument times some constant factor; the only difference is the +constant factor. + +<P>We want to generalize the pattern that these four procedures +exhibit. Each of these procedures has a particular constant factor built in +to its definition. What we'd like instead is one single procedure that lets +you choose a constant factor when you invoke it. This new procedure will +take a second argument besides the linear dimension <CODE>r</CODE> (the radius or +side): a <CODE>shape</CODE> argument whose value is the desired constant factor. + +<P><PRE>(define (<A NAME="g9"></A>area shape r) (* shape r r)) +(define square 1) +(define circle pi) +(define sphere (* 4 pi)) +(define hexagon (* (sqrt 3) 1.5)) + +> (area sphere 7) +615.752160184 +</PRE> + +<P>What's the point? We started with several procedures. Then we found that +they had certain points of similarity and certain differences. In order to +write a single procedure that generalizes the points of similarity, we had to +use an additional argument for each point of difference. (In this example, +there was only one point of difference.) + +<P>In fact, <EM>every</EM> procedure with arguments is a generalization in the +same way. Even <CODE>square-area</CODE>, which we presented as the special case +to be generalized, is more general than these procedures: + +<P><PRE>(define (area-of-square-of-side-5) + (* 5 5)) + +(define (area-of-square-of-side-6) + (* 6 6)) +</PRE> + +<P>These may seem too trivial to be taken seriously. Indeed, nobody +would write such procedures. But it's possible to take the area of a +particular size square without using a procedure at all, and then later +discover that you need to deal with squares of several sizes. + +<P>This idea of using a procedure to generalize a pattern is part of the larger +idea of abstraction that we've been discussing throughout the book. We +notice an algorithm that we need to use repeatedly, and so we separate the +algorithm from any particular data values and give it a name. + +<P>The idea of generalization may seem obvious in the example about areas of +squares. But when we apply the same idea to generalizing over a function, +rather than merely generalizing over a number, we gain the enormous +expressive power of higher-order functions. + +<P><H2>The <CODE><B>Every</B></CODE> Pattern Revisited</H2> + +<P>Here again is the <CODE>every</CODE> template: + +<P><PRE>(define (<B>every-something</B> sent) + (if (empty? sent) + '() + (se (______ (first sent)) + (<B>every-something</B> (bf sent))))) +</PRE> + +<P>You've been writing <CODE>every</CODE>-like procedures by filling in the +blank with a specific function. To generalize the pattern, we'll use the +trick of adding an argument, as we discussed in the last section. + +<P><PRE>(define (<A NAME="g10"></A>every fn sent) + (if (empty? sent) + '() + (se (fn (first sent)) + (every fn (bf sent))))) +</PRE> + +<P>This is hardly any work at all for something that seemed as +mysterious as <CODE>every</CODE> probably did when you first saw it. + +<P>Recall that <CODE>every</CODE> will also work if you pass it a word as its second +argument. The version shown here does indeed work for words, because <CODE>first</CODE> and <CODE>butfirst</CODE> work for words. So probably "<CODE>stuff</CODE>" would +be a better formal parameter than "<CODE>sent</CODE>." (The result from <CODE>every</CODE> is always a sentence, because <CODE>sentence</CODE> is used to construct the +result.) + +<P> +<P><H2>The Difference between <CODE><B>Map</B></CODE> and <CODE><B>Every</B></CODE></H2> + +<P>Here's the definition of the <CODE>map</CODE> procedure: + +<P><PRE>(define (<A NAME="g11"></A>map fn lst) + (if (null? lst) + '() + (cons (fn (car lst)) + (map fn (cdr lst))))) +</PRE> + +<P>The structure here is identical to that of <CODE>every</CODE>; the only +difference is that we use <CODE>cons</CODE>, <CODE>car</CODE>, and <CODE>cdr</CODE> instead of +<CODE>se</CODE>, <CODE>first</CODE>, and <CODE>butfirst</CODE>. + +<P>One implication of this is that you can't use <CODE>map</CODE> with a word, since +it's an error to take the <CODE>car</CODE> of a word. When is it advantageous +to use <CODE>map</CODE> instead of <CODE>every</CODE>? Suppose you're using <CODE>map</CODE> +with a structured list, like this: + +<P><PRE>> (map (lambda (flavor) (se flavor '(is great))) + '(ginger (ultra chocolate) pumpkin (rum raisin))) +((GINGER IS GREAT) (ULTRA CHOCOLATE IS GREAT) + (PUMPKIN IS GREAT) (RUM RAISIN IS GREAT)) +</PRE> + +<P><PRE>> (every (lambda (flavor) (se flavor '(is great))) + '(ginger (ultra chocolate) pumpkin (rum raisin))) +(GINGER IS GREAT ULTRA CHOCOLATE IS GREAT PUMPKIN IS GREAT + RUM RAISIN IS GREAT) +</PRE> + +<P>Why does <CODE>map</CODE> preserve the structure of the sublists while <CODE>every</CODE> +doesn't? <CODE>Map</CODE> uses <CODE>cons</CODE> to combine the elements of the result, +whereas <CODE>every</CODE> uses <CODE>sentence</CODE>: + +<P><PRE>> (cons '(pumpkin is great) + (cons '(rum raisin is great) + '())) +((PUMPKIN IS GREAT) (RUM RAISIN IS GREAT)) + +> (se '(pumpkin is great) + (se '(rum raisin is great) + '())) +(PUMPKIN IS GREAT RUM RAISIN IS GREAT) +</PRE> + +<P><H2><CODE><B>Filter</B></CODE></H2> + +<P>Here's the implementation of <A NAME="g12"></A><CODE>filter</CODE>: + +<P><PRE>(define (<A NAME="g13"></A>filter pred lst) + (cond ((null? lst) '()) + ((pred (car lst)) + (cons (car lst) (filter pred (cdr lst)))) + (else (filter pred (cdr lst))))) +</PRE> + +<P>Like <CODE>map</CODE>, this uses <CODE>cons</CODE> as the constructor so that it +will work properly on structured lists. We're leaving the definition of +<CODE>keep</CODE>, the version for words and sentences, as an exercise. + +<P>(Aside from the difference between lists and sentences, this is just like +the <CODE>keep</CODE> template on page <A HREF="../ssch14/recur-patterns.html#keeptemplate">there</A>.) + +<P><H2><CODE><B>Accumulate</B></CODE> and <CODE><B>Reduce</B></CODE></H2> + +<P>Here are the examples of the <A NAME="g14"></A><CODE>accumulate</CODE> pattern that we showed +you before: + +<P><PRE>(define (addup nums) + (if (empty? nums) + 0 + (+ (first nums) (addup (bf nums))))) + +(define (scrunch-words sent) + (if (empty? sent) + "" + (word (first sent) (scrunch-words (bf sent))))) +</PRE> + +<P>What are the similarities and differences? There are <EM>two</EM> important +differences between these procedures: the combiners (<CODE>+</CODE> versus <CODE>word</CODE>) and the values returned in the base cases (zero versus the empty +word). According to what we said about generalizing patterns, you might +expect that we'd need two extra arguments. You'd invoke <CODE>three-arg-accumulate</CODE> like this: + +<P><PRE>> (three-arg-accumulate + 0 '(6 7 8)) +21 + +> (three-arg-accumulate word "" '(come together)) +COMETOGETHER +</PRE> + +<P>But we've actually defined <CODE>accumulate</CODE> and <A NAME="g15"></A><CODE>reduce</CODE> so +that only two arguments are required, the procedure and the sentence or +list. We thought it would be too much trouble to have to provide the +identity element all the time. How did we manage to avoid it? + +<P>The trick is that in our <CODE>reduce</CODE> and <CODE>accumulate</CODE> the base case is +a one-element argument, rather than an empty argument. When we're down to +one element in the argument, we just return that element: + +<P><PRE>(define (accumulate combiner stuff) ;; first version + (if (empty? (bf stuff)) + (first stuff) + (combiner (first stuff) + (accumulate combiner (bf stuff))))) +</PRE> + +<P>This version is a simplification of the one we actually provide. +What happens if <CODE>stuff</CODE> is empty? This version blows up, since it tries +to take the <CODE>butfirst</CODE> of <CODE>stuff</CODE> immediately. Our final version +has a specific check for empty arguments: + +<P><PRE>(define (<A NAME="g16"></A>accumulate combiner stuff) + (cond ((not (empty? stuff)) (real-accumulate combiner stuff)) + ((member combiner (list + * word se append)) + (combiner)) + (else (error + "Can't accumulate empty input with that combiner")))) + +(define (<A NAME="g17"></A>real-accumulate combiner stuff) + (if (empty? (bf stuff)) + (first stuff) + (combiner (first stuff) (real-accumulate combiner (bf stuff))))) +</PRE> + +<P>This version works just like the earlier version as long as <CODE>stuff</CODE> isn't empty. (<CODE>Reduce</CODE> is the same, except that it uses <CODE>null?</CODE>, <CODE>car</CODE>, and <CODE>cdr</CODE>.) + +<P>As we mentioned in Chapter 8, many of Scheme's primitive procedures +return their identity element when invoked with no arguments. We can take +advantage of this; if <CODE>accumulate</CODE> is invoked with an empty second +argument and one of the procedures <CODE>+</CODE>, <CODE>*</CODE>, <CODE>word</CODE>, <CODE>sentence</CODE>, <CODE>append</CODE> or <CODE>list</CODE>, we invoke the combiner with no +arguments to produce the return value. + +<P> +<P>On the other hand, if <CODE>accumulate</CODE>'s combiner argument is something like +<CODE>(lambda (x y) (word x '- y))</CODE> or <CODE>max</CODE>, then there's nothing <CODE>accumulate</CODE> can return, so we give an error message. (But it's a more +descriptive error message than the first version; what message do you get +when you call that first version with an empty second argument?) + +<P>It's somewhat of a kludge that we have to include in our procedure a +list of the functions that can be called without arguments. What we'd like +to do is invoke the combiner and find out if that causes an error, but +Scheme doesn't provide a mechanism for causing errors on purpose and +recovering from them. (Some dialects of Lisp do have that capability.) + +<P><H2>Robustness</H2> + +<P>Instead of providing a special error message for empty-argument cases +that <CODE>accumulate</CODE> can't handle, we could have just let it blow up: + +<P><PRE>(define (accumulate combiner stuff) ;; non-robust version + (if (not (empty? stuff)) + (real-accumulate combiner stuff) + (combiner))) +</PRE> + +<P>Some questions about programming have clear right and wrong answers—if your +program doesn't work, it's wrong! But the decision about whether to include +the extra check for a procedure that's usable with an empty argument is a +matter of judgment. + +<P>Here is the reasoning in favor of this simpler version: In either version, +the user who tries to evaluate an expression like + +<P><PRE>(accumulate max '()) +</PRE> + +<P>is going to get an error message. In the longer version we've +spent both our own programming effort and a little of the computer's time +on every invocation just to give a <EM>different</EM> error message from the +one that Scheme would have given anyway. What's the point? + +<P>Here is the reasoning in favor of the longer version: In practice, the +empty-argument situation isn't going to arise because someone uses a quoted +empty sentence; instead the second argument to <CODE>accumulate</CODE> will be some +expression whose value happens to be empty under certain conditions. The +user will then have to debug the program that caused those conditions. +Debugging is hard; we should make it easier for the user, if we can, by +giving an error message that points clearly to the problem. + +<P>A program that behaves politely when given incorrect input is called <EM>robust.</EM> It's not always a matter of better or worse error +messages. For example, a program that reads input from a human user might +offer the chance to try again if some input value is incorrect. A robust +program will also be alert for hardware problems, such as running out of +space on a disk, or getting garbled information over a telephone connection +to another machine because of noise on the line. + +<P>It's possible to pay either too little or too much attention to program +robustness. If you're a professional programmer, your employer will expect +your programs to survive errors that are likely to happen. On the other +hand, your programs will be hard to read and debug if the error checking +swamps the real work! As a student, unless you are specifically asked to +"bulletproof" your program, don't answer exam questions by writing +procedures like this one: + +<P><PRE>(define (even? num) ;; silly example + (cond ((not (number? num)) (error "Not a number.")) + ((not (integer? num)) (error "Not an integer.")) + ((< num 0) (error "Argument must be positive.")) + (else (= (remainder num 2) 0)))) +</PRE> + +<P>In the case of <CODE>accumulate</CODE>, we decided to be extra robust +because we were writing a procedure for use in a beginning programming +course. If we were writing this tool just for our own use, we might have +chosen the non-robust version. Deciding how robust a program will be is a +matter of taste. + +<P><H2>Higher-Order Functions for Structured Lists</H2> + +<P>We've given you a fairly standard set of higher-order functions, but there's +no law that says these are the only ones. Any time you notice yourself +writing what feels like the same procedure over again, but with different +details, consider inventing a higher-order function. + +<P>For example, here's a procedure we defined in Chapter 17. + +<P><PRE>(define (<A NAME="g18"></A>deep-pigl structure) + (cond ((word? structure) (pigl structure)) + ((null? structure) '()) + (else (cons (deep-pigl (car structure)) + (deep-pigl (cdr structure)))))) +</PRE> + +<P>This procedure converts every word in a <A NAME="g19"></A><A NAME="g20"></A>structured list +to Pig Latin. +Suppose we have a structure full of numbers and we want to compute all of their +squares. We could write a specific procedure <CODE>deep-square</CODE>, but +instead, we'll write a higher-order procedure: + +<P><PRE>(define (<A NAME="g21"></A>deep-map f structure) + (cond ((word? structure) (f structure)) + ((null? structure) '()) + (else (cons (deep-map f (car structure)) + (deep-map f (cdr structure)))))) +</PRE> + +<P><H2>The Zero-Trip Do Loop</H2> + +<P>The first programming language that provided a level of abstraction over the +instructions understood directly by computer hardware was Fortran, a +language that is still widely used today despite the advances in programming +language design since then. Fortran remains popular because of the enormous +number of useful programs that have already been written in it; if an +improvement is needed, it's easier to modify the Fortran program than to +start again in some more modern language. + +<P>Fortran includes a control mechanism called <CODE>do</CODE>, a sort of higher-order +procedure that carries out a computation repeatedly, as <CODE>every</CODE> does. +But instead of carrying out the computation once for each element of a given +collection of data (like the sentence argument to <CODE>every</CODE>), <CODE>do</CODE> +performs a computation once for each integer in a range specified by its +endpoints. "For every number between 4 and 16, do such-and-such." + +<P>What if you specify endpoints such that the starting value is greater than +the ending value? In the first implementation of Fortran, nobody thought +very hard about this question, and they happened to implement <CODE>do</CODE> in +such a way that if you specified a backward range, the computation was done +once, for the given starting value, before Fortran noticed that it was past +the ending value. + +<P>Twenty years later, a bunch of computer scientists argued that this behavior +was wrong—that a <CODE>do</CODE> loop with its starting value greater than its +ending value should not carry out its computation at all. This proposal for +a "zero-trip <CODE>do</CODE> loop" was strongly opposed by Fortran old-timers, +not because of any principle but because of all the thousands of Fortran +programs that had been written to rely on the one-trip behavior. + +<P>The point of this story is that the Fortran users had to debate the issue so +heatedly because they are stuck with only the control mechanisms that are +built into the language. Fortran doesn't have the idea of function as data, +so Fortran programmers can't write their own higher-order procedures. But +you, using the techniques of this chapter, can create precisely the control +mechanism that you need for whatever problem you happen to be working on. + +<P><H2>Pitfalls</H2> + +<P>The most crucial point in inventing a higher-order function is to make +sure that the pattern you have in mind really does generalize. For example, +if you want to write a higher-order function for structured data, what is the base +case? Will you use the tree abstract data type, or will you use <CODE>car</CODE>/<CODE>cdr</CODE> +recursion? + +<P>When you generalize a pattern by adding a new argument (typically a +procedure), be sure you add it to the recursive invocation(s) as well as to +the formal parameter list! + +<P><H2>Boring Exercises</H2> + +<P><B>19.1</B> What happens if you say the following? + +<P><PRE>(every cdr '((john lennon) (paul mccartney) + (george harrison) (ringo starr))) +</PRE> + +<P>How is this different from using <CODE>map</CODE>, and why? How about <CODE>cadr</CODE> instead of <CODE>cdr</CODE>? + + +<P> +<H2>Real Exercises</H2> + +<P><B>19.2</B> Write <CODE>keep</CODE>. Don't forget that <CODE>keep</CODE> has to return a sentence if +its second argument is a sentence, and a word if its second argument is a +word. + +<P>(Hint: it might be useful to write a <CODE>combine</CODE> procedure that uses either +<CODE>word</CODE> or <CODE>sentence</CODE> depending on the types of its arguments.) + + +<P> +<B>19.3</B> Write the three-argument version of <CODE>accumulate</CODE> that we described. + +<P><PRE>> (three-arg-accumulate + 0 '(4 5 6)) +15 + +> (three-arg-accumulate + 0 '()) +0 + +> (three-arg-accumulate cons '() '(a b c d e)) +(A B C D E) +</PRE> + +<P> +<B>19.4</B> Our <CODE>accumulate</CODE> combines elements from right to left. That is, + +<P><PRE>(accumulate - '(2 3 4 5)) +</PRE> + +<P>computes 2−(3−(4−5)). Write <CODE>left-accumulate</CODE>, which +will compute ((2−3)−4)−5 instead. (The result will be the same for +an operation such as <CODE>+</CODE>, for which grouping order doesn't matter, but +will be different for <CODE>-</CODE>.) + + +<P> +<B>19.5</B> Rewrite the <CODE>true-for-all?</CODE> procedure from Exercise <A HREF="../ssch8/higher.html#trueforall">8.10</A>. +Do not use <CODE>every</CODE>, <CODE>keep</CODE>, or <CODE>accumulate</CODE>. + + +<P> +<B>19.6</B> Write a procedure <CODE><A NAME="g22"></A>true-for-any-pair?</CODE> that takes a predicate and a +sentence as arguments. The predicate must accept two words as its arguments. +Your procedure should return <CODE>#t</CODE> if the argument predicate will return +true for any two adjacent words in the sentence: +<A NAME="exanypair"></A> + +<P><PRE>> (true-for-any-pair? equal? '(a b c b a)) +#F + +> (true-for-any-pair? equal? '(a b c c d)) +#T + +> (true-for-any-pair? < '(20 16 5 8 6)) ;; 5 is less than 8 +#T +</PRE> + +<P> +<B>19.7</B> Write a procedure <CODE><A NAME="g23"></A>true-for-all-pairs?</CODE> that takes a predicate +and a sentence as arguments. The predicate must accept two words as its +arguments. Your procedure should return <CODE>#t</CODE> if the argument predicate +will return true for <EM>every</EM> two adjacent words in the sentence: +<A NAME="exallpairs"></A> + +<P><PRE>> (true-for-all-pairs? equal? '(a b c c d)) +#F + +> (true-for-all-pairs? equal? '(a a a a a)) +#T + +> (true-for-all-pairs? < '(20 16 5 8 6)) +#F + +> (true-for-all-pairs? < '(3 7 19 22 43)) +#T +</PRE> + +<P> +<B>19.8</B> Rewrite <CODE>true-for-all-pairs?</CODE> (Exercise <A HREF="implement-hof.html#exallpairs">19.7</A>) using <CODE>true-for-any-pair?</CODE> (Exercise <A HREF="implement-hof.html#exanypair">19.6</A>) as a helper procedure. Don't use +recursion in solving this problem (except for the recursion you've already +used to write <CODE>true-for-any-pair?</CODE>). Hint: You'll find the <CODE>not</CODE> +procedure helpful. + + +<P> +<B>19.9</B> Rewrite either of the sort procedures from Chapter 15 to take two +arguments, a list and a predicate. It should sort the elements of that list +according to the given predicate: + +<P><PRE>> (sort '(4 23 7 5 16 3) <) +(3 4 5 7 16 23) + +> (sort '(4 23 7 5 16 3) >) +(23 16 7 5 4 3) + +> (sort '(john paul george ringo) before?) +(GEORGE JOHN PAUL RINGO) +</PRE> + +<P> +<B>19.10</B> Write <CODE>tree-map</CODE>, analogous to our <CODE>deep-map</CODE>, but for trees, using +the <CODE>datum</CODE> and <CODE>children</CODE> selectors. + + +<P> +<B>19.11</B> Write <CODE>repeated</CODE>. (This is a hard exercise!) + + +<P> +<B>19.12</B> Write <CODE>tree-reduce</CODE>. You may assume that the combiner argument can +be invoked with no arguments. + +<P><PRE>> (tree-reduce + + + (make-node 3 (list (make-node 4 '()) + (make-node 7 '()) + (make-node 2 (list (make-node 3 '()) + (make-node 8 '())))))) +27 +</PRE> + +<P> +<B>19.13</B> Write <CODE>deep-reduce</CODE>, similar to <CODE>tree-reduce</CODE>, but for structured +lists: + +<P><PRE>> (deep-reduce word '(r ((a (m b) (l)) (e (r))))) +RAMBLER +</PRE> + + +<P> +<HR> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch18/trees.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch20/part6.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |