Scheme

- Typical recursion templates
- Three important classes of recursive list functions:
*mapping*,*reducing*,*filtering*. - Tail recursion
- Higher order functions and applicative programming
- Lexical closures

Use the "debug" button DrScheme to debug programs, and also to understand how recursive functions are operating

;; general form (define (func x) (if end-test end-value (augmenting-function augmenting-value (func reduced-x))))Factorial is the classic example:

(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))Many Scheme functions operate on lists, so we often see an important special case of augmenting recursion where our augmenting function is

(define (double-each s) (if (null? s) '() (cons (* 2 (car s)) (double-each (cdr s)))))Our base value (the value returned when we reach the base case) isn't always ():

(define (my-append x y) (if (null? x) y (cons (car x) (my-append (cdr x) y))))A final important kind of recursion over lists is the class of

;; sum the elements of a list (define (sumlist x) (if (null? x) 0 (+ (car x) (sumlist (cdr x)))))

;; general form: (define (func x) (cond (end-test-1 end-value-1) (end-test-2 end-value-2) (else (func reduced-x)))) ;; example: are all elements of a list positive? (define (all-positive x) (cond ((null? x) #t) ((<= (car x) 0) #f) (else (all-positive (cdr x))))) ;; (all-positive '(3 5 6)) => #t ;; (all-positive '(3 5 -6)) => #fSome tail recursive functions will have more than one argument. All but one of the arguments are passed along unaltered.

;; example: member: (define (my-member e x) (cond ((null? x) #f) ((equal? e (car x)) #t) (else (my-member e (cdr x)))))A less commonly seen form is

Scheme compilers handle tail recursion very efficiently, as efficiently as a program that just uses loops instead of recursion. (In particular, tail recursive functions don't use stack space for every recursive call.)

(define (factorial n) (acc-factorial n 1)) ;; auxiliary function that takes an additional parameter (the accumulator, ;; i.e. the result computed so far) (define (acc-factorial n sofar) (if (zero? n) sofar (acc-factorial (- n 1) (* sofar n))))

;; test whether two lists have the same length (define (same-length x y) (cond ((and (null? x) (null? y)) #t) ((null? x) #f) ((null? y) #f) (else (same-length (cdr x) (cdr y))))) ;; do these two objects have the same shape? (define (same-shape x y) (cond ((and (pair? x) (pair? y)) (and (same-shape (car x) (car y)) (same-shape (cdr x) (cdr y)))) ((or (pair? x) (pair? y)) #f) (else #t)))

(addlists '(1 2 3) '(10 11 12)) => '(11 13 15)

(define (func x) (cond (end-test end-value) (aug-test (augmenting-function augmenting-value (func reduced-x))) (else (func reduced-x)))) ;; example: remove all non-positive numbers from a list (define (positive-numbers x) (cond ((null? x) '()) ((> (car x) 0) (cons (car x) (positive-numbers (cdr x)))) (else (positive-numbers (cdr x)))))

(filter even? '(1 2 3 4 5)) => (2 4)Define your own version

;; variation on list-consing recursion (define (insert x s) (cond ((null? s) (list x)) ((< x (car s)) (cons x s)) (else (cons (car s) (insert x (cdr s)))))) ;; augmenting recursion (define (isort s) (if (null? s) '() (insert (car s) (isort (cdr s)))))

Map is a built in Scheme function that takes a function and a list as an argument, and returns the list that results by applying that function to every element of the list.

(map function list) ;; general form (map null? '(3 () () 5)) => (() T T ()) (map round '(3 3.3 4.6 5)) => (3 3 5 5) (map cdr '((1 2) (3 4) (5 6))) => ((2) (4) (6))

(map (lambda (x) (* 2 x)) '(3 4 5)) ;; the right way to define addN-to-list (define (addN-to-list alist n) (map (lambda (x) (+ n x)) alist))Please note that in the addN-to-list function, the body of the lambda function can refer to the variable n, which is in the lexical scope of the lambda expression.

map can also be used with functions that take more than one argument. Examples:

(map + '(1 2 3) '(10 11 12)) => (11 13 15) (map (lambda (x y) (list x y)) '(a b c) '(j k l)) => ((a j) (b k) (c l))

(define (my-map func alist) (if (null? alist) '() (cons (func (car alist)) (my-map func (cdr alist)))))

(define (addN-to-list alist n) (my-map (lambda (x) (+ n x)) alist))When the lambda expression is used in

As an example, let's define a simple function `test`:

(define (test x) (+ x 1))Evaluating

However, if we evaluate

(let ((test (lambda (x) (* x 2))) (test 10))we get 20 -- within the