CSC151.01 2015S, Review Session Week 12: Lots of Stuff
======================================================

_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`._