ITEC380 lists, scope, tail-recursion

lists, scope, tail-recursion

Due ♣ (Thu) at start of class. Submit via D2l and hardcopy.

Reading: Scott §§ 3.3.0–3.3.3 (scope), § 6.6 (tail-recursion).

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.html. 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:

sublist or take, since that's one of the problems below!

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!. They aren't in intermediate-student, anyway.

Write the function count-bigs : (-> real? (listof number?) natural?) 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. (The data-definition for list-of-number has already been given in lecture, so you don't need to repeat steps 1-3 of the design recipe for list-of-number.)

Use template: Your solution should follow the template for processing lists. Do not make it tail-recursive.

Remember: 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 empty)))), 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; it's the one that can really make things click!

Write the racket function map-sqr : list-of-number → list-of-number, which squares each number in a list; do not call map .

Use template: Your solution should follow the template for processing lists. Do not make it tail-recursive.

To help you out, here are some test cases; no further ones are required.

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

processing a recursive datatype definition:

The Design Recipe

Who doesn't love binge-watching TV shows?² After extensive research to determine what aspects of a TV series are important for binge-watching information, I have personally determined that most shows have plot threads which may span several episodes. It's not even important what the plot threads are; a true connoisseur cares only about how many plot threads there are.

A binge-task is one of:

A cliff-hanger, which contains three things: a number (how many existing plot threads are resolved), another number (how many new plot threads are introduced), and the remaining-show — a binge-task.
A moral, which: introduces either 0 or 1 plot threads (never more); never resolves any; contains a moral (like Be nice., or A fool might show great wisdom, like Phoebe. (Or might not, like Joey.) ); and the remaining-show — a binge-task.
A finale, which has only one piece of interesting info: how many plot threads are resolved. (None are introduced.) It's the last episode of a binge-task; there is nothing more.
A shark-jump: No plot threads are introduced, and exactly two are resolved. But it's so contrived that everybody stops watching their binge-task, so there is nothing more after that.

List-like, but not lists: Although binge-tasks are not lists, they are certainly reminiscent of them: For example, finales and shark-jumps (like empty-lists) cannot possibly followed by any additional tasks. However, cliff-hangers and morals (like cons structs) do have information about an episode, “followed” by one more binge-task (which may be another cliff-hanger which itself contains yet another binge-task, etc.).
Compare this to how we represent a list of a thousand numbers really being a cons struct with only two fields: the first number, and the remainder of the list (which is another cons which itself contains yet another cons, etc.).

So: Do not use built-in lists; everything you need comes straight from the definition above.

Give a racket data-definition to represent a binge-task. Do this by having functions named binge-task?, as well as finale?, — just like we had anc-tree?, child?, and unknown? defined in anc-tree.rkt. Of course, some of these functions might get made for you via define-struct/c.
Hint 1: As always, if you introduce compound data you need to provide both the names and types of the fields (use a define-struct/c) , as we did in anc-tree.rkt. ~~and the type of the field (in a sample make-structname)~~.

Hint 2: In cases where you don't have more than one piece of information to track, you don't need to introduce any compound-data.

warning: Make sure that you can distinguish between a shark-jump, and a finale that happens to resolve two threads (they are different). Also, do not try to represent all the above using a single struct -- one which contains a number-of-threads-introduced and a number-resolved and some sort of tag, plus further fields that are only meaningful depending on the tag. That would be sloppy data-modeling; a shark-jump struct/object shouldn't contain fields that are meaningless, nor fields whose value is a function of other fields ³.
Make five examples of binge-tasks (each different from each other in an interesting way). Give names to them (using define); four suggested names are provided; be sure to provide the close-paren.
(define finale0 (define shark0 (define moral1 (define cliffhanger1 (define
Note that to build examples from our definition, your first example(s) must necessarily be ones that don't contain a remainder-of-the-binge-task.

Write the function count-morals which is given a binge-task, and returns how many (possibly nested) morals it contains.

(check-expect (count-morals finale0)         )
(check-expect (count-morals shark0)         )
(check-expect (count-morals moral1)         )
(check-expect (count-morals cliffhanger1)         )
(check-expect (count-morals                         )         )

Your function should follow the template directly. Thus it should not be tail-recursive. You do not need to write the template-for-binge-tasks, but certainly all its steps are required for writing the above function.

Write the function net-unresolved : binge-task -> number
which returns how many plot threads are introduced, minus how many are resolved.

Note: If somebody starts a binge-task halfway through, this might be a negative number, if they see a thread resolved that they never saw originally introduced ⁴ .

(check-expect (net-unresolved finale0)         )
(check-expect (net-unresolved shark0)         )
(check-expect (net-unresolved moral1)         )
(check-expect (net-unresolved cliffhanger1)         )
(check-expect (net-unresolved                         )         )

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 ancestor with red eyes then don’t change the eye-colors of them or their ancestors. Call your function brown->green/stop-at-red⁶.

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.

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

A tail-recursive function is one where after making its 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).

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, running 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 tail-recursive racket function(s). Include signature, purpose-statement, any pre-conditions, and test-cases for both your main function and your helper. Use the same function/variables names as the Java code (up to idiomatic differences — e.g. my-min instead of myMin, etc.).
: The goal of this problem is to have your racket code correspond nearly word-for-word to the above Java loop, computing the same result in exactly the same way. So each expression/step in one version should correspond directly to an expression/step in the other, with a racket helper-function corresponding to the java while, just as in the lecture examples. E.g. since the Java version has a variable a which is local to the loop, your racket code should do the same.

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.

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) "")    ; Note that we remove (all) leading zeroes (!)
(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")
(check-expect (natnum->string/binary (+ 1024 8 4)) "10000001100")

(check-expect (natnum->string/binary #xA) "1010")  ; hex literal
(check-expect (natnum->string/binary #xFFFF) "1111111111111111")
(check-expect (natnum->string/binary #xfeedBee) "1111111011101101101111101110")

;
(define (natnum->string/binary n)
    (-> natural? string?)
    ; Return the binary-numeral representing n (without any leading zeroes).
    ; Note that the numeral for zero, without leading zeros, is the empty-string!
    ;
    (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 . Observe how the if could be fully evaluated before the recursive call!
Give a tail-recursive version of this function. (Be sure to include tests, purpose-statement, etc. for any helper function you write.)

¹ 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. ↩

² Who'd love to have enough time to binge-watch a show? ↩

³ A field which is a function of the other fields is a violation of 2nd Normal Form, in database-speak. In O.O., we might have a getter without having a backing field. ↩

⁴ Heck, if the writers resolve a thread that never was introduced, this could be negative?! Our data-definition doesn't preclude that. It would be reasonable to do so (if you want to rule out later writing prequels). However, that property is one that isn't a function of the binge-task itself; it relies on information about binge-tasks that refer to it. Thus the current datatype-definition and its template is not appropriate, or at least not self-contained. ↩

⁶ 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 anc-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.⁶ ↩

⁷ 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. ↩

This page licensed CC-BY 4.0 Ian Barland
Page last generated

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