home—lectures—recipe—exams—hws—D2L—breeze (snow day)
tail-recursion, scope, trees
Due Nov.16 (Fri) in class for 10% extra-credit,
or Nov.26 (Mon) 23:59.
Hardcopy, and on D2L.
Note: Some point-values will be increased from what is currently shown, by about 25-50%.
Reading: Scott §3.6.4 (Lambda expressions); §11, but skip 11.4 and 11.5 (OCaml and Evaluation Order, respectively).
Your name and the assignment-number
must be in a comment at the start of the file,
and your hardcopy must be stapled.
All functions/data must include the appropriate steps of the design recipe.
In particular, test cases alone might be worth half the credit for a function.
Unless otherwise indicated, two test cases will suffice for most problems,
if they are testing different situations.
For this (and future) assignments, bump up your DrRacket language-level to
Intermediate Student with lambda.
Do not call any of the following functions:
-
list (except when making test-cases)
-
list-ref, take, drop and similar built-ins
(unless you write them yourself, following the design-recipe)
-
append (unless you write it yourself, following the design-recipe)
-
remove (unless you write it yourself, following the design-recipe)
-
any functions with a “!” in their name, such
as set! and set-rest!.
(4pts)
Write my-list-ref, which takes a list and an index,
and returns the list item at the indicated index (0-based).
(my-list-ref 2 (list 'a 'b 'c 'd 'e))
will return 'c.
In Java, this function is called List#get(int).
Your signature should include a type-variable such as α or T.
The pre-condition
is that the index is less than the length of the list.
Of course, do not just call the built-in list-ref;
you should follow the data-definition for natural numbers,
instead of for lists.
(So do not check for the empty-list.)
data def:
A natural-number is:
- 0, OR
- (+ 1 [natural-number])
The predicates zero? and positive? are often used
to distinguish the two branches,
though of course = and > could be used equally-well.
See also the
D2L post
about viewing sub1 as the "getter" to pull out the "natural-number field, which a
positive is built out of".
- (2pts)
A tail-recursive function is one where
after making a recursive call.
Note:
Note that being tail-recursive is a property of a function’s source-code.
The fact that a tail-recursive function can be optimized
to not unnecessarily-allocate stack space is
a compiler-implementation issue — albeit
it’s what makes the concept of tail-recursion important.
Reading: Scott also discusses recursion and tail-recursion,
in §6.6.1 (both 3rd and 4th eds).
- (5pts) Based on Exercise 11.6b from Scott (third ed., 10.6b), min:
-
First, complete the following Java while-loop,
in spirit similar to stringAppendWhoa
from lecture.
#|
/** Return the smallest number in a list.
* @pre <code>!nums.isEmpty()</code>
* @return the smallest number in `nums`.
*/
static Double myMin( List<Double> nums ) {
// initialize our loop-variables:
double minSoFar = nums.get( );
List<Double> numsRemaining = nums.subList( ,nums.size());
while ( ) {
double a = numsRemaining.get(0); // corresponding to Scott’s variable `a`
minSoFar = ( ? : );
numsRemaining = ;
}
return minSoFar;
}
|# |
(Your code must be legal Java, but you don't need to submit an extra .java file —
you can just paste the method into a #| racket block comment |#.)
-
Now, convert the above code to a tail-recursive racket function.
Use corresponding names (e.g. “my-min”, “nums-remaining”, etc.).
Include signature, purpose-statement, and test-cases for both your main function and your helper.
Btw:
The book’s starting-code calls
(empty? (rest l)) — something not in the template.
It’s a bit of a hack to stray from the template:
Scott wants to avoid making a helper-function,
but still return a sentinel-value answer for empty-lists.
However, when converting to tail-recursion, this difference ends up being moot:
as you make a helper/wrapper function for the tail-recursion, that extra check disappears.
scheme vs racket:
The book’s scheme code uses:
car, cdr, null?, and #t.
In racket, these names are (respectively):
first, rest, empty?, and #true.
- (5pts) Inspired by Scott's exercise about log2 (11.6a; third ed. 10.6a):
Here is a function to convert a number to its base-2 representation:
(check-expect (natnum->string/binary 0) "")
(check-expect (natnum->string/binary 1) "1")
(check-expect (natnum->string/binary 2) "10")
(check-expect (natnum->string/binary 3) "11")
(check-expect (natnum->string/binary 4) "100")
(check-expect (natnum->string/binary 5) "101")
(check-expect (natnum->string/binary 15) "1111")
(check-expect (natnum->string/binary 16) "10000")
; natnum->string/binary : natnum -> string
; Return the binary-numeral representing n (without any leading zeroes).
; Note that the numeral for zero, without leading zeros, is the empty-string!
;
(define (natnum->string/binary n)
(cond [(zero? n) ""]
[(positive? n) (string-append (natnum->string/binary (quotient n 2))
(if (even? n) "0" "1"))]))
|
Btw:
This code doesn’t quite follow the design-recipe for natural-numbers,
because it recurs on (quotient n 2) rather than (sub1 n).
But it still works fine because it “reduces” the natnum
to a smaller one.
To reason about this code, you wouldn’t use straight-up mathematical induction;
instead you'd call it “strong induction”.
-
The above code is not tail-recursive,
because after the recursive call, it must still call .
-
Give a tail-recursive version of this function.
(Be sure to include tests, purpose-statement, etc. for any helper function you write.)
-
Recall:
the scope of identifiers introduced with let is
just the body of the let,
while
the scope of identifiers introduced with let* is
the body of the let and all following right-hand-sides of the let*.
Recall: a variable-use's binding-occurrence is
the place where that variable is defined.
- (4pts)
For each variable-use of a below,
indicate where it gets its value from — its binding-occurence.
For example, if a was used in some line F7,
and that use’s binding occurrence was the global declaration in line 01,
write “01 → F7”.
Another use of a might cause you to write something like “G3 → G6”.
Hint:
The binding-occurrence itself is not considered a use of the variable.
There are a total of seven uses of a, amongst the four parts.
- (2pts)
Fill in the blank, with the result of evaluating the expression.
In all cases, presume we have:
line 01 (define a 5)
line 02 (define b 10) |
-
line A1 (let {[z 50]
line A2 [a 51]
line A3 }
line A4 (+ a b z))
; evaluates to: |
-
line B1 (let {[z 50]
line B2 [a 51]
line B3 [b (* a 3)]
line B4 }
line B5 (+ a b z))
; evaluates to: |
-
line C1 (define (foo a)
line C2 (let {[z 50]
line C3 [a 51]
line C4 [b (* a 3)]
line C5 }
line C6 (+ a b z)))
line C7 (foo 1001)
; evaluates to: |
-
line D1 (let* {[z 50]
line D2 [a 51]
line D3 [b (* a 3)]
line D4 }
line D5 (+ a b z))
; evaluates to: |
-
Notice that
several of the image-creating functions imported via
(require 2htdp/image)
are similar, in that they happen to take four arguments:
two non-negative numbers v and w,
a drawing mode (e.g. 'solid or #o222 (a transparency))
and a color.
Two such examples are
ellipse
and
rhombus.
(3pts)
Let’s write a function shapes-in-a-row which takes in a list containing such functions,
and returns an image that is the result of calling each function with the arguments
54, 40, #o222, and 'lightCoral,
and putting all the images beside each other:
(check-expect (shapes-in-a-row (list ellipse right-triangle rhombus))
(beside (ellipse 54 40 #o222 'lightCoral)
(beside (right-triangle 54 40 #o222 'lightCoral)
(beside (rhombus 54 40 #o222 'lightCoral)
empty-image))))
|
Make sure you've increased your language-level to “Intermediate
Student with lambda”, as mentioned above.
When writing the signature for shapes-in-a-row,
don’t just say one input is of type “function”; give its full
signature.
This function and the next do not need to be tail-recursive — the goal of this exercise is
to be comfortable with passing functions.
(2pts)
Pass your function a list containing
-
a shape-drawing-function which (when passed v,w,mode,color) will create a
5-sided
star
with v as its side-length,
of the indicated mode & color (and w is unused).
(shapes-in-a-row will of course pass your function
the arguments 54,40,#o222,'lightCoral).
and
-
a shape-drawing-function which (when passed v,w,mode,color) will create a
pulled-regular-polygon
with sides v long,
having w sides,
a pull of 0.9
and
angle of 20
of the indicated mode and color.
Don’t name these functions; use lambda.
Do not, of course, modify your previous code for shapes-in-a-row.
- (3pts) Scott, Exercise 11.7b (third ed: 10.7b), filter.
Call your function my-filter;
do not use the built-in function filter, of course.
This function does not need to be tail-recursive — the goal of this exercise is
to be comfortable with passing functions.
Hint: Using the name “keep?” for one of your parameters is a good, descriptive name.
(2pts): using my-filter,
re-write
count-bigs
and
aliens-remaining
as one-liners.
tentative: I will make this problem slightly easier,
asking for something like of aliens-not-remaining.
- (5pts)
Write the function count-name,
which takes in an anc-tree (as in lecture)
and a string,
and returns how many times that name occurs as a name in the anc-tree.
For this problem and the next:
Do not try to make this tail-recursive, or use an accumulator variable.
A linear loop fundamentally can't process a branching tree!
- (5pts)
Write a function that takes in an anc-tree,
and returns a similar anc-tree where eye-colors might be changed:
In particular, brown eyes have been changed to green,
except that if you reach an ancestors with red eyes
then don’t change the eye-colors of them or their ancestors.
Call your function brown->green/stop-at-red.
home—lectures—recipe—exams—hws—D2L—breeze (snow day)
This page licensed CC-BY 4.0 Ian Barland Page last generated | Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu |
|