EBoard 21: Numeric recursion

Warning This class is being recorded (and transcribed).

Approximate overview

  • Administrivia
  • A bunch of stuff from Monday
  • Questions
  • Lab

Administrivia

  • Happy halfway point!
  • I’ve had a request to permit free late submissions of MP4. You may submit MP4 without penalty until Saturday night. You may submit the MP4 post-assessment without penalty until Sunday night.
  • I anticipate getting the Gradescope page for MP4 up this afternoon or evening.
  • If you are struggling because of the conflict (or the world’s varied reactions to the conflict), let me know how I can help. I’m certainly willing to push deadlines.
  • It appears that my office hours today and tomorrow are nearly completely booked (completely booked today, just a little time tomorrow). If you’d like to meet with me, drop me a note and we’ll see what we can work out. (Preferred times: noon-1pm and 3:00-3:30pm today; 10:00am-noon tomorrow.

Upcoming Token activities

Academic

Cultural

Peer

  • Football, 1pm, Saturday 21 October 2023.

Wellness

  • Have a relaxing and rejuvinating fall break.

Misc

Other good things

Upcoming work

  • Thursday night: MP4
  • Thursday night: NO READING DUE!
  • Friday morning: Today’s lab due (normal policy)
  • Friday Quiz
  • Saturday night: Permitted late MP4

Friday’s Quiz

Topics

  • New topic: Local bindings.
  • Repeat topics: Lists and the big three, List recursion
  • Optional topics (you must email me by Wednesday evening if you want a quiz on one of these topics): Tracing, documentation

Timing and such

  • I’ll be here at 7:30 a.m. on Friday for those who want to take multiple quizzes.
  • You can bring a sheet of paper (8.5x11 or A4) with hand-written notes if you think it will help.

Studying for quizzes

  • Try lab problems related to the topic
    • On paper, not on DrRacket
    • If you have to look up something, write it down.
  • Write your own similar problems (and solve them)
  • A brain dump never hurts.

Sample question

Refactor redundancy and add clarity in computations with let-bindings.

Consider the following procedure that contains some repetitious code.

;;; (letter->number ch) -> either integer? boolean?
;;;   ch : char?
;;; Converts ch to the corresponding number in the English alphabet.
;;; (1 for #\a or #\A, 2 for #\b or #\B, etc.).  Returns false (#f)
;;; if ch is not a letter in the English alphabet.
(define letter->number
  (lambda (ch)
    (cond
      [(<= (char->integer #\a) (char->integer ch) (char->integer #\z))
       (+ 1 (- (char->integer ch) 97))]
      [(<= (char->integer #\a) (+ (char->integer ch) 32) (char->integer #\z))
       (+ 1 (- (+ (char->integer ch) 32) 97))]
      [else #f])))

(check-equal? (map letter->number (string->list "abcde"))
              '(1 2 3 4 5)
              "First five lowercase letters")
(check-equal? (map letter->number (string->list "ABCDE"))
              '(1 2 3 4 5)
              "First five uppercase letters")
(check-equal? (map letter->number (string->list "XYZ"))
              '(24 25 26)
              "Last three uppercase letters")
(check-equal? (map letter->number (string->list "xyz"))
              '(24 25 26)
              "Last three lowercase letters")
(check-equal? (letter->number #\.)
              #f
              "Not a letter")

As you know, we should avoid redundant computations and magic numbers. Using local bindings (let or let*), remove the redundant computations and magic numbers from letter->number. You need not change the primary stucture of the cond, but you should not compute the same value twice.

Note: In case you didn’t know, 32 is the result of subtracting the collating sequence number of #\A from the collating sequence number of #\a. By adding 32, we switch from uppercase to lowercase. And 97 seems to be the collating sequence number of #a, but we probably shouldn’t count on that.

A different way to write select-odds

Here’s a way that Ellie and Ella and Sam tried helping some folks with select-odds. I like it because it emphasizes the recursion.

(define select-odds
  (lambda (nums)
    (if (null? nums)
        null
        (let ([remaining-odds (select-odds (cdr nums))])
          (if (and (integer? (car nums)) (odd? (car nums)))
              (cons (car nums)
                    remaining-odds)
              remaining-odds)))))

Many ways to write longest-string

I like longest-string because it suggests multiple approaches.

#|
Implement a procedure, `(longest-word words)`, that takes a nonempty list
of strings as input and finds the longest string in the list.  If there
are multiple strings that have the same length and are longer than any
other strings in the list, you can return any of them.

You may not use `sort` or `reduce` to solve this problem.  (You've
guessed it; this procedure helps you understand how one of the
forms of `reduce` might be implemented.)
|#

;;; (longest-word words) -> string?
;;;   words : list-of string? (nonempty)
(define longest-word
  (lambda (words)
    ???))

A straightforward way. Compare the recursive result to the first word and take the longer of the two.

(define longest-word
  (lambda (words)
    (if (singleton? words)
        (car words)
        (if (> (string-length (car words))
               (string-length (longest-word (cdr words))))
            (car words)
            (longest-word (cdr words))))))

The straightfoward way, rethought with a helper procedure to avoid duplicating work. In my world, this more closely matches the English-language description.

(define longer-word
  (lambda (word1 word2)
    (if (> (string-length word1) (string-length word2))
        word1
        word2)))

(define longest-word
  (lambda (words)
    (if (singleton? words)
        (car words)
        (longer-word (car words) (longest-word (cdr words))))))

The straightforward way, using a local binding to name the recursive result.

(define longest-word
  (lambda (words)
    (if (singleton? words)
        (car words)
        (let ([longest-remaining (longest-word (cdr words))])
          (if (> (string-length (car words)) (string-length longest-remaining))
              (car words)
              longest-remaining)))))

Twisting things around: Compare the first two words.

(define longest-word
  (lambda (words)
    (if (singleton? words)
        (car words)
        (if (> (string-length (car words)) (string-length (car (cdr words))))
            (longest-word (cons (car words) (cdr (cdr words))))
            (longest-word (cdr words))))))

TPS: Load the eboard, look at the variants. Which do you prefer? Why?

  • To some folks, the last one feels more like (a) how they’d do it by hand and (b) how reduce (or at least reduce-left) works.
  • To other folks, the first few were simpler.
  • The term longer-word helps with readability.
(define longest-word
  (lambda (words)
    (if (singleton? words)
        (car words)
        (longest-word (cons (longer-word (list-ref words 0) (list-ref words 1))
                            (cddr words))))))

awesum

Consider the problem of adding up all the numbers in a nested list of a form something like the following.

'(3 (4 5) (6 (7 (8 9) (10 (11)))))

As you’ve seen in the mini-project, we call such lists “deeply nested”. A deeply nested list of numbers is a list that contains only numbers and deeply nested lists of numbers.

;;; (awesum numbers) -> number?
;;;   numbers : a deeply nested list of numbers
;;; Add up all of the numbers in numbers.
(define awesum
  (lambda (numbers)
    ???))

We’ll assume that numbers is correctly formed (that is, it is a list of either numbers or deeply nested lists of numbers).

TPS: Base case, easy recursive case, harder recursive case.

(test-equal? "empty list" (awesum '()) 0)
(test-equal? "simple list" (awesum '(1 2 1)) 4)
(test-equal? "slightly nested list" (awesum '(4 (2 3) 5)) 14)
(test-equal? "more deeply nested list" 
             (awesum '(1 ((2) 3 () (4 (5 (6))) (7))))
             28)

(define awesum
  (lambda (numbers)
    (if (null? numbers)
        0
        (if (number? (car numbers))
            (+ (car numbers) (awesum (cdr numbers)))
            (+ (awesum (car numbers)) (awesum (cdr numbers)))))))


(awesum '(1 ((2) 3 () (4 (5 (6))) (7)))) --> (+ 1 (awesum '((2) 3 () (4 (5 (6))) (7)))) --> (+ 1 (+ (awesum '(2)) (awesum '(3 () (4 (5 (6))) (7))))) --> (+ 1 (+ (+ 2 (awesum '())) (awesum '(3 () (4 (5 (6))) (7))))) --> (+ 1 (+ (+ 2 0) (awesum '(3 () (4 (5 (6))) (7))))) --> (+ 1 (+ 2 (awesum '(3 () (4 (5 (6))) (7))))) --> (+ 1 (+ 2 (+ 3 (awesum '(() (4 (5 (6))) (7)))))) --> (+ 1 (+ 2 (+ 3 (+ (awesum '()) (awesum '((4 (5 (6))) (7))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (awesum '((4 (5 (6))) (7))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ (awesum '(4 (5 (6)))) (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ (+ 4 (awesum (5 (6)))) (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ (+ 4 (+ 5 (awesum '(6)))) (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ (+ 4 (+ 5 (+ 6 (awesum '())))) (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ (+ 4 (+ 5 (+ 6 0))) (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ (+ 4 (+ 5 6)) (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ (+ 4 11) (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ 15 (awesum '((7)))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ 15 (+ (awesum '(7)) (awesum '()))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ 15 (+ (+ 7 (awesum '())) (awesum '()))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ 15 (+ (+ 7 0) (awesum '()))))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ 15 (+ 7 0)))))) --> (+ 1 (+ 2 (+ 3 (+ 0 (+ 15 7))))) --> (+ 1 (+ 2 (+ 3 (+ 0 22)))) --> (+ 1 (+ 2 (+ 3 22))) --> (+ 1 (+ 2 25)) --> (+ 1 27) --> 28 ```

Questions

Administrative

Numeric recursion

I’m confused as to how the “partof” label applies to numeric recursion. I understand how it applies in regard to lists, but it just doesn’t make sense to me in the examples given from the reading.

For numeric recursion, partof is almost always just the number.

MP4

I’m getting an error with rgb-red.

It should be color-red.

Can I have an extension until Saturday night?

Yes.

Can we assume that all sublists have at least two elements?

For an M, yes. For an E, you must handle singleton lists.

Hint: Write something that checks for these cases, does the appropriate thing for them, and applies beside or above in the remaining cases. (I think that’s the only time it really matters.)

Other

Lab

Copyright © Eric Autry, Charlie Curtsinger, Sarah Dahlby Albright, Janet Davis, Nicole Eikmeier, Fahmida Hamid, Priscilla Jiménez, Barbara Johnson, Titus Klinge, Peter-Michael Osera, Samuel A. Rebelsky, John David Stone, Anya Vostinar, Henry Walker, and Jerod Weinman.

Unless specified otherwise elsewhere on this page, this work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/3.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.

This website was built using Jekyll, Twitter Bootstrap, and the Bootswatch Cosmo Theme.