Overview

• Quick quiz overview.
• You ask questions, I attempt to answer.
• We talk more about the forthcoming quiz.

Quiz Topics

• Higher-order procedures
• Analyzing procedures
• assoc
• Searching

Your Questions

Can we start with an overview of higher-order procedures?

Basic idea: A procedure can be a parameter to another procedure or a return value from another procedure. ("Procedures are first-class values in Scheme")

We've used them as parameters to existing procedures for at least half the semester. (map square (iota 10)) - square is a parameter to map.

We've used them as return values for at least half the semester. (l-s + 2) - returns a procedure.

We've moved forward to how we write things like map and l-s.

Taking a procedure as a parameter.

    ; Given a procedure and a list, apply the procedure to each
    ; element of the list and build a list of the results.
    (define simple-map
      (lambda (proc lst)
        ; If there's nothing in the list, there's no work to do
        (if (null? lst)
            null
            ; Otherwise, apply the procedure to the first element
            ; of the list, apply the procedure to each remaining
            ; element, and put it back together
            (cons _____ (simple-map proc (cdr lst))))))

We want to insert "apply the procedure to the car of the list". That's (proc (car lst)). The strange part is that we're using a variable as a procedure. But Scheme allows it.

    (define simple-map
      (lambda (proc lst)
        ; If there's nothing in the list, there's no work to do
        (if (null? lst)
            null
            ; Otherwise, apply the procedure to the first element
            ; of the list, apply the procedure to each remaining
            ; element, and put it back together
            (cons (proc (car lst)) (simple-map proc (cdr lst))))))

Key idea: We can apply a procedure that we get as a parameter the same way we apply any other procedure.

Next issue: How do we write procedures that return other procedures as results.

Assume that we don't have left-section (l-s) or right-section

    ;;; Procedure:
    ;;;   multiplier
    ;;; Parameters:
    ;;;   n, a number
    ;;; Purpose:
    ;;;   Build a procedure that multiplies its parameter by n.
    ;;; Produces:
    ;;;   multiply-by-n, a unary procedure
    (define multiplier
      (lambda (n)

Detour: How would you write a procedure, add2, that adds 2 to the value it takes as input

    (define add2 (lambda (x) (+ 2 x)))

When you need "a procedure", you almost always write a lambda.

    (define multiplier
      (lambda (n)
        (lambda (x)
          (* n x))))

    > (multiplier 5)
    #<procedure>
    > (define m5 (multiplier 5))
    > (m5 2)
    10
    > (m5 23.1)
    115.5
    > (m5 2+3i)
    10+15i

Big idea: When you return a procedure, you often create that procedure with another lambda.

Troublesome issue: "Why are there two lambda?"

Smart students suggest that I write the following, which may be clearer

    (define multiplier
      (lambda (n)
        (let ([multiply-by-n (lambda (x) (* n x))])
          multiply-by-n)))

What have students seemed to be struggling with recently (or in past semesters when dealing with these topics)?

Determining that code they write is inefficient. (Two patterns of inefficiency on the lab, one in subsequent discussions.)

One inefficiency: Building lists with repeated calls to append.

A similar inefficiency: Getting each element of a list using list-ref

A related inefficiency: Calling length for each of a list.

Another inefficiency: Calling the same procedure multiple times on the same inputs (which can lead to really slow code).

What else?

Figuring out all of the parameters to binary-search and the general binary search process.

I won't ask you to read or implement binary search on the quiz.

How do we tell when we're writing inefficient code?

Use the tricks I showed earlier; either add a counter, or print something each time a procedure or kernel is called. Try a variety of inputs.

Generalization of a skill we've been working on: We used to try inputs to make sure it worked correctly (and we still do); now we also think about different inputs to make sure that it always works "efficiently".

Don't make an identical procedure call twice! (Use let)

About the Quiz

Likely types of quiz questions:

• Interpret or document this code.
• Finish writing this code that is supposed to accomplish this task.
• Find the bugs in this code that is supposed to accomplish this task.

Consider the following code

    (define w
      (lambda (x y)
        (let ([result (lambda (z) (x y z))])
          result)))

• What type is x in this procedure? A procedure of two parameters
• What type does w return? - A procedure of one parameter.

• What does the returned procedure do? - Applies x to two values, y and z. (Given z, applies x to y and z.)

  (define w
    (lambda (f v1)
      (let ([result (lambda (v2) (f v1 v2))])
        result)))
  

• What commonly used function does w implement? l-s

• Your classmates all owe you big time for convincing me that this shouldn't be on the quiz tomorrow.

_Consider the following table. Write an expression to find an event on 2015-04-25."

    (define events
      (list (list "2015-04-21" "Convo")
            (list "2015-04-14" "Convo")
            (list "2014-04-28" "PBK Convo")
            (list "2015-04-25" "Titular Head")
            (list "2015-04-23" "Town Hall")
            (list "2015-05-10" "Convo")
            (list "2015-04-23" "Pub Night")))

(assoc "2015-04-25" events)

Write a procedure that will find all of the convocations ("Convo" not "PBK Convo")

    (define find-all-convos
      (lambda (lst)
        (cond
          [(null? lst) null]
          [(equal? (cadar lst) "Convo")
           (cons (car lst) (find-all-convos (cdr lst)))]
          [else
           (find-all-convos (cdr lst))])))

What does the following expression return?

    > (reverse (assoc "Convo" (map reverse events)))
    '("2015-04-10" "Convo")

What's wrong with the following procedure?

    (define max-value
      (lambda (values)
        ; If there's only one value, it's the largest
        (if (= (length values) 1)
            (car values)
            ; Otherwise, we need to compare the car to the
            ; largest remaining value and take the larger of the two
            (if (> (car values) (max-value (cdr values)))
                (car values)
                (max-value (cdr values))))))

We shouldn't use (= (length values) 1). length is expensive. Use (null? (cdr lst)) isntead.

Nested if statements are pretty ugly.

Two identical recursive calls to (max-value (cdr values)). Use a let.