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 (and inefficiencies)
• assoc
• Searching (no, you don't need to understand all the details of the implementation of binary search)

Your Questions

Can you explain how assoc works?

It's going to look through a list, so we'll use our normal pattern of list recursion.

    (define assoc
      (lambda (val lst)
        (if (null? lst)
            __________
            (__________ (assoc val (cdr lst))))))

Base case. What should we get if the list is empty? #f

        (if (null? lst)
            #f
            (__________ (assoc val (cdr lst))))))

I probably need to look at the car of the list

        (if (null? lst)
            #f
            ; if the car of the list matches
            (if (_____ (car lst))
               (car lst)
               (assoc val (cdr lst))))

The car of the list is a list. We want to know if its first element matches

            ; if the car of the list matches
            (if (equal? val (car (car lst)))

Cleaning it up

    (define my-assoc
      (lambda (val lst)
        (cond
          [(null? lst)
           #f]
          [(equal? val (caar lst))
           (car lst)]
          [else
           (my-assoc val (cdr lst))])))


    > (my-assoc 5 (list (list 3 "a") 
                        (list 4 "b") 
                        (list 1 "c") 
                        (list 5 "a") 
                        (list 2 "b") 
                        (list 5 "c")))
    '(5 "a")

Assoc returns only the first value that matches. How do we get a list of *all* the matching values?

    (define assoc-all
      (lambda (val lst)
        (cond
          [(null? lst)
           null]
          [(equal? val (caar lst))
           (cons (car lst) (assoc-all val (cdr lst))))]
          [else
           (assoc-all val (cdr lst))])))

Can you explain more about the relationship between lists and vectors?

Both store collections of values.

Vectors are "indexed", they are built in such a way that (vector-ref vec i), it's fast (independent of i)

In Scheme, Vectors are fixed-size.

Lists are dynamic, you can always cons another value on to the front.

Vectors are mutable: You can change what's in a vector. Lists are immutable.

How do vectors work?

See whiteboard.

The element at a particular index is (start + index*cellsize)

How can you tell just by looking at a procedure if it's likely to be inefficient?

You can model a formula for how it grows.

Excellent: When you double the input size, the running time doesn't change.

Really good: When you double the input size, the running time goes up by a constant amount. (E.g., binary search)

Acceptable: When you double the input size, the running time doubles. (Typical list model)

Less acceptable, but sometimes necessary: When you double the input size, the running time quadruples (Running time is a function like size*size)

Unacceptable: 2^x: If the input goes up by 1, the running time doubles.

Some rules of thumb

Don't use append, length, or list-ref in a recursive procedure.

If you have two identical recursive calls, use a let.

If you have multiple identical expressions, use a 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

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

• What type is x? Procedure of two parameters
• What type is result? / What type does w return? Procedure
• w is something that takes a procedure as input and returns a procedure

• w is a procedure we use a lot. What procedure is it? l-s

  (define l-s
    (lambda (proc left)
      (let [result (lambda (right) (proc left right))]
        result)))
  

Consider the following table

    (define students
      (list (list "C" "Z")
            (list "S" "R")
            (list "V" "V")
            (list "D" "C")
            (list "K" "H")
            (list "L" "W")
            (list "A" "C")))

• What is the value of (reverse (assoc "C" (map reverse students)))?

• Answers

  • '("Z" "C") - proposed

  • '("D" "C") - Actual. Why?

    (map reverse students)

    (map reverse students) '(("Z" "C") ("R" "S") ("V" "V") ("C" "D") ("H" "K") ("W" "L") ("C" "A"))

• Note that this strategy is efficient in programmer time and inefficient in computer time. If I regularly searched using the key as the last element of an entry, I'd write the following.

  (define assoc-by-last
    (lambda (val lst)
      (cond
        [(null? lst)
         #f]
        [(equal? val (last lst))
         (car lst)]
        [else
         (assoc-by-last val (cdr lst))])))
  

Fill in the details to implement assoc-all that builds a list of all entries with a car of val

    (define assoc-all
      (lambda (val lst)
        (cond
          [(null? lst)
           ___]
          [(equal? val (caar lst))
           ___]
          [else
           ___])))

Fill in the details for a more general assoc?

    (define assoc-general
      (lambda (val lst get-key)
        (cond
          [(null? lst)
           _____]
          [______
           (car lst)]
          [else
           (assoc-general val (cdr lst) get-key)])))

    (define assoc-general
      (lambda (val lst get-key)
        (cond
          [(null? lst)
           #f]
          [(equal? val (get-key (car lst)))
           (car lst)]
          [else
           (assoc-general val (cdr lst) get-key)])))