CSC 324 Tutorial Week 3
=======================

Procedures taking and producing procedures
==========================================
Question:

  Recall from lecture (something like):

    ; Return the slope of the secant of f from x1 to x2
    (define secant-slope
      (lambda (f x1 x2) (/ (- (f x2) (f x1)) (- x2 x1))))

  Write a procedure named approximate-derivative-at that takes a function f
   and number x, and returns the approximate derivative  of f at x by
   returning the secant slope from x to x + 0.01 of f.

Answer:

  (define approximate-derivative-at
    (lambda (f x) (secant-slope f x (+ x 0.01))))

Question:

  We could call approximate-derivative-at like:

    (approximate-derivative-at sin 0) => 0.9999833334166665

  Define approximate-derivative so that we can write:

    ((approximate-derivative sin) 0) => 0.9999833334166665
    ((approximate-derivative (lambda (x) (* x x))) 1) => 2.009999999999999
    (define almost-cos (approximate-derivative sin))

Answer:

  (define approximate-derivative
    (lambda (f)
      (lambda (x) (approximate-derivative-at f x))))

Question:

  Write approximate-derivative without calling any helper methods.

  (define approximate-derivative
    (lambda (f)
      (lambda (x) (/ (- (f (+ x 0.01)) (f x)) 0.01))))


Linear recursion on (linked) lists
==================================
Question:

  Give pseudo-code for a procedure that takes two (linked) lists and
  concatenates them.

Answer:

  if the first list is empty
    return the second list
  else
    return the first element of the first list
     attached to the front of
      the rest of the first list concatenated with the second list

Question:

  Write this in scheme.

Answer:

  (define concatenate
    (lambda (l1 l2)
      (if (null? l1) l2
        (cons (car l1) (concatenate (cdr l1) l2)))))


Procedures taking an arbitrary number of arguments
==================================================

Recall from lecture the + procedure (among others) take any
number of arguments:
    (+ 2 2)  => 4
    (+ 1 2 3 4 5 6 7)  => 28
    (+ 5)  => 5
    (+)  => (exercise, equals 0, the additive identity)

How can we write such a function? Another form for lambda:

  (lambda args exp ...)

Here args is a list of the parameters given to the function when it's called.

Question:

  Suppose we are given the procedure binary-add that adds two
  numbers. That is, 

    (define binary-add (lambda (x y) (+ x y)))

  Write the function sum that takes an arbitrary number of arguments and
  uses binary-add to compute the sum of the arguments. You may not use +.

Answer:

  We need to do this recursively.
  What are our base cases? Zero or one arguments!
  How do we test for them?

    (define sum (lambda args
      (cond ((null? args) 0)
	    ((null? (cdr args)) (car args))
	    (else ...))))

  How do we write the recursive case?
  Keep a running total. Remove the first two numbers, add them,
  cons the answer to the front of the list (remember, not changing the
  list, but creating new data), and apply the result to sum.

    (define sum
      (lambda args
	(cond ((null? args) 0)
	      ((null? (cdr args)) (car args))
	      (else (apply sum (cons (binary-add (car args) (car (cdr args)))
				     (cdr (cdr args))))))))

  Works!
    (sum) => 0
    (sum 1) => 1
    (sum 1 2) => 3
    (sum 1 2 3) => 6

Let
===
Our definition of sum is horrible to read. It's hard to understand what
all the car's and cdr's are supposed to be. We can use local variables
to help with readability.

Form:
  (let ((var1 val1)
	(var2 val2)
	... )
    expr ... )

Question: How to clean up the readability of sum using let?

Attempt 1:

    (define sum
      (lambda args
	(let ((arg1 (car args))
	      (arg2 (car (cdr args)))
	      (therest (cdr (cdr args))))
	  (cond ((null? args) 0)
		((null? arg2) arg1)
		(else (apply sum (cons (binary-add arg1 arg2) therest)))))))

  Doesn't work though! Get strange car errors:
    car: expects argument of type <pair>; given ()

  Why? Our let assumes there are at least two arguments. We have to check
  that first.

Answer:

    (define sum
      (lambda args
	(cond ((null? args) 0)
	      ((null? (cdr args)) (car args))
	      (else 
	       (let ((arg1 (car args))
		     (arg2 (car (cdr args)))
		     (therest (cdr (cdr args))))
		 (apply sum (cons (binary-add arg1 arg2) therest)))))))

Symbols
=======
We've seen how to quote a list in scheme:
  '(1 2 3)  => (1 2 3)

What about if we use identifiers instead?
  '(a b c)  => (a b c)
  (car '(a b c))  => a

What is a here? Quote has stopped a from being evaluated, so it's just
left as an identifier. What is its type? In Scheme, we call it a symbol.

We can use any sequence of characters that could be used as an
identifier in Scheme.

What can we do with symbols?

  - Check for equality using eq?

      (eq? 'abc 'AbC) => #t
      (eq? '1+?2x 'sadf) =>#f

  - Test whether we have a symbol using symbol?

      (symbol? '()) => #f
      (define a 1)
      (symbol? 'a) => #t
      (symbol? a) => #f

Question:

  Define a procedure tell-me that takes one parameter and prints
  "Harry likes Sally" if the argument is the symbol please,
  and prints "No" if the argument is anything else.

Answer:

  (define tell-me
    (lambda (x)
      (if (eq? x 'please)
	  (display "Harry likes Sally")
	  (display "No"))))

Exercise:

  tell-me prints its output without a newline, which looks less than
  aesthetic. Modify the tell-me procedure so that it prints a newline
  appropriately.

Answer:

  Since tell-me prints something in both cases, we could just add a
  newline call after the if:

  (define tell-me
    (lambda (x)
      (if (eq? x 'please)
	  (display "Harry likes Sally")
	  (display "No"))
      (newline)))

Exercise: What if we only wanted the newline printed in the "No" case?