EBoard 22: Higher-order recursion

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

Approximate overview

• General administrative stuff + More [~20 min]
• Q&A [~10 min]
• Quiz [~10 min]
• Lab [~50 min]

Administrative stuff

Be kind to your graders

• Good documentation. The explanation should be what, not how, and should be short. Correct types.
  • This prepares them to read.
• Well-formatted code.
• Refactor when possible. Less code is easier to read.

Notes and news

• I think I’ve scheduled everyone who asked for an appointment. If not, let me know.
  • I do have a few Thursday afternoon slots left.
  • If you are 12–14 hours away, I can possibly schedule an evening (for me) / morning (for you) meeting.

Tutoring reminders

• Please use our tutors! They like to work.
• Evening tutoring will be available
  • 8-10 p.m. Sundays through Thursdays
  • 3-5 p.m. Sundays
  • In the “Drop in tutoring” channel on the CS team.
  • Sam will generally not be available during these times.
• Individual tutors are temporarily unavailable. We’re recruiting more.
  • Don’t let this stop you from requesting one.
  • If you’re willing to share your individual tutor (as in, to do pair tutoring), let me know.

Upcoming activities

Attend (or watch recording) and send a one-paragraph reflection.

• None currently scheduled.

Upcoming work

• Mini-project 4 (due Wednesday (TOMORROW), December 2 at 10:30 p.m. CST)
• Redo of Mini-project 3 (due Sunday the 6th at 10:30 p.m. CST)
  • Returned today
• Reading for Wednesday
  • Randomness and simulation
  • Yes, we’re moving on from recursion
• Quiz today: Tail recursion
• Quiz Wednesday: Hop recursion

Some longer examples

The evil Fibonacci

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

Let’s list some Fibonacci numbers

0 1 1 2 3 5 8 13 21 34 55 89

Starting point

;;; (fib n) -> non-negative-integer?
;;;   n : non-negative-integer?
;;; Computes the nth Fibonacci number
(define fib
  (lambda (n)
    undefined))

;;; (fibber n) -> listof non-negative-integer?
;;;   n : non-negative-integer?
;;; Computes a list of the first n Fibonacci numbers in
;;; reverse order.
(define fibber
  (lambda (n)
    (cond
      [(= n 0)
       '()]
      [(= n 1)
       '(0)]
      [(= n 2)
       '(1 0)]
      [else
       ; "I'm sorry, there's a lot of background noise"
       ; The magic recursion fairy says: "Use a recursive
       ; call, it just works out."
       (let ([remaining-fibs (fibber (- n 1))])
         ; Suppose n is 5
         ; What will `remaining-fibs` be?
         ;  (fibber 4) is '(2 1 1 0)
         ; How do we build (fibber 5) from that list
         ; (cons ... remaining-fibs)
         ; Without using fib
         ; We can get the next Fibonacci number by adding
         ; the first two numbers in '(2 1 1 0)
         ; (+ (list-ref remaining-fibs 0) (list-ref remaining-fibs 1))
         ; (+ 2 1)
         ; 3
         (cons (+ (list-ref remaining-fibs 0)
                  (list-ref remaining-fibs 1))
               remaining-fibs))])))```

Predicting times for `(car (fibber 36))`

* Between 100 and 1000, probably on the lower end
* "Really fast"
* Closer to 1000, since we have to do the car after computing the 35th
  Fibonacci number
* Hmmm ... It took about 0 miliseconds

What will happen if Sam types `(time (car (fibber 100)))`

* It will take longer, but at a smaller rate.  It will be manageable. [+2]
* DrRacket will crash.

What will happen if Sam types `(time (fib 100))`?

* DrRacket will crash, or at least take a long time.
* A lot longer.

What do we find?

(time (car (fibber 100))) cpu time: 0 real time: 1 gc time: 0 218922995834555169026 (time (car (fibber 1000))) cpu time: 17 real time: 17 gc time: 16 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626 (time (fib 40)) cpu time: 11945 real time: 12286 gc time: 16 102334155 ```

Are there data that should tell us?

• No. This is intuition

Why is fibber so much faster than fib?

• For fib, each time you have a recursive case, you almost double the amount of time, because you’re calling it twice.
• For fibber, you’re only doing one recursive call.
• Doubling every time feels bad.

Suggestions

• Don’t do multiple recursive calls if you can avoid it.
• We’re doing something like tail recursion: Building up a value as we go and using it.
• Trust the magic recursion fairy
  • Generalized process: I’m going to assume the recursive call works (I’m going to assume that I’ve correctly written the procedure for all “smaller” inputs.) What can I do next?
  • Specific process: Let’s take an example, assume the recussive call works, and see what we can do.
  • “Trust the process”

The brain-twisting map-filter

Consider the following procedure

;;; (square-nums lst) -> list of numbers
;;;   lst : list?
;;; Return the squares of all the numbers in a given list
(define square-nums
  (lambda (lst)
    (map sqr (filter number? lst))))

Implementation:

• First filter the list for numbers
• Then square all the numbers

(define square-nums
  (lambda (lst)
    (map sqr (filter-numbers lst))))
; How do we write a
procedure that filters a list for numbers
; without using lambda.  We can use section!
(define filter-numbers
  (section filter number? <>))

(define square-nums
  (lambda (lst)
    (square-all (filter-numbers lst))))

; Square all elements in a list of numbers
(define square-all
  (lambda (nums)
    (map sqr nums)))
(define square-all
  (section map sqr <>))

; Can we get rid of the lambda in `square-nums`?
;   Possibly section
;   Possibly composition
(define square-nums
  (o square-all filter-numbers))

; Can we do that without helpers?
(define square-nums
  (o (section map sqr <>) 
     (section filter number? <>)))

Doesn’t that hurt your head?

Big idea: We can often think in terms of functions without using lambda, as long as we’ve mastered o and section.

• Don’t go overboard with this!

What’s a good rule of thumb for using section and compose?

Is this related to the reading for last night?

• Yes, but primarily in that we are talking about procedures as primary values.

Let’s talk about higher-order recursion

Consider filter.

;;; (my-filter pred? lst) -> list
;;;   pred? : procedure?
;;;   lst : list?
;;; Selects all of the elements of lst for which pred? holds.
;;; Pre: pred? must be applicable to all elements of hte list.
(define my-filter
  (lambda (pred? lst)
    (match lst
      [(list)
       null]
      [(cons head tail)
       (if (pred? head)
           (cons head (my-filter pred? tail))
           (my-filter pred? tail))])))

Big conclusions

• Trust the magic recursion fairy!
• This looks a lot like the code for remove; sometimes you can use patterns from simpler procedures for writing hops.

Smaller notes

• Embrace the Zen of Booleans
• ’(), null, and (list) all build the empty list.
• ’() and (list) are the patterns for the empty list.

(define my-filter
  (lambda (pred? lst)
    (cond
      [(null? lst)
       null]
      [(pred? (car lst))
       (cons (car lst) (my-filter pred? (cdr lst)))]
      [else
       (my-filter pred? tail)])))

Can we use tail recursion?

Yes, but not today.

Quiz

NOPE!

Lab

NOPE!

Tomorrow

RANDOM!

We are skipping today’s lab. You may want to practice writing some of the higher-order procedures.

Some dialogs about MP4

Dialog the first

Sam, I’m stuck on the '(join P1 P2) pattern. Can P1 be anything other than x or 1?

Yes, it should work when P1 is any pattern.

Wow, I have to write a lot of extra code to check if P1 is a variable or P1 is an integer or P1 is a string or P1 is a join or P1 is a seq.

No, you don’t. You shouldn’t.

What else can I do?

What is your goal for P1?

I’d like to make sure that P1 has to match the car of value. That means I check if P1 is a symbol, in which case it matches. If it’s not a symbol, I check if it’s 1, in which case I check if the car of the value is 1. I realize I need to generalize that.

Step back a second. Look at what you want to do, not how?

I’d like to make sure that P1 has to match the car of value.

Do you have a procedure that does that?

I was just describing that procedure to you.

When you finish MP4, will you have a procedure that matches P1 to a value. (What procedures are you writing in MP4?)

[Sounds of brain burning]. Oh!

Trust the magic recursion fairy. This assignment is mostly about thinking recursively.

Dialog the second

I’m having trouble with join. I think I have things working right but I can’t get (match? '(join 1 xs) (list 1)) to work.

Okay, what are you doing?

I’m matching the cadr of the pattern with the car of the value. Then I’m matching the cddr of the pattern with the cdr of the value.

Let’s check. What’s the cadr of '(join 1 xs)

1

What’s the car of the value?

1

Do they match?

Yes, of course.

Did you check it?

Um.

Let’s check it: (match? 1 1).

Yes!

What’s the cddr of '(join 1 xs)

The symbol 'xs

What’s the cdr of value (list 1)

The empty list, '()

Do those match?

Yes.

Are you sure?

Let me check. (match? xs '()). Yes.

Are you sure that the cddr of '(join 1 xs) is xs?

Yes.

Are you sure?

Yes.

Did you check?

Oh. I guess I should check. Oh, I got '(xs). Is that the same as xs?

No!

How do I get the xs?

Liam asked that on Monday.

Oh, that’s (list-ref pattern 2).

Right.

Dialog the third

I’m not sure what to do with seq.

Did you read the FAQ.

Of course. It said “Write a helper for lists of patterns and lists of values”.

Great. So what help do you need?

I need help getting started.

What’s your documentation?

;;; (match-lists? patterns values) -> boolean
;;; ...

Great! I’m so glad documenting. What about your tests?

I’m putting that off.

Can you at least think of a few?

Sure.

(check-true (match-lists? '(a) '(1)) "test/1")
(check-true (match-lists? '(a (join 1 xs)) '(1 (1))) "test/2")
(check-true (match-lists? '() '()) "test/3")

What’s your high-level design?

Um. Can we just write some code.

[Sigh.] Ok.

Let’s start with a template.

(define match-lists?
  (lambda (patterns values)
    ...))

What’s your base case?

Um. Probably null.

(cond [um

[Groan]

More seriously

(define match-lists?
  (lambda (patterns values)
    (cond
      ; If there are no patterns left.  
      [(null? patterns)

What should we do?

Stop and return true, since there are no patterns like.

(define match-lists?
  (lambda (patterns values)
    (cond
      ; If there are no patterns left.  
      [(null? patterns)
       #t]

What if there still values left?

patterns and values had the same length before I called match-lists?. Don’t you read your own assignments Sam? You told us to do that.

Ok.

What next?

I need to match the car of patterns to the car of values.

Great. How?

[Dialog 1.]

Great. You’ve figured out how to match the car. What next?

“Magic recursion fairy”

“Magic recursion dragon”

“Magic recursion loud doctor”

“Magic recursion mentor”

“Magic recursion dragon fractal”

“Magic recursion brain explosion”

Q&A

Mini-Project 3 Redo

Mini-Project 4

I think you got the pattern for the empty list wrong.

You are correct. Here’s a corrected one.

;;; (empty-list-pattern? pattern) -> boolean
;;;   pattern : a pattern (see MP4 assignment)
;;; Determine if pattern represents the empty list.
(define empty-list-pattern? 
  (lambda (pattern)
    (and (list? pattern) 
         (not (null? pattern)) 
         (null? (cdr pattern))
         (equal? (car pattern) 'seq))))

The dialogs confused me. Can we talk?

Questions on Teams.

SoLA general questions

Other

Can we look at fold?

Not today. Maybe tomorrow.

Are you always this snarky?

Often. Haven’t you been in my class?