(exp->english '(+ (sin x) (cos y))) ==> (the sum of the sine of x and the cosine of y)
(define (exp->english x) (if (pair? x) (append (op->english (op x)) (exp->english (lhs x)) (if (null? (cddr x)) ; test for unary '() ; if unary, that's all (cons 'and ; else do rhs also (exp->english (rhs x)) ) ) ) (list x) ) ) ; base case: make a list for append (define (op->english op) (list 'the (cadr (assoc op '((+ sum) (- difference) (* product) (/ quotient) (sin sine) (cos cosine)))) 'of)) (define op car) (define lhs cadr) (define rhs caddr)
(gpa '((cs307 a) (psy301 c))) ==> 3.0
(define (gpa l) (let ((sum 0.0)) (dolist (pair l) (set! sum (+ sum (cadr (assoc (cadr pair) '((a 4.) (b 3.) (c 2.) (d 1.) (f 0.)))))) ) (/ sum (length l)) ))
(pay '((smith 3)) '((jones 4.50) (smith 6.00))) ==> prints: smith 18.0
(define (pay hours rates) (dolist (person hours) (display (car person)) (display " ") (display (* (cadr person) (cadr (assoc (car person) rates)))) (newline) ) )
(total '((clothing jeans 3) (hardware wrench 2)) '((hardware (saw 9.95) (wrench 4.00)) (clothing (socks 2.50) (jeans 19.95)))) ==> 67.85 [remember to multiply by number of items]
(define (total items prices) (define dept car) (define item cadr) (define number caddr) (let ((sum 0)) (dolist (it items) (set! sum (+ sum (* (number it) (cadr (assoc (item it) (cdr (assoc (dept it) prices))))))) ) sum))
(ngreater '(+ (* 88 x) (+ 3 7) (/ 17 z)) 5) ==> 3
(define (ngreater tree m) (if (pair? tree) (+ (ngreater (car tree) m) (ngreater (cdr tree) m)) (if (and (number? tree) (> tree m)) 1 0)))
d/dx(x) = 1 (derivative of x with respect to x is one) d/dx(v) = 0 (derivative of any variable v other than x with respect to x is zero) d/dx(c) = 0 (derivative of a constant is zero) d/dx(u + v) = d/dx(u) + d/dx(v) d/dx(u * v) = u * d/dx(v) + v * d/dx(u)Note that in the last two cases you must make new list structure (a new formula) as the result. Examples:
(deriv 'x 'x) ==> 1 (deriv 'y 'x) ==> 0 (deriv 5 'x) ==> 0 (deriv '(+ x 3) 'x) ==> (+ 1 0) (deriv '(+ (* x 3) 7) 'x) ==> (+ (+ (* x 0) (* 3 1)) 0)
(define (deriv e var) (define lhs cadr) (define rhs caddr) (if (pair? e) (case (car e) ((+) (list '+ (deriv (lhs e) var) (deriv (rhs e) var))) ((*) (list '+ (list '* (lhs e) (deriv (rhs e) var)) (list '* (rhs e) (deriv (lhs e) var)))) ) (if (eqv? e var) 1 0)))
(english 'x) ==> (x) (english '(+ x 7)) ==> (the sum of x and 7) (english '(if (= (+ i j) 3) (set! k 7))) ==> (if the sum of i and j equals 3 then set k to 7)
(define (english code) (define lhs cadr) (define rhs caddr) (if (pair? code) (case (car code) ((+ - * /) (append (list 'the (opword (car code)) 'of) (english (lhs code)) '(and) (english (rhs code))) ) ((=) (append (english (lhs code)) '(equals) (english (rhs code)))) ((if) (append '(if) (english (lhs code)) '(then) (english (rhs code)) (if (null? (cdddr code)) '() (append '(else) (english (cadddr code)))))) ((set!) (append (list 'set (lhs code) 'to) (english (rhs code))))) (list code))) (define (opword op) (cadr (assoc op '((+ sum) (* product) (- difference) (/ quotient)))))
(deep-reverse '(((a b) c) d)) ==> (d (c (b a)))
(define (deep-reverse l) (deep-rev l '())) (define (deep-rev l result) (if (pair? l) (deep-rev (cdr l) (cons (deep-reverse (car l)) result)) (if (null? l) result l) ) )
(define (deep-reverse l) (if (pair? l) (let ((answer '())) (dolist (x l answer) (set! answer (cons (deep-reverse x) answer)) )) l))
The complement of a DNA sequence is a sequence of the complementary letters (A-T, C-G) of the given sequence. Write a function (complement dna) to compute the complement of a given string. Use auxiliary functions if you wish. Example:
(complement '(a a a g t g c)) ==> (t t t c a c g)
(define (complement lst) ; the easiest solution (sublis '((a . t) (t . a) (c . g) (g . c)) lst))
(define (complement lst) (reverse (complementb lst '()))) (define (complementb lst result) (if (pair? lst) (complementb (cdr lst) (cons (opposite (car lst)) result)) result)) (define (opposite base) (cdr (assoc base '((a . t) (t . a) (c . g) (g . c)) )))
(protein '(a a a g t g a t a) codes) = (Phe His Tyr)
(define (protein dna codes) (if (pair? dna) (cons (cadr (assoc (list (car dna) (cadr dna) (caddr dna)) codes)) (protein (cdddr dna) codes)) '()))
(define (protein dna codes) (proteinb dna codes '())) (define (proteinb dna codes result) (if (and (pair? dna) (pair? (cdr dna)) (pair? (cddr dna))) (proteinb (cdddr dna) codes (cons (cadr (assoc (list (car dna) (cadr dna) (caddr dna)) codes)) result)) (reverse result)))
(restrict '(g t g a a a g t g a t a) '(t g a)) = (1 7) ----- ----- 0 1 2 3 4 5 6 7 8 9 10
(define (restrict dna enzyme) (restrictb dna enzyme 0 '())) (define (restrictb dna enzyme position result) (if (pair? dna) (restrictb (cdr dna) enzyme (1+ position) (if (matchenz dna enzyme) (cons position result) result)) (reverse result))) (define (matchenz dna enzyme) ; does enzyme match front of dna? (if (pair? enzyme) (if (pair? dna) (if (eq? (car dna) (car enzyme)) (matchenz (cdr dna) (cdr enzyme)) #f) #f) #t)) (define (matchenz dna enzyme) ; 2nd version (or (null? enzyme) (and (pair? dna) (eq? (car dna) (car enzyme)) (matchenz (cdr dna) (cdr enzyme)))))
Example: (dnamatch '(a a a g t g c) '(t g c g t g)) = 4 0 1 2 3 4 5 6 -----(The sequence t g c matches beginning at position 4.)
(define (dnamatch one two) (dnamatchb one two 0)) (define (dnamatchb one two n) (if (pair? one) (if (matchfront one two) n (dnamatchb (cdr one) two (1+ n))) #f)) ; see if list x matches front of list two. ; (matchfront '(a b c) '(a b c d e)) = #t (define (matchfront x two) (if (pair? x) (and (pair? two) (eq? (car x) (car two)) (matchfront (cdr x) (cdr two))) #t))
Example: (combine '(a a a g t g c) '(t g c g t g)) = (a a a g t g c g t g)
(define (combine one two) (append one (list-tail two (- (length one) (dnamatch one two)))) )
(evalexp '(+ a (* 3 b)) '((a . 7) (b . 8))) = 31
(define (evalexp expr vals) (define op car) (define lhs cadr) (define rhs caddr) (if (pair? expr) (case (op expr) ((+) (+ (evalexp (lhs expr) vals) (evalexp (rhs expr) vals))) ((*) (* (evalexp (lhs expr) vals) (evalexp (rhs expr) vals))) ((/) (/ (evalexp (lhs expr) vals) (evalexp (rhs expr) vals))) ((-) (if (pair? (cddr expr)) (- (evalexp (lhs expr) vals) (evalexp (rhs expr) vals))) (- (evalexp (lhs expr) vals)))) (if (symbol? expr) (cdr (assoc expr vals)) expr)))
(weight '((star ball star) star ball) '((ball . 4) (star . 2))) = 14
(define (weight mobile weights) (define left car) (define center cadr) (define right caddr) (if (pair? mobile) (+ (weight (left mobile) weights) (cdr (assoc (center mobile) weights)) (weight (right mobile) weights)) (cdr (assoc mobile weights))))
(balanced '((star ball star) ball bell) '((ball . 4) (star . 2) (bell . 8))) = #t
(define (balanced mobile weights) (define left car) (define right caddr) (if (pair? mobile) (and (balanced (left mobile) weights) (= (weight (left mobile) weights) (weight (right mobile) weights)) (balanced (right mobile) weights)) #t))
Example: (wlt '((14 7) (10 10) (21 24) (17 7))) = (2 1 1) [2 wins, 1 loss, 1 tie]
(define (wlt scores) (let ((wins 0) (losses 0) (ties 0)) (dolist (game scores) (cond ((> (car game) (cadr game)) (set! wins (1+ wins))) ((< (car game) (cadr game)) (set! losses (1+ losses))) (else (set! ties (1+ ties))))) (list wins losses ties)))
Example: (evens '(a (2 3 4) (b (5 6)))) = 48
(define (evens tree) (if (pair? tree) (* (evens (car tree)) (evens (cdr tree))) (if (and (number? tree) (even? tree)) tree 1)))
Example: (mouse '((#f #f #t) #f (#f #f #f))) = (left right)
(define (mouse maze) (if (pair? maze) (if (mouse (car maze)) (cons 'left (mouse (car maze))) (if (mouse (cadr maze)) (cons 'center (mouse (cadr maze))) (if (mouse (caddr maze)) (cons 'right (mouse (caddr maze))) #f))) (if maze '() #f)))
(pushn n) put the number n onto the front of the stack (pushv v) put the value of the variable v onto stack (add) remove the top two elements from the stack, add them, and put the result back on the stack (mul) multiply (as above)Return the top value on the stack.
Example: (sm '((pushv x) (pushn 7) (mul)) '((x 3))) = 21
(define (sm instructions memory) (let ((stack '())) (dolist (inst instructions) (case (car inst) ((pushv) (set! stack (cons (cadr (assoc (cadr inst) memory)) stack))) ((pushn) (set! stack (cons (cadr inst) stack))) ((add) (set! stack (cons (+ (car stack) (cadr stack)) (cddr stack)))) ((mul) (set! stack (cons (* (car stack) (cadr stack)) (cddr stack)))) ) ) (car stack) ))
Example: (code 'x) = ((pushv x)) (code '(+ x 3)) = ((pushv x) (pushn 3) (add)) (code '(* a (+ b 3))) = ((pushv a) (pushv b) (pushn 3) (add) (mul))
(define (code e) (reverse (codeb e '()))) (define (codeb e lst) (if (pair? e) (cons (cdr (assoc (car e) '((+ add) (* mul)))) (codeb (caddr e) (codeb (cadr e) lst))) (cons (if (symbol? e) (list 'pushv e) (list 'pushn e)) lst)))
Example: (backchain 'a '() '((a #t))) = #t (backchain 'a '((a b)) '((b #t))) = #t (backchain 'a '((a b c) (c d)) '((b #t) (d #t))) = #t [the rules are "a is true if b and c are true", "c is true if d is true"]
(define (backchain goal rules facts) (if (assoc goal facts) (cadr (assoc goal facts)) (some (lambda (rule) (and (eq? (car rule) goal) (every (lambda (subgoal) (backchain subgoal rules facts)) (cdr rule)))) rules)) )
(ship '((widgets 2) (gizmos 7) (thingies 14)) '((thingies 12) (widgets 5) (grommets 3))) => ((widgets 2) (thingies 12))
(define (ship order inventory) (if (pair? order) (let ((inv (assoc (caar order) inventory))) (if inv (cons (list (caar order) (min (cadar order) (cadr inv))) (ship (cdr order) inventory)) (ship (cdr order) inventory))) '()))
(limit '((9 to (5)) (spirit (of 76))) 7) => ((7 to (5)) (spirit (of 7)))
(define (limit tree m) (if (pair? tree) (cons (limit (car tree) m) (limit (cdr tree) m)) (if (number? tree) (min m tree) tree)))
(encrypt '(* (+ (/ a b) c) (- d (+ e f))) '(1 0 1)) => (* (- d (+ f e)) (+ (/ b a) c))
(define op car) (define lhs cadr) (define rhs caddr) (define (encrypt formula keylist) (if (pair? formula) (if (zero? (car keylist)) (list (op formula) (encrypt (lhs formula) (cdr keylist)) (encrypt (rhs formula) (cdr keylist))) (list (op formula) (encrypt (rhs formula) (cdr keylist)) (encrypt (lhs formula) (cdr keylist)))) formula))
(starmatch '(i feel * today) '(i feel wild and crazy today)) => (wild and crazy)
(define (starmatch pattern input) (if (pair? pattern) (if (eq? (car pattern) '*) (starmatchb (cdr pattern) '() input) (and (pair? input) (eq? (car pattern) (car input)) (starmatch (cdr pattern) (cdr input)))) (if (null? input) '() #f))) (define (starmatchb pattern ans input) (if (equal? pattern input) (reverse ans) (if (pair? input) (starmatchb pattern (cons (car input) ans) (cdr input)) #f)))
(doctor '(i argued with my mother today) '( ... ((i argued with * today) (what did * say))...) ) => (what did your mother say)
(define (doctor input patterns) (let ((pat (some (lambda (pair) (and (starmatch (car pair) input) pair)) patterns))) (if pat (splice (sublis '((i . you) (my . your) (myself . yourself)) (starmatch (car pat) input)) (cadr pat)) '(tell me more)) )) (define (splice new pattern) (if (pair? pattern) (if (eq? (car pattern) '*) (append new (cdr pattern)) (cons (car pattern) (splice new (cdr pattern)))) '()))
(failure '(a (b #t #t) (d (e #f #f) (f #t #f)))) => d
(define (failure tree) (if (pair? tree) (if (or (eq? (lhs tree) #f) (eq? (rhs tree) #f) (and (failure (lhs tree)) (failure (rhs tree)))) (car tree) (or (failure (lhs tree)) (failure (rhs tree)))) #f))
(prize '(20 (10 5) (20 (10 100) 50) (20 40)) 45) => 50
(define (prize cave rope) (if (pair? cave) (if (>= rope (car cave)) (let ((best 0)) (dolist (sub (cdr cave) best) (set! best (max best (prize sub (- rope (car cave))))))) 0) cave))
This elegant solution was suggested by a student:
(define (prize cave rope) (if (pair? cave) (if (>= rope (car cave)) (apply max (map (lambda (sub) (prize sub (- rope (car cave)))) (cdr cave))) 0) cave))
(check '((name john) (age 27) (sex m) (major cs)) '(and (= sex 'm) (> age 21)) ) => #t
This function is similar to the version of eval in the class notes.
(define (check relation test) (if (pair? test) (case (car test) ((quote) (cadr test)) ((and) (and (check relation (lhs test)) (check relation (rhs test)))) ((or) (or (check relation (lhs test)) (check relation (rhs test)))) ((not) (not (check relation (lhs test)))) ((=) (equal? (check relation (lhs test)) (check relation (rhs test)))) ((>) (> (check relation (lhs test)) (check relation (rhs test)))) (else #f)) (if (symbol? test) (cadr (assoc test relation)) test)))
(query '(((name john) (sex m)) ((name jill) (sex f))) '(= sex 'f)) => (((name jill) (sex f)))
(define (query database test) (subset (lambda (x) (check x test)) database))
(deep-assoc 'cat '((rat mouse shrew) (dog cat) (horse pig cow))) => (dog cat)
(define (deep-assoc item lists) (if (pair? lists) (if (member item (car lists)) (car lists) (deep-assoc item (cdr lists))) #f))
(paraphrase '(my love is like a red rose) '((scarlet crimson red) (flower rose posy) (love mate))) => (my love is like a scarlet posy)
(define (paraword word synonyms) (let ((lst (deep-assoc word synonyms))) (if lst (list-ref lst (random (length lst))) word))) (define (paraphrase sentence synonyms) (map (lambda (x) (paraword x synonyms)) sentence))
(sanitize '((guns toys) (dynamite candy-canes) (grenades lemons)) '(send (6 dynamite) and 12 grenades)) => (send (6 candy-canes) and 12 lemons)
This is basically sublis with lists rather than dotted pairs.
(define (sanitize alist tree) (if (pair? tree) (cons (sanitize alist (car tree)) (sanitize alist (cdr tree))) (let ((pair (assoc tree alist))) (if pair (cadr pair) tree) ) ))
(half-list '(a b c d e)) => (a c e)
(define (half-list lst) (if (pair? lst) (cons (car lst) (half-list (if (pair? (cdr lst)) (cddr lst) '()))) '()))
(shuffle '(a b c d e f g h)) => (b a c e d f h g)
(define (shuffle lst) (if (pair? lst) (shuffleb (half-list lst) (half-list (cdr lst))) '())) (define (shuffleb one two) (if (pair? one) (if (pair? two) (if (zero? (random 2)) (cons (car one) (shuffleb (cdr one) two)) (cons (car two) (shuffleb one (cdr two)))) one) two))
(trip 250 '(austin 0 200 ((waco 100 20 ((college-station 40 -100 ()) (dallas 120 200 ())))))) => ((austin waco dallas) 420)
(define city car) (define miles cadr) (define value caddr) (define destinations cadddr) ; This is a tree search. ; Base case: not enough mileage to reach the current city; ; return an empty list of cities and 0 points. ; Recursive case: subtract the miles for this city from the mileage, ; then find the best trip from this city. ; Return a list of: cons this city onto that trip, ; add points for this city to that trip's points. (define (trip mileage tree) (let ((best (list '() 0)) (new #f)) (if (< mileage (miles tree)) best (dolist (d (destinations tree) (list (cons (city tree) (car best)) (+ (cadr best) (value tree)))) (set! new (trip (- mileage (miles tree)) d)) (if (> (cadr new) (cadr best)) (set! best new))))))
public static double average( double[] arr ) { double sum = 0.0; int n = 0; for ( int i=0; i < arr.length; i++ ) { sum = sum + arr[i]; n++; }; return ( sum / (double) n ); }
A program similar to this is given in the lecture notes.
Note that this is the same as the length function: although the company structure is a tree structure, each employee object can be thought of as a list of the employee, the employee's boss, etc., terminating in the president. The level of the employee is the length of this list. Following the definition of the length function as given in the file Cons.java, we could write:
public static int level(Employee lst) { int n = 0; while ( lst != null ) { n++; lst = lst.boss(); } return n; }
(set! x (vector-ref v i)) x = v[i];
(if (> i 7) (set! j (+ j 1))) if (i > 7) j++;
(while (< i 3) (display i) (set! i (1+ i))) while (i < 3) { System.out.print(i); i++; }
(dotimes (i 7) (set! sum (+ sum (vector-ref v i)))) for (i = 0; i < 7; i++) sum = sum + v[i];
(set! y (* 8 (sin x))) y = 8 * Math.sin(x);
(set! x (+ y 2)) x = y + 2;
(set! y (* (exp (- x)) (sin x))) y = Math.exp(- x) * Math.sin(x);
(dotimes (j 3) (vector-set! v j 0.0)) for (j = 0; j < 3; j++) v[j] = 0.0;
(while (< i 7) (set! i (+ i 1))) while (i < 7) i = i + 1;
(if (> i 3) (display (vector-ref x i))) if (i > 3) System.out.print(x[i]);