ITEC380 hw06 -- lists and trees

hw06
lists and trees
incl. tail-recursion

Due Oct.31 (Mon) 15:00.

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—the design recipe: final version. 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.

Complete problems in racket, except for 5 and 6 which you’ll complete in Java and racket, as instructed. Your Java method should compile and run and be correct, but then you can paste it into a racket block-comment (#| … |#) so that you only need submit one file. Make sure it is property formatted, of course.

Unless otherwise indicated, all problems are to be written in Racket, in Beginning-student. Do not call any of the following functions:

list

append (unless you write it yourself, following the template)

remove (unless you write it yourself, following the template)

any functions with a “!” in their name, such as set! and set-rest!.

(4pts) Write the function count-bigs : real, list-of-real → natnum, which takes in a threshold and a list of numbers, and returns how many of them are larger than the threshold. To help you out, here are some test cases; no further ones are required.

hint: We can’t re-assign to variables, in functional programming. So we won’t have a counter which we increment, like you might in your imperative-programming class. Instead, be sure to follow the design recipe, and after copying the template, think about the inventory-with-values (assuming we call our parameters “threshold” and “nums”): if we call count-bigs with the particular inputs (count-bigs 3 (cons 10 (cons 2 (cons 5 '())))), what is…

threshold =

nums =

(first nums) =

(rest nums) =

(count-bigs threshold (rest nums)) =

Fill in each blank with a particular number, or list-of-numbers. Then, ask yourself: Starting with those pieces of info, how do I assemble them to get my desired result of 2?
(You don’t need to include the above in your answer — it’s just to remind you of what you do, for the “inventory-with-values” step of the design-recipe, #6. If you get stuck on any of the problems below, make sure you didn’t skip this step!)

(4pts) Write the racket function map-sqr : list-of-number → list-of-number, which squares each number in a list; do not call map (or, my-map). To help you out, here are some test cases; no further ones are required.

  (check-expect (map-sqr '())  
                '())
  (check-expect (map-sqr (cons 7 '())) 
                (cons 49 '()))
  (check-expect (map-sqr (cons 9 (cons 7 '())))  
                (cons 81 (cons 49 '())))

(5pts) 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 (cons 'a (cons 'b (cons 'c (cons 'd (cons 'e '())))))) will return 'c. Of course, follow the design recipe; do not just call the built-in list-ref.

hint: Follow the template for natural-numbers — not for lists!

I will only run your code on lists that meet the pre-condition that the index will be less than the length of the list. (If it isn’t, it’s fine for your function to have a run-time exception.)

Write a function list-ref/random which takes in a list, and returns a random element. (You don’t need any unit-tests for this, since there isn’t one exact desired result.)

Notice that several of the image-creating functions in imported via (require 2htdp/image) are similar, in that they take four arguments: two non-negative numbers v and w, a drawing mode (e.g. 'solid) and a color. Two such examples are ellipse and rhombus.

(5pts) 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, 'solid, and 'orange, and putting all the images beside each other:

      (check-expect (shapes-in-a-row (cons ellipse (cons right-triangle (cons  rhombus '()))))
                    (beside (ellipse 54 40 'solid 'orange)
                            (beside (right-triangle 54 40 'solid 'orange)
                                    (beside (rhombus 54 40 'solid 'orange)
                                            empty-image))))

When writing the signature for shapes-in-a-row, don’t just say one input is of type “function”; give its full signature .

language:For this problem and the next, you’ll need to switch DrRacket's language level to “Intermediate Student with lambda” (so that you can mention a function without calling it). Although Intermediate Student also includes the function list, do not use it for this homework; build lists via cons. After this homework, use of list will be allowed.

Extra credit (2pts): Without modifying your function, pass it a list containing

a shape-drawing-function which (when passed v,w,mode,color) will create a star with v sides, of the indicated mode & color (and w is unused).
(shapes-in-a-row will of course pass your function the arguments 54,40,'solid,'orange).
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.

(5pts) Scott, problem 10.7b (filter). Call your function my-filter; do not use the built-in function filter, of course.

Extra Credit (2pts): using my-filter, re-write count-bigs as a one-liner.

(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.

(5pts) Based on problem 10.6b from Scott (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 min( List<Double> nums ) {
        // initialize our loop-variables:
        double minSoFar = nums.get(    );
        List<Double> numsRemaining = nums.subList(    );

        while (                          ) {
            double a = numsRemaining.get(0);  // corresponding to Scott’s variable `a`
            minSoFar = (               ?            :      );
            numsRemaining =                             ;
            }
        return minSoFar;
        }

Now, convert the above code to a tail-recursive racket function. Call the function my-min (to avoid conflict with the built-in min).
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 10.6a from Scott (log2): 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"))]))

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.)

Btw: This code doesn’t quite follow the design-recipe for natural-numbers, because it uses quotient rather than sub1. 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”.

(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.

(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 bluebrown->green/stop-at-red.

¹ Your final program doesn’t need to include any "transitional" results from the template: For example, you don’t need the stubbed-out version of a function from step 5. However, you should still have passed through this phase. ↩

²For example, when sorting a list-of-songs, we might write sort : list-of-song, (song, song → boolean) → list-of-song.
(Though in the case of sort, “song” could be replaced by any type, so we used a type-variable like α or (in Java) <T>. That’s not needed here; we already know the exact the signature of the functions that shapes-in-a-row receives.) ↩

³In many languages, we'd call this the "adaptor pattern", and might write entire classes and interfaces, instead of just using an anonymous function. ↩

⁴ Realize that numbers, numerals, and digits are three distinct concepts. In programming, the distinction becomes clear: numbers/numerals/digits correspond to double/string/char, respectively. ↩

⁵I'll accept answers which change either blue eyes, or brown eyes. ↩

⁷ Well, more seriously: we’ll do an equivalent tree-traversal in the future, when working with parse-trees for a programming-language:
we’ll want to re-name all occurrences of a variable x, but if we come across a new variable-declaration named x, that’s making a new, different variable — so don’t change that x, nor any x in sub-trees of that declaration. We say that the newly-declared x is shadowing the original x being re-named. ↩

⁶ People sometimes wonder what possible use-case such a function could have. Well: Sometimes you want to doctor an ancestor-tree, to make yourself appear to be irish. But if you have an ancestor who cried so much that their eyes were red — probably on hearing how you seem to be ashamed of your heritage — we won’t modify their ancestors out of respect. ↩

Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu

hw06 lists and treesincl. tail-recursion

hw06
lists and trees
incl. tail-recursion