Functional Programming
Homework Solutions
COMS 362.01

From Homework 1:

(define sigma (m n) ; to sum m up to n
(if (> m n) 0 (+ n (sigma m (- n 1)) ) )
; add n to the sum of m up to n-1
)

(define exp (m n) ; to raise m to the n
(if (= n 0) 1 (* m (exp m (- n 1)) ) )
; multiply m by m to the n-1
)

(define binary(m) ; to return binary for n
(if (+ (= m 0) (= m 1)) m (+ (* 10 (binary (/ m 2))) (mod m 2)))
)

(define or(x y) (if x 1 y))

(define choose(n k)
;; returns binomial coeff n choose k
(if (or (= k 0) (= n k)) 1 (+ (choose (- n 1) k) (choose (- n 1) (- k 1)))
) )

From Homework 2:

(define nth-elt(n l) ; returns nth elt of list l
(if (null? l) '() (if (= n 1) (car l) (nth-elt (- n 1) (cdr l)))))

(define append(l1 l2) ;; needed below (if (null? 11) l2 (cons (car l1) (append (cdr l1) l2))))

(define list1(x) (cons x '()))

(define reverse(l) ; assumes append and list1 already defined
(if (null? l) '() (append (reverse(cdr l)) (list1 (car l)))))

From Homework 3:

(define or(x y) (if x 1 y))

(define atom?(x) (or (symbol? x) (number? x)))

(define countatoms(l)
(if (null? l) 0
(if (atom? (car l)) (+ 1 (countatoms (cdr l))) (+ (countatoms (car l)) (countatoms (cdr l))))))

(define member?(x s) ;; test if atom x is a member of set s
(if (null? s) '() (if (= x (car s)) 'T (member? x (cdr s)))))

(define union(s1 s2)
(if (null? s1) s2
(if (member? (car s1) s2) (union (cdr s1) s2) (cons (car s1) (union (cdr s1) s2))))))

(define intersection(s1 s2)
(if (null? s1) '() ;; simple but not as efficient as could be
(if (member? (car s1) s2) (cons (car s1) (intersection (cdr s1) s2)) (intersection (cdr s1) s2))))

Back to COMS 362 Syllabus Page