Naming Values with Local Bindings

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Evaluating let
  • Exercise 2: Nesting Lets
  • Exercise 3: Simplifying Nested Lets
  • Exercise 4: Access to Local Procedures
  • Exercise 5: Finding the Longest Element List
  • Exercise 6: Alternate Techniques
  • Exercise 7: Another Alternative
  • Exercise 8: Checking Preconditions
• For Those With Extra Time
• Notes

Exercises

Exercise 0: Preparation

Start DrScheme.

Exercise 1: Evaluating let

What are the values of the following let-expressions? You may use DrScheme to help you answer these questions, but be sure you can explain how it arrived at its answers.

a.

(let ((tone "fa")
      (call-me "al"))
  (list call-me tone "l" tone))

b.

;; Solutions to the quadratic equation x^2 - 5x + 4:
(let ((discriminant (- (* -5 -5) (* 4 1 4))))
  (list (/ (+ (- -5) (sqrt discriminant)) (* 2 1))
        (/ (- (- -5) (sqrt discriminant)) (* 2 1))))

c.

(let ((total (+ 8 3 4 2 7)))
  (let ((mean (/ total 5)))
    (* mean mean)))

Exercise 2: Nesting Lets

Write a nested let-expression that binds a total of five names, alpha, beta, gamma, delta, and epsilon, with alpha bound to 9387 and each subsequent name bound to a value twice as large as the one before it -- beta should be twice as large as alpha, gamma twice as large as beta, and so on. The body of the innermost let-expression should then compute the sum of the values of the five names.

Exercise 3: Simplifying Nested Lets

Write a let*-expression equivalent to the let-expression in the previous exercise.

Exercise 4: Access to Local Procedures

Consider the following procedure that squares all the values in a list.

;;; Procedure:
;;;   square-values
;;; Parameters:
;;;   lst, a list of numbers of the form (num_1 num_2 ... num_n)
;;; Purpose:
;;;   Squares all the values in lst.
;;; Produces:
;;;   list-of-squares, a list of numbers
;;; Preconditions:
;;;   [Standard]
;;; Postconditions:
;;;   list-of-squares has the form (square_1 square_2 ... square_n)
;;;   For all i, square_i is the square of num_i (that is num_i * num_i).
(define square-values
  (lambda (lst)
    (let ((square (lambda (val) (* val val))))
      (if (null? lst)
          null
          (cons (square (car lst)) (square-values (cdr lst)))))))

a. Verify that square-values works correctly.

b. Try to execute square outside of square-values. Explain what happens.

Exercise 5: Finding the Longest Element List

Here is a procedure that takes a non-empty list of lists as an argument and returns the longest list in the list (or one of the longest lists, if there is a tie).

;;; Procedure:
;;;   longest-list-in-list
;;; Parameters:
;;;   los, a list of lists
;;; Purpose:
;;;   Finds one of the longest lists in los.
;;; Produces:
;;;   longest, a list
;;; Preconditions:
;;;   los is a nonempty list.
;;;   every element of los is a list.
;;; Postconditions:
;;;   Does not affect los.
;;;   Returns an element of los.
;;;   No element of los is longer than longest.
(define longest-list-in-list
  (lambda (los)
    ; If there is only one list, that list must be the longest.
    (if (null? (cdr los))
        (car los)
        ; Otherwise, take the longer of the first list and the
        ; longest remaining list.
        (longer-list (car los) (longest-list-in-list (cdr los))))))

This definition of the longest-list-in-list procedure includes a call to the longer-list procedure, which returns the longer of two given lists:

;;; Procedure:
;;;   longer-list
;;; Parameters:
;;;   left, a list
;;;   right, a list
;;; Purpose:
;;;   Find the longer of left and right.  
;;; Produces:
;;;   longer, a list
;;; Preconditions:
;;;   Both left and right are lists.
;;; Postconditions:
;;;   longer is a list.
;;;   longer is either equal to left or to right.
;;;   longer is at least as long as left.
;;;   longer is at least as long as right.
(define longer-list
  (lambda (left right)
    (if (<= (length right) (length left))
        left
        right)))

Revise the definition of longest-list-in-list so that the name longer-list is bound to the procedure that it denotes only locally, in a let-expression.

Exercise 6: Alternate Techniques

Note that there are at least two possible ways to do the previous exercise: The definiens of longest--list-in-list can be a lambda-expression with a let-expression as its body, or it can be a let-expression with a lambda-expression as its body. That is, it can take the form

(define longest-list-in-list
  (let (...)
    (lambda (los)
      ...)))

or the form

(define longest-list-in-list
  (lambda (los)
    (let (...)
      ...)))

a. Define longest-list-in-list in whichever way that you did not define it for the previous exercise.

b. Does the order of nesting affect what happens when the procedure is invoked? If so, which arrangement is better? Why?

c. Make a similar change to square-values.

Exercise 7: Another Alternative

The two definitions you came up with in the previous exercises are not the only alternatives you have in placing the let. Since longer-list is only needed in the recursive case, you can place the let there.

(define longest-list-in-list
  (lambda (los)
    ; If there is only one list, that list must be the longest.
    (if (null? (cdr los))
        (car los)
        ; Otherwise, take the longer of the first list and the
        ; longest remaining list.
        (let ((longer-list
                (lambda (left right)
                  (if (<= (length right) (length left))
                      left
                      right))))
          (longer-list (car los) (longest-list -in-list (cdr los))))))

Including the original definition, you've now seen or written four variants of longest-list-in-list. Which do you prefer? Why?

Exercise 8: Checking Preconditions

Extend your favorite version of longest-list-in-list so that it verifies its preconditions (i.e., that los only contains lists and that los is nonempty). If the preconditions are not met, your procedure should return #f.

It is perfectly acceptable for you to check each list element in turn to determine whether or not it is a list, rather than to check them all at once, in advance.

For Those With Extra Time

Using DrScheme's (time exp) operation, determine which of the four versions of longest-list-in-list is indeed the fastest. You should try a variety of lengths for the outer list. The inner lists can be mostly 0- or 1-element lists..

Notes