VI Accumulators
When you ask ISL+ to apply some function f to an argument a, you usually get some value v. If you evaluate (f a) again, you get v again.The function application may also loop forever or signal an error, but let’s ignore these possibilities for now. We also ignore random, which is the only real exception to this rule. As a matter of fact, you get the same result no matter how often you request the evaluation of (f a). Whether the function is applied for the first time or the hundredth time, whether the application is located in DrRacket’s interactions area or inside the function itself, doesn’t matter. The function works according to its purpose statement, and that’s all you need to know.
This principle of contextindependence plays a critical role in the design
of recursive functions. When it comes to coding, you are free to assume
that the function computes what the purpose statement promises—
Although contextindependence facilitates the design of functions, it also causes two problems. The general idea is that contextindependence induces a loss of knowledge during a recursive evaluation; a function does not “know” whether it is called on a complete list or on a piece of that list. For structurally recursive programs this loss of knowledge means that they may have to traverse data more than once, inducing a grave performance cost. For functions that employ generative recursion, the loss means that the function may not be able to compute the result; instead the function loops forever for certain inputs. The preceding part illustrates this second problem with a graph traversal function that cannot find a path between two nodes for a circular graph.
This part introduces a variant of the design recipes to address this “loss of context” problem. Since we wish to retain the principle that (f a) returns the same result no matter how often it is evaluated, our only solution is to add an argument that represents the context of the function call. We call this additional argument an accumulator. During the traversal of data, the recursive calls continue to receive new regular arguments while accumulators change in relation to the other arguments and the context of the call.
Designing functions with accumulators correctly is clearly more complex than any of the design approaches from the preceding chapters. The key is to understand the relationship between the proper arguments and the accumulators. The following chapters explain how to design functions with accumulators work and how they work.
36 The Loss of Knowledge
Both functions designed according to structural recipes and the generative
one suffer from the loss of knowledge, though in different ways. This
chapter explains with two examples—
36.1 A Problem with Structural Processing
Let’s start with a seemingly straightforward example:
Sample Problem: You are working for a geometer team that will measure the length of roads segments. The team asked you to design a program that translates these relative distances between a series of road points into absolute distances for some starting point.
Designing a program that performs this calculation is at this point an
exercise in structural function design. Figure 105
contains the complete program. When the given list is not empty,
the natural recursion computes the absolute distance of the remainder of
the dots to the first item on (rest alon). Because the first item
is not the actual origin and has a distance of (first alon) to the
origin, we must add (first alon) to each number on the result of
the natural recursion. This second step—
; [Listof Number] > [Listof Number] ; convert a list of relative distances to a list of absolute distances ; the first item on the list represents the distance to the origin (checkexpect (relative>absolute '(50 40 70 30 30)) '(50 90 160 190 220)) (define (relative>absolute l) (cond [(empty? l) empty] [else (local ((define restofl (relative>absolute (rest l))) (define adjusted (addtoeach (first l) restofl))) (cons (first l) adjusted))])) ; Number [Listof Number] > [Listof Number] ; add n to each number on alon (checkexpect (cons 50 (addtoeach 50 '(40 110 140 170))) '(50 90 160 190 220)) (define (addtoeach n alon) (cond [(empty? alon) empty] [else (cons (+ (first alon) n) (addtoeach n (rest alon)))])) Figure 105: Converting relative distances to absolute distances
size
1000
2000
3000
4000
5000
6000
7000
time
25
109
234
429
689
978
1365
Exercise 396. Determine the abstract running time of relative>absolute.
Hint Evaluate the expressionby hand. Start by replacing size with 1, 2, and 3. How many natural recursions of relative>absolute and addtoeach are required each time?
Considering the simplicity of the problem, the amount of “work” that the program performs is surprising. If we were to convert the same list by hand, we would tally up the total distance and just add it to the relative distances as we take another step along the line. Why can’t a program use this idea?
(define (relative>absolute/a alon) (cond [(empty? alon) ...] [else ... (first alon) ... (relative>absolute/a (rest alon)) ...]))
= (cons ... 3 ... (convert (list 2 7))) = (cons ... 3 ... (cons ... 2 ... (convert (list 7)))) = (cons ... 3 ... (cons ... 2 ... (cons ... 7 ... (convert empty))))
Put differently, the problem is that recursive functions are independent of their context. A function processes L in (cons N L) in the same manner as in (cons K L). Indeed, it would also process L in that manner if it were given L by itself.
To make up for the loss of “knowledge,” we equip the function with an additional parameter: accudist. The new parameter represents the accumulated distance, which is the tally that we keep when we convert a list of relative distances to a list of absolute distances. Its initial value must be 0. As the function processes the numbers on the list, it must add them to the tally.
(define (relative>absolute/a alon accudist) (cond [(empty? alon) empty] [else (local ((define tally (+ (first alon) accudist))) (cons tally (relative>absolute/a (rest alon) tally)))]))
= (relative>absolute/a (list 3 2 7) 0) = (cons 3 (relative>absolute/a (list 2 7) 3)) = (cons 3 (cons 5 (relative>absolute/a (list 7) 5))) = (cons 3 (cons 5 (cons 12 (relative>absolute/a empty 12)))) = (cons 3 (cons 5 (cons 12 empty)))
One minor problem with the new definition is that unlike relative>absolute, the new function consumes two arguments not just one. Worse, someone might accidentally misuse relative>absolute/a by applying it to a list of numbers and a number that isn’t 0. We can solve both problems with a function definition that uses a local definition to encapsulate relative>absolute/a; figure 106 shows the result. Now, relative>absolute and relative>absolute2 are indistinguishable with respect to the inputoutput relationship.
; [Listof Number] > [Listof Number] ; convert a list of relative distances to a list of absolute distances ; the first item on the list represents the distance to the origin (checkexpect (relative>absolute.v2 '(50 40 70 30 30)) '(50 90 160 190 220)) (define (relative>absolute.v2 alon) (local (; [Listof Number] Number > [Listof Number] (define (relative>absolute/a alon accudist) (cond [(empty? alon) empty] [else (local ((define accu (+ (first alon) accudist))) (cons accu (relative>absolute/a (rest alon) accu)))]))) (relative>absolute/a alon 0))) Figure 106: Converting relative distances with an accumulator
size
1000
2000
3000
4000
5000
6000
7000
time
0
0
0
0
0
1
1
36.2 A Problem with Generative Recursion
Sample Problem: Design an algorithm that checks whether two nodes are connected in a simple graph. In a simple graph, each node has exactly one, onedirectional connection to another node, possibly itself.
Consider the sample graph in figure 107. There are six nodes: A through F, and six connections. To get from A to E, you must go through B and C. It is impossible, though, to reach F from A or from any other node besides F itself.
(define asimplegraph '((A B) (B C) (C E) (D E) (E B) (F F)))
; Node Node SimpleGraph > Boolean ; is there a path from origination to destination in sg (checkexpect (pathexists? 'A 'E asimplegraph) true) (checkexpect (pathexists? 'A 'F asimplegraph) false) (define (pathexists? origination destination sg) false)
The problem is trivial if the nodes origination and destination are the same.
The trivial solution is true.
If origination is not the same as destination, there is only one thing we can do: step to the immediate neighbor and search for destination from there.
There is no need to do anything if we find the solution to the new problem. If origination’s neighbor is connected to destination, then so is origination. Otherwise there is no connection.
; Node Node SimpleGraph > Boolean ; is there a path from origination to destination in sg (checkexpect (pathexists? 'A 'E asimplegraph) true) (checkexpect (pathexists? 'A 'F asimplegraph) false) (define (pathexists? origination destination sg) (cond [(symbol=? origination destination) #t] [else (pathexists? (neighbor origination sg) destination sg)])) ; Node SimpleGraph > Node ; determine the node that is connected to anode in sg (checkexpect (neighbor 'A asimplegraph) 'B) (checkerror (neighbor 'G asimplegraph) "neighbor: not a node") (define (neighbor anode sg) (cond [(empty? sg) (error "neighbor: not a node")] [else (if (symbol=? (first (first sg)) anode) (second (first sg)) (neighbor anode (rest sg)))]))
Figure 108 contains the complete program, including the
function for looking up the neighbor of a node in a simple graph—
(pathexists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))
= (pathexists? 'E 'D '((A B) (B C) (C E) (D E) (E B) (F F))) = (pathexists? 'B 'D '((A B) (B C) (C E) (D E) (E B) (F F))) = (pathexists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))
Our problem with pathexists? is again a loss of “knowledge,” similar to that of relative>absolute in the preceding section. Like relative>absolute, the design of pathexists? uses a recipe and assumes contextindependence for recursive calls. In the case of pathexists? this means, in particular, that the function doesn’t “know” whether a previous application in the current chain of recursions received the exact same arguments.
The solution to this design problem follows the pattern of the preceding section. We add a parameter, which we call seen and which represents the accumulated list of origination nodes that the function has encountered, starting with the original application. Its initial value must be '(). As the function checks on a specific origination and moves to its neighbors, origination is added to seen.
; Node Node SimpleGraph [Listof Node] > Boolean ; is there a path from origination to destination in sg ; assume the nodes in seen are known not to solve the problem (define (pathexists?/a origination destination sg seen) (cond [(symbol=? origination destination) #t] [else (pathexists?/a (neighbor origination sg) destination sg (cons origination seen))]))
(pathexists?/a 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '())
= (pathexists?/a 'E 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(C)) = (pathexists?/a 'B 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(E C)) = (pathexists?/a 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(B E C))
All we need to do now, is to make the algorithm exploit the accumulated knowledge. Specifically, the algorithm can determine whether the given origination is already an item in seen. If so, the problem is also trivially solvable yielding false as the solution. Figure 109 contains the definition of pathexists.v2?, which is the revision of pathexists?. The definition refers to member?, an ISL+ function.
; Node Node SimpleGraph > Boolean ; is there a path from origination to destination in sg (checkexpect (pathexists.v2? 'A 'E asimplegraph) true) (checkexpect (pathexists.v2? 'A 'F asimplegraph) false) (define (pathexists.v2? origination destination sg) (local (; Node Node SimpleGraph [Listof Node] > Boolean (define (pathexists?/a origination seen) (cond [(symbol=? origination destination) #t] [(member? origination seen) #f] [else (pathexists?/a (neighbor origination sg) (cons origination seen))]))) (pathexists?/a origination '()))) Figure 109: Finding a path in a simple graph with an accumulator
The definition of pathexists.v2? also eliminates the two minor problems with the first revision. By localizing the definition of the accumulating function, we can ensure that the first call always uses '() as the initial value for seen. And, pathexists.v2? satisfies the exact same contract and purpose statement as the pathexists? function.
Still, there is a significant difference between pathexists.v2? and relativetoabsolute2. Whereas the latter was equivalent to the original function, pathexists.v2? improves on pathexists?. While the latter fails to find an answer for some inputs, pathexists.v2? finds a solution for any simple graph.
Exercise 397. Modify the definitions of findpath and findpath/list in figure 99 so that they produce false, even if they encounter the same starting point twice.
37 Designing AccumulatorStyle Functions
The preceding chapter illustrates the need for accumulating extra knowledge with two examples. In one case, accumulation makes it easy to understand the function and yields one that is far faster than the original version. In the other case, accumulation is necessary for the function to work properly. In both cases though, the need for accumulation becomes only apparent once a properly designed function exists.
the recognition that a function benefits from an accumulator;
an understanding of what the accumulator represents with respect to the design.
37.1 Recognizing the Need for an Accumulator
If a structurally recursive function processes the result of its natural recursion with an auxiliary, recursive function, consider the use of an accumulator parameter.
Take a look at the definition of invert:; [Listof X] > [Listof X] ; construct the reverse of alox (checkexpect (invert '(a b c)) '(c b a)) (define (invert alox) (cond [(empty? alox) empty] [else (addaslast (first alox) (invert (rest alox)))])) ; X [Listof X] > [Listof X] ; add anx to the end of alox (checkexpect (addaslast 'a '(c b)) '(c b a)) (define (addaslast anx alox) (cond [(empty? alox) (list anx)] [else (cons (first alox) (addaslast anx (rest alox)))])) The result of the recursive application produces the reverse of the rest of the list. It is processed by addaslast, which adds the first item to the reverse of the rest and thus creates the reverse of the entire list. This second, auxiliary function is also recursive. We have thus identified a potential candidate.It is now time to study some handevaluations, as we did in A Problem with Structural Processing, to see whether an accumulator helps. Consider the following expression:(invert '(a b c))
Here is how you calculate how invert determines the result when given '(a b c):= (addaslast 'a (invert '(b c))) = (addaslast 'a (addaslast 'b (invert '(c)))) = (addaslast 'a (addaslast 'b (addaslast 'c (invert '())))) = (addaslast 'a (addaslast 'b (addaslast 'c '()))) = (addaslast 'a (addaslast 'b '(c))) = (addaslast 'a '(c b)) = '(c b a) Eventually invert reaches the end of the given list—just like addaslast— and if it knew which items to put there, there would be no need for the auxiliary function. If we are dealing with a function based on generative recursion, we are faced with a much more difficult task. Our goal must be to understand whether the algorithm can fail to produce a result for inputs for which we expect a result. If so, adding a parameter that accumulates knowledge may help. Because these situations are complex, we defer the discussion of an example to More Uses of Accumulation.
Exercise 398. Does the insertion sort> function from Recursive Auxiliary Functions need an accumulator? If so, why? If not, why not?
37.2 Adding Accumulators
Determine the knowledge that the accumulator represents, what kind of data to use, and how the knowledge is acquired as data.
For example, for the conversion of relative distances to absolute distances, it suffices to accumulate the total distance encountered so far. As the function processes the list of relative distances, it adds each new relative distance found to the accumulator’s current value. For the routing problem, the accumulator remembers every node encountered. As the pathchecking function traverses the graph, it conses each new node on to the accumulator.
In general, you want to proceed as follows. Create an accumulator template:
; Domain > Range (define (function d0) (local (; Domain AccumulatorDomain > Range ; accumulator ... (define (function/a d a) ...)) (function/a d0 a0))) Sketch a manual evaluation of an application of function to understand the nature of the accumulator. Determine the kind of data that the accumulator tracks.
Write down a statement that explains the accumulator as a relationship between the argument d of the auxiliary function/a and the original argument d0.
Note The relationship remains constant—
also called invariant— over the course of the evaluation. Because of this property, an accumulator statement is also called an accumulator invariant. Use the accumulator statement to determine the initial value a0 for a.
Also exploit the accumulator statement to determine how to compute the accumulator for the recursive function calls within the definition of function/a.
Exploit the accumulator’s knowledge for the design of the auxiliary function.
For a structurally recursive function, the accumulator’s value is typically used in the base case, that is, the cond clause that does not recur. For functions that use generative recursive functions, the accumulated knowledge might be used in an existing base case, in a new base case, or in the cond clauses that deal with generative recursion.
; [Listof X] > [Listof X] ; construct the reverse of alox0 (checkexpect (invert.v2 '(a b c)) '(c b a)) (define (invert.v2 alox0) (local (; [Listof X] ??? > [Listof X] ; construct the reverse of alox ; accumulator ... (define (invert/a alox a) (cond [(empty? alox) ...] [else (invert/a (rest alox) ... a ...)]))) (invert/a alox0 ...)))
(invert '(a b c))
= (invert/a '(a b c) a0) = (invert/a '(b c) ... 'a ... a0) = (invert/a '(c) ... 'b ... 'a ... a0) = (invert/a '() ... 'c ... 'b ... 'a ... a0)
(define (invert.v2 alox0) (local (; [Listof X] [Listof X] > [Listof X] ; construct the reverse of alox ; accumulator a is the list of all those items ; on alox0 that precede alox in reverse order (define (invert/a alox a) (cond [(empty? alox) (code::hilite a)] [else (invert/a (rest alox) (cons (first alox) a))]))) (invert/a alox0 '())))
Note how once again invert.v2 traverses the list just. In contrast, invert reprocesses every result of its natural recursion with addaslast. Stop! Measure how much faster invert.v2 runs than invert on the same list.
Terminology Programmers use the phrase accumulatorstyle function when they discuss functions that use an accumulator parameter. Examples of functions in accumulatorstyle are relative>absolute/a, pathexists?/a, and invert/a.
37.3 Transforming Functions into AccumulatorStyle
Articulating the accumulator statement is difficult but without formulating a good invariant, it is impossible to understand an accumulatorstyle function. Since the goal of a programmer is to make sure that others who follow understand the code easily, practicing this skill is critical. And formulating invariants is deserves a lot of practice.
The goal of this section is to study the formulation of accumulator statements with three case studies: a summation function, the factorial function, and a treetraversal function. Each such case is about the conversion of a structurally recursive function into accumulator style. None actually call for the use of an accumulator parameter. But they are easily understood and, with the elimination of all other distractions, using such examples allows us to focus on the articulation of the accumulator invariant.
; [Listof Number] > Number ; compute the sum of the numbers on alon (checkexpect (sum '(10 4 6)) 20) (define (sum alon) (cond [(empty? alon) 0] [else (+ (first alon) (sum (rest alon)))]))
; [Listof Number] > Number ; compute the sum of the numbers on alon0 (checkexpect (sum.v2 '(10 4 6)) 20) (define (sum.v2 alon0) (local (; [Listof Number] ??? > Number ; compute the sum of the numbers on alon ; accumulator ... (define (sum/a alon a) (cond [(empty? alon) ...] [else (... (sum/a (rest alon) ... a ...) ...)]))) (sum/a alon0 ...)))
(sum '(10 4)) =  (sum.v2 '(10 4)) =  


a represents the sum of the numbers that alon lacks in comparison to alon0
(define (sum.v2 alon0) (local (; [Listof Number] ??? > Number ; compute the sum of the numbers on alon ; accumulator a represents the sum of the numbers ; that alon lacks in comparison to alon0 (define (sum/a alon a) (cond [(empty? alon) a] [else (sum/a (rest alon) (+ (first alon) a))]))) (sum/a alon0 0)))
Exercise 399. Explain why the natural recursion maintains the correctness of the accumulator statement:Study the above examples before you formulate a general argument.
(sum/a '(10 4 6))
Doing so shows that the sum and sum.v2 add up the given numbers in reverse order. While sum adds up the numbers from right to left, the accumulatorstyle version adds them up from left to right.
> (gseries 5)
(list
#i0.9509900498999999
#i0.96059601
#i0.970299
#i0.9801
#i0.99)
> (sum (gseries 1000.0)) #i0.49746596003269394
> (sum.v2 (gseries 1000.0)) #i0.49746596003269533
; N > N ; compute (* n ( n 1) ( n 2) ... 1) (checkexpect (! 3) 6) (define (! n) (cond [(zero? n) 1] [else (* n (! (sub1 n)))]))
; N > N ; compute (* n0 ( n0 1) ( n0 2) ... 1) (checkexpect (!.v2 3) 6) (define (!.v2 n0) (local (; N ??? > N ; compute (* n ( n 1) ( n 2) ... 1) ; accumulator ... (define (!/a n a) (cond [(zero? n) ...] [else (... (!/a (sub1 n) ... a ...) ...)]))) (!/a n0 ...)))
(! 3) =  (!.v2 3) =  


a is the product of the natural numbers in the interval [n0,n).
Exercise 401. What should the value of a be when n0 is 3 and n is 1? How about when n0 is 10 and n is 8?
(define (!.v2 n) (local (; N N > N ; compute (* n ( n 1) ( n 2) ... 1) ; accumulator a is the product of the natural ; numbers in the interval [n0,n). (define (!/a n a) (cond [(zero? n) a] [else (!/a (sub1 n) (* n a))]))) (!/a n0 1)))
Exercise 402. Like sum, ! performs the primitive computation steps—
multiplication in this case— in reverse order. Surprisingly, this affects the performance of the function in a negative manner. Measure how long it takes to evaluate (! 20) one thousand times. Recall that (time anexpression) function determines how long it takes to run _anexpression.
For the third and last example, we use a function that measures the height of simplified binary trees. The example illustrates that accumulatorstyle programming applies to all kinds of data, not just those defined with single selfreferences. Indeed, it is as common for complicated data definitions as it is for lists and natural numbers.
(definestruct node (left right)) ; A BinaryTree (short Tree) is one of: ; – '() ; – (makenode Tree Tree) (define example (makenode (makenode '() (makenode '() '())) '())) ; Tree > Number ; measure the height of abt0 (checkexpect (height example) 3) (define (height abt) (cond [(empty? abt) 0] [else (+ (max (height (nodeleft abt)) (height (noderight abt))) 1)]))
'()
(makenode '() '())
(makenode (makenode '() (makenode '() '())) '())
; Tree > Number ; measure the height of abt0 (checkexpect (height.v2 example) 3) (define (height.v2 abt0) (local (; Tree ??? > Number ; measure the height of abt ; accumulator ... (define (height/a abt a) (cond [(empty? abt) ...] [else (... (height/a (nodeleft abt) ... aR ...) ... ... (height/a (noderight abt) ... aL ...) ...)]))) (height abt0 ...)))
a is the number of steps it takes to reach abt from abt0.
If abt0 is the complete tree and abt is the subtree pointed to by 1, the accumulator’s value must be 1 because it takes exactly one step to get from the root of abt to the root of abt0.
In the same spirit, for the subtree labeled 1 the accumulator is 2 because it takes two steps to get this place.
(define (height.v2 abt0) (local (; Tree N > Number ; measure the height of abt ; accumulator a is the number of steps ; it takes to reach abt from abt0 (define (height/a abt a) (cond [(empty? abt) a] [else (... (height/a (nodeleft abt) (+ accumulator 1)) ... ... (height/a (noderight abt) (+ accumulator 1)) ...)]))) (height abt0 0)))
Following the design recipe also tells us that we need to interpret the two values to find the appropriate function. According to the purpose statement for height/a, the first value is the height of the left subtree, and the second one is the height of the right one. Given that we are interested in the height of abt itself and that the height is the largest number of steps it takes to reach a leaf, we use the max function to pick the proper one; see figure 111 for the complete definition.
; Tree N > Number ; measure the height of abt0 (checkexpect (height.v2 example) 3) (define (height.v2 abt0) (local (; Tree N > Number ; measure the height of abt ; accumulator a is the number of steps ; it takes to reach abt from abt0 (define (height/a abt a) (cond [(empty? abt) a] [else (max (height/a (nodeleft abt) (+ accumulator 1)) (height/a (noderight abt) (+ accumulator 1)))]))) (height abt0 0)))
Exercise 403. Design an accumulatorstyle version of product, the function that computes the product of a list of numbers. Stop when you have formulated the accumulator invariant and have someone check it.
Exercise 404. Design an accumulatorstyle version of howmany, which is the function that determines the number of items on a list. Stop when you have formulated the accumulator invariant and have someone check it.
Exercise 405. Design an accumulatorstyle version of addtopi, which adds a natural number to pi without using +:
; N > Number ; add n to pi without use + (checkwithin (addtopi 2) (+ 2 pi) 0.001) (define (addtopi n) (cond [(zero? n) pi] [else (add1 (addtopi (sub1 n)))])) Stop when you have formulated the accumulator invariant and have someone check it.
Exercise 406. Design the function makepalindrome, which accepts a nonempty list and constructs a palindrome by mirroring the list around the last item. When given (explode "abc"), it yields (explode "abcba").
Hint Here is a solution designed by function composition:
; [cons 1String [Listof 1String]] > [cons 1String [Listof 1String]] ; create a palindrome by mirroring the given list around the last item (checkexpect (mirror (explode "abc")) (explode "abcba")) (define (mirror s0) (append (allbutlast s0) (list (last s0)) (reverse (allbutlast s0)))) See Generalizing Functions for last; design allbutlast in an analogous manner. This solution traverses s0 four times:
via allbutlast,
via last,
via allbutlast again, and
via reverse, which is ISL+’s version of inverse.
Even with local definition for the result of allbutlast, the function needs three traversals. While these traversals aren’t “stacked” and therefore don’t have a disastrous impact on the function’s performance, an accumulator version can compute the same result with a single traversal.
Exercise 407. Design to10. It consumes a list of digits and produces the corresponding number. The first item on the list is the most significant digit. Hence, when applied to '(1 0 2), it produces 102.
Domain knowledge You may recall from grade school that the result is determined by
Exercise 408. Design the function isprime, which consumes a natural number and returns true if it is prime and false otherwise.
Domain knowledge A number n is prime if it is not divisible by any number between n  1 and 2.
Hint The design recipe for N [>=1] suggests the following template:
Note People who encounter accumulatorstyle programming for the first time often get the impression that they are always faster than their recursive counterparts. Both parts are plain wrong. While it is impossible to explain this mistake in reasoning in this book, let us take a look at the solution of exercise 402:
!
5.760
5.780
5.800
5.820
5.870
5.806
!.v2
5.970
5.940
5.980
5.970
6.690
6.111
The table represents the timings for the two factorial functions. Specifically, the top row shows the number of seconds for 1,000 evaluations of (! 20) where the last cell shows the average. The bottom row shows the result of an analogous experiment with !.v2. Bottom line is the performance of the accumulatorstyle version of factorial is always worse than that of the original factorial function.
38 More Uses of Accumulation
39 Generative Recursion with Accumulators
39.1 Fractals, a Second Taste
Exercise 409. As mentioned, the rightmost image in figure 87 illustrates the generative idea behind the Sierpinski process in a single picture. The given problem is a triangle, that is, three points. Once again, when the triangle is too small to be subdivided any further, the algorithm just draws it. Otherwise, the algorithm finds the midpoints of the three sides and draws the three outer triangles, which implicitly identifies the inner triangle, too.
To translate this description, and especially the partitioning step, into an ISL+ function, it is critical to choose the input data properly. Based on the description, the function consumes three points, each of which is easily represented
obvious choice for a tri
From the perspective of "2htdp/image" drawing a tr
. Let us summarize our discussion with a skeletal ISL+ definition:
; Posn Posn Posn Image > Image ; adds the triangle (a, b, and c) to s ; if it is small enough (define (sierpinski a b c) (cond [(toosmall? a b c) (addtriangle s a b c)] [else (... ...)])) The function consumes three posn structures and returns #t when it is done. The cond expression reflects the general outline of an algorithm. It is our task to define toosmall the function that determines whether the problem is trivially solvable, and addtriangle. In addition, we must still add a ISL+ expression that formulates the partitioning of the triangle.The partitioning step requires the function to determine the three midpoints between the three endpoints. Let us call these new midpoints ab, bc, and ca. Together with the given endpoints, a, b, and c, they determine four triangles:
a, ab, ca;
b, ab, bc;
c, ca, bc;
ab, bc, ca.
Thus, if we wanted to create the Sierpinski triangle for, say, the first listed triangle, we would use (sierpinski a ab ca).Since each midpoint is used twice, we use a local expression to translate the generative step into ISL+. The local expression introduces the three new midpoints. Its body contains three recursive applications of sierpinski and the addtriangle application mentioned earlier. To combine the solutions of the three problems, we use an and expression, which ensures that all three recursions must succeed. Figure 87 collects all the relevant definitions, including two small functions based on domain knowledge from geometry.
Develop the functionsto complete the definitions in figure 87.Use the teachpack "draw.ss" to test the code. For a first test of the complete function, use the following definitions:Create a canvas with (start 400 400). Experiment with other end points and canvas dimensions.
%% —
Exercise 410. The process of drawing a Sierpinski triangle usually starts from an equilateral shape. To compute the endpoints of an equilateral Sierpinski triangle, we can pick a large circle and three points on the circle that are 120 degrees apart. For example, they could be at 0, 120, 240:
(define CENTER (makeposn 200 200)) (define RADIUS 200) ; cicrclpt: Number > Posn ; computes a position on the circle with CENTER ; and RADIUS as defined above (define (circlept factor) ...) (define A (circlept 1/3)) (define B (circlept 2/3)) (define C (circlept 1)) Develop the function circlept.Hint Recall that DrRacket sin and cos compute the sine and cosine in terms of radians, not degrees. Also keep in mind that onscreen positions grow downwards not upwards.
Exercise 411. Rewrite the function in figure 87 to use structures for the representation of triangles. Then apply the new function to a list of triangles and observe the effect.
—
\treepic The left one is the basic step for the generation of the “Savannah” tree on the right. It is analogous to the picture in the middle of figure 86. Develop a function that draws trees like the one in the right picture.Hint Think of the problem as drawing a straight line, given its starting point and an angle in, say, radians. Then, the generative step divides a single straight line into three pieces and uses the two intermediate points as new starting points for straight lines. The angle changes at each step in a regular manner.
Exercise 413. In mathematics and computer graphics, people must often connect some given points with a smooth curve. One popular method for this purpose is due to Bézier.Dr. Géraldine Morin suggested this exercise. Here is a sequence of pictures that illustrate the idea:—
\bezierpic For simplicity, we start with three points: p1, p2, and p3. The goal is to draw a smooth curve from p1 to p3, viewed from p2. The original triangle is shown on the left; the desired curve appears on the right.To draw the curve from a given triangle, we proceed as follows. If the triangle is small enough, draw it. It appears as a large point. If not, generate two smaller triangles as illustrated in the center picture. The outermost points, p1 and p3, remain the respective outermost points. The replacements for the point in the middle are r2 and q2, which are the midpoints between p1 and p2 and between p2 and p3, respectively. The midpoint between r2 and q2 (marked with ) is the new leftmost and rightmost endpoint, respectively, for the two new triangles.
To test the function, use the teachpack "draw.ss". Here is some good test data:Use (start 300 200) to create the canvas. Experiment with other positions.
39.2 Gaussian Elimination, Again
(define M '((0 4 5) (1 2 3))) (define M1 '((1 2 3) (0 4 5))) (checkexpect (rotateuntil.v1 M) M1) (define (rotateuntil.v1 l0) (local ((define (rotateuntil l seen) (cond [(not (= (first (first l)) 0)) (cons (first l) (append seen (rest l)))] [else (rotateuntil (rest l) (cons (first l) seen))]))) (rotateuntil l0 '()))) (checkexpect (rotateuntil.v2 M) M1) (define (rotateuntil.v2 l) (cond [(not (= (first (first l)) 0)) l] [else (rotateuntil.v2 (append (rest l) (list (first l))))])) (define N 10000) (define (run N rotateuntil) (local ((define large (append (buildlist N (lambda (i) `(0 ,(+ (random (+ i 1)) 1) 0 0))) '((1 2 3 0))))) (time (first (rotateuntil large))))) (buildlist 10 (lambda (i) (run (* i 1000) rotateuntil.v1))) (buildlist 10 (lambda (i) (run (* i 1000) rotateuntil.v2)))
40 Summary
This sixth part of the book is about the design of functions that employ generative recursion
This fifth part of the book shows
... logical reasoning ...