;;; $Id: expt-maker-mod.scm,v 1.1 2006/02/08 17:53:15 leavens Exp $
;;; A literate, fully developed, example of how to combine numerical recursion
;;; and higher order functions. 

(module expt-maker-mod (lib "typedscm.ss" "typedscm")

  (provide expt-maker)
  
  ;; We want to write a procedure

  (deftype expt-maker (-> (number) (-> (number) number)))

  ;; that takes a non-negative integer, n, and returns a procedure that
  ;; takes a number, x, and multiplies x by itself n times.
  ;;
  ;; Examples are given in expt-maker-mod.tst
  ;;
  ;; A solution recognizes from the first and last examples that
  ;;
  ;;   ((expt-maker 0) x) = 1
  ;;
  ;; which is the base case, so that (expt-maker 0) returns the function
  ;; that when applied to x, returns 1, i.e., (lambda (x) 1).  That is,
  ;;
  ;;    (expt-maker 0) = (lambda (x) 1)
  ;;
  ;; For the inductive case we have to look at related simplier examples.
  ;; Since the argument to expt-maker is a number, we look at a number and
  ;; the next smaller number, like:
  ;; 
  ;;      ((expt-maker 4) 3) = 81
  ;;      ((expt-maker 3) 3) = 27
  ;; 
  ;; Now we can ask: how do we get 81 from the answer for the recursive call
  ;; (27) and the other information.  It works like this...
  ;; 
  ;;     ((expt-maker 4) 3)
  ;;    = <by the example>
  ;;     81
  ;;    = <by arithmetic>
  ;;     (* 3 27)
  ;;    = <by the simplier example, 27 is ((expt-maker 3) 3)>
  ;;     (* 3 ((expt-maker 3) 3))
  ;; 
  ;; So we conclude that
  ;; 
  ;;     ((expt-maker 4) 3) = (* 3 ((expt-maker 3) 3))
  ;; 
  ;; Now, let's generalize, calling the 4, that is the argument to the
  ;; inner call n, and calling 3 that is the outer argument x.
  ;; 
  ;;     ((expt-maker n) x) = (* x ((expt-maker (- n 1)) x))
  ;; 
  ;; This tells us the general form of the inductive case.  Notice also the
  ;; recursive call inside: (expt-maker (- n 1)),
  ;; 
  ;; So we see that (expt-maker n) returns a function that, when applied
  ;; to any arugment x, returns (* x ((expt-maker (- n 1)) x)).  That is:
  ;; 
  ;;     (expt-maker n) = (lambda (x) (* x ((expt-maker (- n 1)) x)))
  ;; 
  ;; So we fit this into the outline for numerical recursion
  ;; 
  ;; (define expt-maker
  ;;   (lambda (n)
  ;;     (cond
  ;;      ((zero? n) _________________)
  ;;      (else (_________  (expt-maker (- n 1))___________)))))
  ;; 
  ;; by using the information about the base and inductive cases we gained
  ;; from analyzing and generalizing the examples above:

  (define expt-maker
    (lambda (n)
      (cond
       ((zero? n) (lambda (x) 1))
       (else (lambda (x) (* x ((expt-maker (- n 1)) x)))))))

) ;; end module