Chapter 4 - Numbers Games#
1996 Friedman, Daniel P. & Matthias Felleisen. The Little Schemer. 4e. MIT Press.
; n + 1, increase quantity n by unity
(define add1
(lambda (n)
(+ n 1)))
; n - 1, decrease quantity n by unity
(define sub1
(lambda (n)
(- n 1)))
; n + m, nonnegative integer addition - unity added to quantity n, m times
(define o+
(lambda (n m)
(cond
( (zero? m) n )
( else (add1 (o+ n (sub1 m))) ))))
; n - m, nonnegative integer subtraction - unity subtracted from quantity n, m times
(define o-
(lambda (n m)
(cond
( (zero? m) n )
( else (sub1 (o- n (sub1 m))) ))))
; one-tup sum
(define addtup
(lambda (tup)
(cond
( (null? tup) 0 )
( else (o+ (car tup) (addtup (cdr tup))) ))))
; n x m, nonnegative integer multiplication - quantity n added to itself m times
(define x
(lambda (n m)
(cond
( (zero? m) 0 )
( else (o+ n (x n (sub1 m))) ))))
; two-tup sum (elementwise)
(define tup+
(lambda (tup1 tup2)
(cond
( (null? tup1) tup2 )
( (null? tup2) tup1 )
( else (cons (o+ (car tup1) (car tup2)) (tup+ (cdr tup1) (cdr tup2))) ))))
; n > m ?
(define >
(lambda (n m)
(cond
( (zero? n) #f )
( (zero? m) #t )
( else (> (sub1 n) (sub1 m)) ))))
; n < m ?
(define <
(lambda (n m)
(cond
( (zero? m) #f )
( (zero? n) #t )
( else (< (sub1 n) (sub1 m)) ))))
; n = m ?
(define =
(lambda (n m)
(cond
( (> n m) #f )
( (< n m) #f )
( else #t ))))
; n^m, nonnegative integer exponentiation - quantity n multiplied by itself m times
(define exp
(lambda (n m)
(cond
( (zero? m) 1 )
( else (x n (exp n (sub1 m)) )))))
; n/m, nonnegative integer division - the number of times quantity m fits inside of quantity n
(define ÷
(lambda (n m)
(cond
( (< n m) 0 )
( else (add1 (÷ (o- n m) m)) ))))
; get the length of a list
(define length
(lambda (lat)
(cond
( (null? lat) 0 )
( else (add1 (length (cdr lat))) ))))
; get the n-th element of a list
(define pick
(lambda (n lat)
(cond
( (zero? (sub1 n)) (car lat) )
( else (pick (sub1 n) (cdr lat)) ))))
; remove the n-th element of a list
(define rempick
(lambda (n lat)
(cond
( (zero? (sub1 n)) (cdr lat) )
( else (cons (car lat) (rempick (sub1 n) (cdr lat)) )))))
; remove all numbers from a list
(define no-nums
(lambda (lat)
(cond
( (null? lat) '())
( (number? (car lat)) (no-nums (cdr lat)))
( else (cons (car lat) (no-nums (cdr lat)) )))))
; remove all non-numbers from a list
(define all-nums
(lambda (lat)
(cond
( (null? lat) '() )
( (number? (car lat)) (cons (car lat) (all-nums (cdr lat))) )
( else (all-nums (cdr lat)) ))))
; equals, atoms and numbers
(define eqan?
(lambda (a1 a2)
(cond
( (and (number? a1) (number? a2)) (= a1 a2) )
( (or (number? a1) (number? a2)) #f )
( else (eq? a1 a2) ))))
; get the number of occurrences of an element in a list
(define occur
(lambda (a lat)
(cond
( (null? lat) 0 )
( (eq? (car lat) a) (add1 (occur a (cdr lat))) )
( else (occur a (cdr lat)) ))))
; n = 1 ?
(define one?
(lambda (n)
(= n 1)))
(define rempick
(lambda (n lat)
(cond
( (one? n) (cdr lat) )
( else (cons (car lat) (rempick (sub1 n) (cdr lat)) )))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Chapter 4 - Numbers Games
(atom? 14) ; #t
(atom? -3) ; #t
(atom? 3.14159) ; #t
(define add1
(lambda (n)
(+ n 1)))
(define sub1
(lambda (n)
(- n 1)))
(add1 67) ; 68
(sub1 5) ; 4
(sub1 0) ; -1
(zero? 0) ; #t
(zero? 1492) ; #f
; addition, nonnegative integer
; adds unity to n as many times as unity may be subtracted from m
; until m reaches null
(define o+
(lambda (n m)
(cond
; vvvvvvvvvvv Are there no more units to add to quantity n? If not, then return quantity n.
( (zero? m) n )
( else (add1 (o+ n (sub1 m))) ))))
; ^^^^ constructor of numbers - add a unit to quantity n
; ^^^^^^^^^^^^^^^ natural recursion - add m-1 units to quantity n
(o+ 46 12) ; 58
; subtraction, nonnegative integer
; subtracts unity from n as many times as unity may be subtracted from m
; until m reaches null
; (rule: m cannot be negative)
(define o-
(lambda (n m)
(cond
; vvvvvvvvvvv Are there no more units to subtract from quantity n? If not, then return quantity n.
( (zero? m) n )
( else (sub1 (o- n (sub1 m))) ))))
; ^^^^ constructor of numbers - subtract a unit from quantity n
; ^^^^^^^^^^^^^^^ natural recursion - subtract m-1 units from quantity n
(o- 14 3) ; 11
(o- 17 9) ; 8
(o- 18 25) ; -7
; (tup? '(2 11 3 79 47 6)) ; #t
; (tup? '(8 55 5 555)) ; #t
; (tup? '(1 2 8 apple 4 3)) ; #f
; (tup? '(3 (7 4) 13 9)) ; #f
; (tup? '()) ; #t
; addtup, nonnegative integer
; builds a number by totaling all the numbers in a tup
(define addtup
(lambda (tup)
(cond
; vvvvvvvvvvvvv Is the tup empty? If so, then return the empty number.
( (null? tup) 0 )
( else (o+ (car tup) (addtup (cdr tup))) ))))
; ^^ constructor of numbers
; ^^^^^^^^^ typical element - a number
; ^^^^^^^^^^^^^^^^^^ natural recursion
(addtup '(3 5 2 8)) ; 18
(addtup '(15 6 7 12 3)) ; 43
; multiplication, nonnegative integer
; builds up a number by adding a quantity n up m times
(define x
(lambda (n m)
(cond
; vvvvvvvvvvv Are there no more additions of quantity n? If not, then return the empty addition.
( (zero? m) 0 )
( else (o+ n (x n (sub1 m))) ))))
; ^^ constructor of numbers
; ^ typical element - the quantity n
; ^^^^^^^^^^^^^^ natural recursion - multiply the quantity n by m-1 times
(x 5 3) ; 15
(x 13 4) ; 52
(x 12 3) ; 36
; (zero? 3) - no
; (+ 12 (x 12 2))
; (zero? 2) - no
; (+ 12 (+ 12 (x 12 1)))
; (zero? 1) - no
; (+ 12 (+ 12 (+ 12 (x 12 0))))
; (zero? 0) - yes
; (+ 12 (+ 12 (+ 12 0)
; (+ 12 (+ 12 12)
; (+ 12 24)
; 36
; tup+
; number-wise addition of two n-number tups
; inputs: tup1, tup2
; output: tup
;
; tup+ recurs on two tups simultaneously, and so we need to ask four questions
; 1. (and (null? tup1) (null? tup2))
; 2. (null? tup1)
; 3. (null? tup2)
; 4. else
; this can be reduced to two, since the two tups must have the same length
; (i.e., (null? tup1) is true exactly when (null? tup2) is true)
; 1. (and (null? tup1) (null? tup2))
; 2. else
;
; (define tup+
; (lambda (tup1 tup2)
; (cond
; ((and (null? tup1) (null? tup2)) '())
; (else (cons (o+ (car tup1) (car tup2)) (tup+ (cdr tup1) (cdr tup2)) )))))
;
; If tup1 is null before tup2, we need to ask ((null? tup1) tup2).
; If tup2 is null before tup1, we need to ask ((null? tup2) tup1).
; The order of these terminal conditions does not matter, and else is the last question because
; either one or the other is true if either one of the tups does not contain at least one number.
(define tup+
(lambda (tup1 tup2)
(cond
( (null? tup1) tup2 )
( (null? tup2) tup1 )
( else (cons (o+ (car tup1) (car tup2)) (tup+ (cdr tup1) (cdr tup2))) ))))
; ^^^^ constructor of lists
; ^^^^^^^^^^^^^^^^^^^^^^^^^^ typical element - the sum of the ith number of each tup
; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion on tup+
(tup+ '(3 6 9 11 4) '(8 5 2 0 7)) ; (11 11 11 11 11)
(tup+ '(2 3) '(4 6)) ; (6 9)
(tup+ '(3 7) '(4 6)) ; (7 13)
; (and (null? (3 7)) (null? (4 6))) - no
; (cons 7 (tup+ (7) (6)))
; (and (null? (7)) (null? (6))) - no
; (cons 7 (cons 13 (tup+ () ())))
; (and (null? ()) (null? ())) - yes
; (cons 7 (cons 13 ()))
; (cons 7 (13))
; (7 13)
(tup+ '(3 7) '(4 6 8 1)) ; (7 13 8 1)
(tup+ '(3 7 8 1) '(4 6)) ; (7 13 8 1)
; greater-than
; inputs: n [int], m [int]
; output: bool
;
; the order of the terminal conditions matters
; if ((zero? m) #t) comes before ((zero? n) #f) then (> 3 3) is #t, which is incorrect
; if ((zero? n) #f) comes before ((zero? m) #t) then (> 3 3) is #f, which is correct
(define >
(lambda (n m)
(cond
( (zero? n) #f )
( (zero? m) #t )
( else (> (sub1 n) (sub1 m)) ))))
; no constructor, we aren't constructing anything
; ^^^^^^^^^^^^^^^^^^^^^ natural recursion on >
(> 12 133) ; #f
(> 120 11) ; #t
(> 3 3) ; #f
; less-than
; inputs: n [int], m [int]
; output: book
;
; n < m - the order of the terminal condition matters
; incorrect order
; ((zero? n) #t) - if n = 0, regardless of whether m = 0 or m > 0, then n < m is true - INCORRECT
; ((zero? m) #f)
; correct order
; ((zero? m) #f) - if m = 0, regardless of whether n = 0 or n > 0, then n < m is false - CORRECT
; ((zero? n) #t) - if m > 0 and n = 0, then n < m is true - CORRECT
(define <
(lambda (n m)
(cond
( (zero? m) #f )
( (zero? n) #t )
( else (< (sub1 n) (sub1 m)) ))))
; no constructor, we aren't constructing anything
; ^^^^^^^^^^^^^^^^^^^^^ natural recursion on <
(< 4 6) ; #t
(< 8 3) ; #f
(< 6 6) ; #f
; equals
; inputs: n [int], m [int]
; output: bool
;
; 1-2) if m = 0 then return (zero? n)
; 3) if m > 0 and n = 0 then return #f
; 4) if m, n > 0 then recur
;
; (define =
; (lambda (n m)
; (cond
; ((zero? m) (zero? n))
; ((zero? n) #f)
; (else (= (sub1 n) (sub1 m)) ))))
; no constructor, we aren't constructing anything
; ^^^^^^^^^^^^^^^^^^^^^ natural recursion on =
;
; non-recursive definition of = in terms of < and >
(define =
(lambda (n m)
(cond
( (> n m) #f )
( (< n m) #f )
( else #t ))))
; exponentiation
; inputs: n [int], m [int]
; output: int
(define exp
(lambda (n m)
(cond
( (zero? m) 1 )
( else (x n (exp n (sub1 m)) )))))
; ^ constructor of numbers
; ^ typical element - the quantity n
; ^^^^^^^^^^^^^^^^ natural recursion - raise the quantity n to the m-1 power
(exp 1 1) ; 1
(exp 2 3) ; 8
(exp 5 3) ; 125
; division, nonnegative integer
; counts how many times the second argument fits into the first one
(define ÷
(lambda (n m)
(cond
; vvvvvvvvv Is the dividend smaller than the divisor? If so, then the divisor does not go into the dividend.
( (< n m) 0 )
( else (add1 (÷ (o- n m) m)) ))))
; ^^^^ constructor of numbers - increase the number of times the divisor goes into the divident
; ^^^^^^^^^^^^^^ natural recursion - decrease the dividend by the divisor and recur
(÷ 15 4) ; 3
; (< 15 4) - no
; + 1 (÷ 11 4)
; (< 11 4) - no
; + 1 (+ 1 (÷ 7 4))
; (< 7 4) - no
; + 1 (+ 1 (+ 1 (÷ 3 4)))
; (< 3 4) - yes
; + 1 (+ 1 (+ 1 0))
; + 1 (+ 1 1)
; + 1 2
; 3
; length
(define length
(lambda (lat)
(cond
( (null? lat) 0 )
( else (add1 (length (cdr lat))) ))))
; ^^^^ constructor of numbers
; ^^^^^^^^^^^^^^^^^^ natural recursion
(length '(hotdogs with mustard sauerkraut and pickles)) ; 6
(length '(ham and cheese on rye)) ; 5
; pick
; inputs: n [int], lat [lat]
; output: atom
(define pick
(lambda (n lat)
(cond
( (zero? (sub1 n)) (car lat) )
( else (pick (sub1 n) (cdr lat)) ))))
; no constructor
; ^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion
(pick 4 '(lasagna spaghetti ravioli macaroni meatball)) ; macaroni
(pick 0 '(a)) ; no answer
; rempick
; inputs: n [int], lat [lat]
; output: lat
(define rempick
(lambda (n lat)
(cond
( (zero? (sub1 n)) (cdr lat))
; ( (one? n) (cdr lat))
( else (cons (car lat) (rempick (sub1 n) (cdr lat)) )))))
; ^^^^ constructor
; ^^^^^^^^^ typical element - atom
; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion of rempick
(rempick 3 '(hotdogs with hot mustard)) ; (hotdogs with mustard)
(rempick 3 '(lemon meringue salty pie)) ; (lemon meringue pie)
(number? 'tomato) ; #f
(number? 76) ; #t
; no-nums
; removes all the numbers from a lat
; inputs: lat [lat]
; output: lat
(define no-nums
(lambda (lat)
(cond
( (null? lat) '())
( (number? (car lat)) (no-nums (cdr lat)))
( else (cons (car lat) (no-nums (cdr lat)) )))))
; ^^^^ constructor
; ^^^^^^^^^ typical element - atom
; ^^^^^^^^^^^^^^^^^^^ natural recursion of no-nums
(no-nums '(5 pears 6 prunes 9 dates)) ; (pear prunes dates)
; all-nums
; extracts a tup from a lat using all the numbers in the lat
(define all-nums
(lambda (lat)
(cond
( (null? lat) '() )
( (number? (car lat)) (cons (car lat) (all-nums (cdr lat))) )
( else (all-nums (cdr lat)) ))))
; ^^^^ constructor of lists
; eqan
; true if its two arguments are the same atom
(define eqan?
(lambda (a1 a2)
(cond
( (and (number? a1) (number? a2)) (= a1 a2) )
( (or (number? a1) (number? a2)) #f )
( else (eq? a1 a2) ))))
; occur
; counts the number of times an atom appears in a lat
(define occur
(lambda (a lat)
(cond
( (null? lat) 0 )
( (eq? (car lat) a) (add1 (occur a (cdr lat))) )
( else (occur a (cdr lat)) ))))
; one?
;
; (define one?
; (lambda (n)
; (cond
; ((zero? n) #f)
; (else (zero? (sub1 n))))))
(define one?
(lambda (n)
(= n 1)))