Module 5 Extra Materials

Fibonacci numbers

Recall A1 where you are asked to write a non-recursive function
for fibonacci numbers. Now we are writing a recursive version.

There are two base cases!

$f(0) = 0, f(1) = 1$

Recursive case:

$f(n) = f(n-1) + f(n-2)$

;; (fib n) computes the nth fibonacci number.
;; fib: Nat -> Nat
;; Examples:
(check-expect (fib 0) 0)
(check-expect (fib 1) 1)

(define (fib n)
  (cond
    [(zero? n) 0]
    [(= n 1) 1]
    [else (+ (fib (- n 1)) (fib (- n 2)))]))

Slide 31: String Prefixes Example

;; (prefixes s) produces a list of prefixes of s,
;; in the order of the shortest prefix to the longest
;; (that is, the string itself)
;; prefixes: Str -> (listof Str)
;; Examples:
(check-expect (prefixes "") (list ""))
(check-expect (prefixes "abc") (list "" "a" "ab" "abc"))

(define (prefixes s)
  ...)

In the slides, it has hinted the pattern: the produced value should be a list of values from (substring s 0 k) where k is from 0 to the length of s.

(list (substring s 0 0) (substring s 0 1) ... (substring s 0 k))

• Should I count up or count down?
  • In this case, the string are in increasing length - the base case should produce the string itself (that is, k is (string-length s)).
    • We are counting up.
• Our recursive function should know the length of the string we are producing at a time; however, prefixes takes only a string, so we have no way to keeping track of length of the string we produce at a time.
  • That means we need to introduce extra parameters to this function for that length.
    • but the problem says prefixes should only have one argument!
    • make prefixes a wrapper and write a recursive helper.

(define (prefix-from s len)
  (cond
  [(= len (string-length s)) (list s)]
  [else (cons (substring s 0 len)
              (prefixes-from s (add1 len)))])

(define (prefixes s)
  (prefixes-from s 0))

Slide 34: gcd-three

Remember that the strategy we use is counting down from (min n1 n2 n3) to the first common denominator we meet. That first common denominator have to be the greatest (why?).

(define (gcd-three-search n1 n2 n3 k)
  (cond
    [(common? k n1 n2 n3) k]
    [else (gcd-three-search n1 n2 n3 (sub1 k))]))

;; gcd-three: Nat Nat Nat -> Nat
;; requires: n1 n2 n3 > 0
(define (gcd-three n1 n2 n3)
  (gcd-three-search n1 n2 n3 (min n1 n2 n3)))

Slide 55: A new type Point

For every single non-recursive "structure type" (A type does is a grouping of finite values), we want to make sure we have the constructor function (i.e. make a value of this structure type from the values given) and accessor function (access individual values from this structure).

;; (make-point x y) creates a Point given x and y coordinates.
;; contract: exercise
(define (make-point x y)
  (list x y))

(define (point-x p) (first p))
(define (point-y p) (second p))

Using these new functions we can then write a function that calculates the distance between two Points.

;; (point-dist p1 p2) produce the distance between p1 and p2.
;; point-dist: Point Point -> Num
;; Examples:
(check-expect (point-dist (make-point 3 4) (make-point 0 0)) 5)
(check-expect (point-dist (make-point 5 12) (make-point 0 0)) 13)

(define (point-dist p1 p2)
  (sqrt (+ (sqr (- (point-x p1) (point-x p2)))
           (sqr (- (point-y p1) (point-y p2))))))

Slide 59: add remove for association lists

Here are the solution for al-add and al-remove. Make sure you check this after you write your own version!

Although the functions we write here corresponds to the definition in the slides, these implementations should work for any kind of key and value.

;; (al-add al k v) produces a new association list created by
;; trying to add the association (key-value pair) (k, v) into al.
;; if k already exists in al, produce al.
;; al-add: AL Num Str -> AL
(define (al-add al k v)
  (cond
    ;; Remember, all keys in the association list *must be unique*!
    ;; Add (k, v) onto al only if no pair of such key exists.
    [(equal? (assoc k al) false) (cons (list k v) al)]
    [else al]))

;; (al-remove al k) produces a new association list created by
;; removing the association (key-value pair) with key k from al.
;; if no such association does not exist in al, produce al.
;; al-remove: AL Num -> AL
(define (al-remove al k)
  (cond
    [(empty? al) empty]
    [(equal? k (first (first al))) (rest al)]
    [else (cons (first al) (al-remove (rest al) k))]

Exercise: write the function al-add-replace which adds an association $(k, v)$ to an association list al, but when there is already an element with key $k$, replace the corresponding value with $v$.