EBoard 21: Pause for breath

This class will be recorded! Its use is limited to members of the class. Please do not share with others.

Approximate overview

  • Administrative stuff [~10 min]
  • Q&A [~10 min]
  • All sorts of stuff [~70 min]

Administrative stuff

Notes and News

  • Happy Monday! It’s sunny in Grinnell.
  • Friday’s lab was clearly more complicated than intended. I thought we’d use today to go over it and some other issues related to recursion.
  • You should know the drill on evening tutoring. Please use the evening tutors. Please consider visiting them in person (if you are on campus).
    • Tutors can also work with you on learning things, such as tracing.

Upcoming activities and other token-earning things

Events

  • Mentor session Wednesday at 7 pm.
    • Write it up to get a token.
  • CS Table Monday, 8 March 2021 at noon. Chapter 2 of the book.
  • March 2, 10:00-11:30 or 7:00-8:30: Restorative Justice Community Event
  • WGMC presents Ethics and Social Justice in CS. 6pm, Wednesday, 3 March 2021.
  • Journalism Ethics Workshop, 7:00-8:30 pm, Thursday, March 4 and Tuesday, March 9

Upcoming work

I’m not sure if all of these links are correct. Let me know if any are not.

  • Mini-project 4 is due TONIGHT
  • There is no reading response for tomorrow.
  • These is no lab writeup for tomorrow.
  • Quiz tomorrow: Numeric recursion

Q&A

How do I match the start of a string or the end of a string?

If you update the csc151 library, you’ll now have (rex-start-of-string) and (rex-end-of-string). Here’s an example.

    > (rex-find-matches (rex-char-range #\a #\z) "blah")
    '("b" "l" "a" "h")
    > (rex-find-matches (rex-concat (rex-start-of-string)
                                    (rex-char-range #\a #\z))
                    "blah")
    '("b")
    > (rex-find-matches (rex-concat (rex-char-range #\a #\z)
                                    (rex-end-of-string))
                    "blah")
    '("h")

Do you realize how much reading you gave us for today?

Too much! But at least there’s no reading for tomorrow.

The longest string in a list

One solution.

(define longest-string
  (lambda (lst)
    (cond
      [(null? (cdr lst))
       (car lst)]
      [(> (string-length (car lst))
          (string-length (longest-string (cdr lst))))
       (car lst)]
      [else
       (longest-string (cdr lst))])))

What do you notice?

There are two calls to (longest-string (cdr lst)).

What is the effect?

  • Perhaps they’ll give different values. (We hope that identical procedure calls will give identical values, but they won’t always.)
    • Referential transparency
  • Will we get runaway recursion?
    • Probably not, because we are shrinking the list down to null.
  • Doing the whole giant reursive seems dangerous / lots of extra work. .

Side conversation

;;; (num->words nums) -> listof string?
;;;   nums : listof natural?
;;; Make a list of words, each of whose length is the corresponding
;;; value in nums.
(define nums->words
  (lambda (nums)
    (map (section make-string <> #\a)
         nums)))

What is (num->words ‘(1 4 2))

  • Not sure
  • Put the digit in front of the number
  • Make a list, the first of which is a string of one a, the second is four a’s, and the third is two a’s.
> (nums->words '(1 4 2))
'("a" "aaaa" "aa")

We’ve defined increasing as follows.

;;; increasing : listof string?
;;; A list of strings in increasing length order
(define increasing
  (nums->words (range 0 22)))

What value do you expect increasing to have?

  • Empty string then one then two then … up to twenty-one or twenty-tow.
  • Is range inclusive or exclusive.
> increasing
'("" "a" "aa" ... "aaaaaaaaaaaaaaaaaaaaa")

> (time (longest-string increasing))
cpu time: 204 real time: 205 gc time: 0
"aaaaaaaaaaaaaaaaaaaaa"
> (string-length "aaaaaaaaaaaaaaaaaaaaa")

What is decreasing?

  • The same list, except in the reverse order.

And when we try to do it …

  • Output? twenty-one a’s
  • Time?
    • More: 300 milliseconds. More work to go through? [+2]
    • Faster: It doesn’t have to do the second recursive call. So maybe 100 milliseconds.
    • More: 400 milliseconds.
    • About the same. It’s the same length.
> (time (longest-string decreasing))
cpu time: 0 real time: 1 gc time: 0
"aaaaaaaaaaaaaaaaaaaaa"

Whooa! That’s a lot faster. Why?

  • The computer could have cached the prior work, making things faster.
    • Good guess, but that does not appear to be it.

  • If we reach the else branch every time, we’re doubling. But we’re not doubling once, we’re doubling at every time through the recursive calls. 2^21 times the work.

      (longest-string *list-of-length-21*)
  2 * (longest-string *list-of-length-20*)
  2 * 2 * (longest-string *list-of-length-19*)
  2 * 2 * 2 * (longest-string *list-of-length-18*)

If the hypohtesis is true, and I increase the range by one, the time shoudl be twice as much.

> (let ([lst (nums->words (range 0 23))])
    (time (longest-string lst)))
cpu time: 430 real time: 433 gc time: 0
"aaaaaaaaaaaaaaaaaaaaaa"
> (let ([lst (nums->words (range 0 24))])
    (time (longest-string lst)))
cpu time: 868 real time: 873 gc time: 0
"aaaaaaaaaaaaaaaaaaaaaaa"
> (let ([lst (nums->words (range 0 25))])
    (time (longest-string lst)))
cpu time: 1689 real time: 1701 gc time: 0
"aaaaaaaaaaaaaaaaaaaaaaaa"

How can we fix it? How can we make longest-string better?

  • Use an accumulator! Which might allow us to use tail recursion.
  • Munge the input!
  • Use a let statement to avoid the two recursive calls. [+2]
(define longest-string
  (lambda (lst)
    (let ([longest-in-cdr (longest-string (cdr lst))])
      (cond
        [(null? (cdr lst))
         (car lst)]
        [(> (string-length (car lst))
            (string-length longest-in-cdr))
         (car lst)]
        [else
         longest-in-cdr]))))
  • Whoops! We’re calling cdr before we make sure that the list is not null.
  • It does help with the cost (if it worked) in that we only do a recursive call once, rather than twice. (Use do the recursive call and then tuse it.)
(define longest-string
  (lambda (lst)
    (cond
      [(null? (cdr lst))
       (car lst)]
      [else
       (let ([longest-in-cdr (longest-string (cdr lst))])
         (cond
           [(> (string-length (car lst))
               (string-length longest-in-cdr))
            (car lst)]
           [else
            longest-in-cdr]))])))
  • The nested cond is ugly and confusing. Sam should write clearer code.
  • We need unit tests!
> (time (longest-string increasing))
cpu time: 0 real time: 0 gc time: 0
"aaaaaaaaaaaaaaaaaaaaaa"
> (time (longest-string decreasing))
cpu time: 0 real time: 0 gc time: 0
"aaaaaaaaaaaaaaaaaaaaaa"
> (let ([lst (nums->words (range 0 240))])
    (time (longest-string lst)))
cpu time: 1 real time: 0 gc time: 0
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

The morals of the story.

  • When you have repeated code, use a let (or other technique) to avoid it.
  • Do this especially with repeated identical recursive calls. Otherwise your code runs really slowly.

And make your code cleaner.

(define longest-string
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst)
        (let ([longest-in-cdr (longest-string (cdr lst))])
          (if (> (string-length (car lst))
                 (string-length longest-in-cdr))
              (car lst)
              longest-in-cdr)))))
  • Each longest-in-cdr is just a look up into a table of the name/value pairs. [Mental Model 2]
  • Or … we evaluate (Longest-string (cdr lst)) which gives some string “aaaaaaaaaaaa”, which we then plug in for both cases of longest-in-cdr. [Mental Model 1]
    • This is the better way to think about it: Compute it, substitute it, discard the let.
  • In either case, we don’t have a recursive call, we just have a string. And strings don’t require further evaluation.

Writing list-length

How do we write list-length?

;;; (list-length lst) -> integer?
;;;   lst : list?
;;; Determines the number of elements in lst
(define list-length
  (lambda (lst)
    (if (null? lst) ; Check for base case
        0           ; Return a base value
        (+ 1 (list-length (cdr lst))))))

(test-equal? "um ... a normal list of integers"
             (list-length '(1 2 3 4 5))
             5)
(test-equal? "empty list"
             (list-length null)
             0)
(test-equal? "integers in reverse order"
             (list-length '(6 5 4 3 2 1))
             6)
(test-equal? "a really long list"
             (list-length (make-list 10000 1))
             10000)

Let’s figure out how to deal with the recursive call. Let’s suppose it works for the smaller list

  • Looking ahead: Should we check for the singleton list?
  • Suppose we know that (length (list 2 3 4 5)) is 4, what is (length (list 1 2 3 4 5))? 5
  • More generally, suppose we know that (length (cdr lst)) is 17. What is (length lst)? 18
  • Even more generally, suppose we know that (length (cdr lst)) is n. What is (length lst)? (+ n 1)
  • Because cdr throws away one value

A tip on tail recursion

Normal (direct)

(define fun
  (lambda (params)
    (if (base-case-test? params)
        base-case
        (combine params (fun (simplify params))))))

Convert to tail recursive

(define fun-helper
  (lambda (params so-far)
    (if (base-case-test? params)
        so-far
        (fun-helper (simplify params) (combine params so-far)))))

(define fun
  (lambda (params)
    (fun-helper params base-case)))

Rewriting list-length

Let’s try again, this time making list-length tail-recursive.

(define list-length-helper
  (lambda (lst so-far)
    (if (null? lst)
        so-far
        (list-length-helper (cdr lst) (+ 1 so-far)))))

(define list-length
  (lambda (lst)
    (list-length-helper lst 0)))

> (time (list-length-old ben))
cpu time: 8187 real time: 11445 gc time: 5201
1000000
> (time (list-length ben))
cpu time: 28 real time: 29 gc time: 0
1000000

Checking for a one-element list

Option one: DON’T USE THIS

(define one-element-list?
  (lambda (lst)
    (= (length lst) 1)))

Option two:

(define one-element-list?
  (lambda (lst)
    (null? (cdr lst))))

Option three

(define one-element-list?
  (o null? cdr))

Option four

(define one-element-list?
  (lambda (lst)
    (and (not (null? lst))
         (null? (cdr lst)))))

Writing reverse

Tail recursion will be our first approach.

;;; (rev lst) -> list?
;;;   lst : list?
;;; Reverse lst.
(define rev
  (lambda (lst)
    (rev-helper lst null)))

(define rev-helper
  (lambda (lst so-far)
    (if (null? lst)
        so-far
        (rev-helper (cdr lst) (cons (car lst) so-far)))))

(test-equal? "base case"
             (rev '())
             '())
(test-equal? "That standard list of integers"
             (rev '(1 2 3))
             '(3 2 1))

(test-equal? "An excessive case"
             (rev (range 1 10000))
             (range 9999 0 -1))

Writing powers-of-two

Detour away from tail recursion, but still use a helper.

;;; (powers-of-two n) -> listof integer?
;;;   n : natural?
;;; Make a list of all integral powers of 2 strictly less than n,
;;; starting with 1
(define powers-of-two
  (lambda (n)
    (powers-of-two-helper n 1)))

;;; (powers-of-two-helper n k) -> listof integer?
;;;   n : natural?
;;;   k : natural?
;;; Make a list of all integral powers of 2 strictly less than n,
;;; starting with k.
(define powers-of-two-helper
  (lambda (n k)
    (if (>= k n)
        null
        (cons k (powers-of-two-helper n (* k 2))))))

What do you expect for (powers-of-two-helper 128 128)?

(test-equal? "k equals n"
             (powers-of-two-helper 128 128)
             '())

(test-equal? "k exceeds n"
             (powers-of-two-helper 60 64)
             '())

Writing range

;;; (my-range start finish) -> listof integer?
;;;   start : integer?
;;;   finish : integer?
;;; Compute the list (start start+1 start+2 ... finish-1).
(define my-range
  (lambda (start finish)
    (if (>= start finish)
        '()
        (cons start (my-range (+ start 1) finish)))))

(test-equal? "empty range at 0"
             (my-range 0 0)
             '())
(test-equal? "empty range at 5"
             (my-range 5 5)
             '())
(test-equal? "the normal list"
             (my-range 1 6)
             '(1 2 3 4 5))

We’ve written it “counting up”. We could also use tail recursion to count down.

Writing append

Writing list-ref

Writing fibonacci

Copyright © Charlie Curtsinger, Sarah Dahlby Albright, Janet Davis, Nicole Eikmeier, Fahmida Hamid, Titus Klinge, Peter-Michael Osera, Samuel A. Rebelsky, and Jerod Weinman. Selected materials are copyright by John David Stone or Henry Walker and are used with permission.

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.