Comp 200 Lecture
NatNums

Some more counting

Related-but-different from the previous example of #outfits:
Suppose i have 5pr pants, and i wear *all* of them. How long until i have to repeat an ordering?
Equivalently: 5 students in 5 chairs -- how many until repeat an ordering?
5 * 4 * 3 * 2 * 1
What if i have 6 students?
6 * (number-arrangements-of-5-students)
What if i have 2 students? 2*1. One student? 1. Zero students? 1.
This is sometimes called "factorial":
5! = 5*4*3*2*1.
1! = 1.
Base case: 0! = 1. (Think of multiplying no numbers at all.)

Now let's look at functions involving natural numbers (0, 1, 2, ...). We mentioned earlier:

Definition: a NatNum is either

• 0
• (+ NatNum 1)

Write factorial (recall the defn of NatNum; code will mirror it); Cruise a bit quickly here, since this is also in hofstadter:

;; (! n): natNum --> number
;; Given n, return n!.
;;
(define (! n)
    (if (= n 0)
        ...
        ...(! (sub1 n))...))

; Test cases (think about what stepper does):
(! 2)
(! 3)

;; (! n): natNum --> number
;; Given n, return n!.
;;
(define (! n)
    (if (= n 0)
        1
        (* n (! (sub1 n)))))

A student's question: Why do we recur on n-1? Why not just recur on n, wouldn't that be more direct?'

functions returning lists

We've seen some functions which process lists, and which process natural numbers, in class. But so far these functions have always returned a number or a boolean. Here are some exercises which have one slight twist: they return a list. Not a big deal; just remember your tool cons, which if you're given one list, lets you make a slightly longer list.

1. ;; (countdown n): NatNum --> (list-of (or NatNum symbol))
   ;; Return a list of numbers counting down to 'blastoff.  E.g.
   ;;   (countdown 3) = (cons 3 (cons 2 (cons 1 (cons 'blast-off empty))))
   ;;   (countdown 1) = (cons 1 (cons 'blast-off empty))
   ;;   (countdown 0) =  [What should the answer be?  (Must obey the contract!)]
   ;;
   

   This takes in a NatNum, so we'll start with a program that looks like NatNum's definition:

   (define (countdown n)
       (if (= n 0)
           ...
           ...(countdown (sub1 n))...))
   

   How to fill in the ...s? (Hint: When n is, say, 3, we know what (countdown (sub1 n)) will return. How can we use that result, to get the desired answer for (countdown n)?)

2. ;; (uninvite-daphne names): (list-of symbol) --> (list-of symbol)
   ;; Return another list which is like names but w/o any occurrences of 'daphne.
   ;;
   

   Hint:
   1. write the define bit;
   2. write an "if" that asks whether the list is empty or not;
   3. if non-empty use first/rest to extract the sub-parts of names; ask what first/rest return, and put in any recursive calls;
   4. ask what the recursive calls return, and finally:
   5. figure how to put together the pieces you have to get desired answer.
   These are the main steps. If you get stuck on one of these, you can remind yourself of the more detailed list of steps from the lecture on writing functions-on-lists.

We probably won't get this far:

The Law of Scheme

Expressions:                           How to evaluate them:
  1. values                             - Easy: just themselves.
     (numbers, booleans, symbols, 
      lists, functions)
  2. placeholders                       - Easy: just look up the 'define'
     eg: pi, washer-area, etc.
  3. function application               - evaluate each expression to get
     (exp0 exp1 exp2 ... expn)             (val0 val1 val2 ... valn)
     They start with a paren.              NB val0 had better be a function!
     a. primitive                          a: val0 is is a built-in function
                                              - just apply to val1...valn.
     b. constructed                        b: val0 names a user-defined function
                                              - just re-write the *body* of the
                                                function definition...oh,
                                                replace parameters
                                                with val1...valn.
                                                Evaluate that.
  4. Special forms:
       define
     This are the only places where () doesn't mean call-a-function.
     (How do we know that "define" couldn't be a built-in function,
      and just use the rules for 3. above?)

• Consider (= 1 (/ 7 0)). Clearly the (/ 7 0) will cause an error, even before = gets called. Fine.
• But now consider

       (or (= 4 (+ 2 2))
           (= 1 (/ 7 0)))
  

  If we followed Law #3 above, we'd have to evaluate (= 1 (/ 7 0)) before calling or. And as we just saw, evaluating (= 1 (/ 7 0)) entails first evaluating (/ 7 0), causing an error immediately. But what should the answer be to the original expression? See if Dr Scheme agrees!
• You might think "What a silly example; nobody would ever try dividing by 0." But we don't always know in advance what we are dividing by!

      ;; (avg sum n) : number, number --> number
      ;; Given the sum of n items, return the average,
      ;; but be sure to not divide-by-zero!
      ;; (In that case we return a symbol, 'average-of-zero-things-is-undefined.)
      ;;
      (define (avg sum n)
           (if (= n 0)
               'average-of-zero-things-is-undefined
               (/ sum n)))
  
      (avg 0 0)      ; Were "if" ordinary, the above rules would try 0/0.