Write the function (factorial n), which takes a number n as input and returns the factorial of n. The factorial of n is written n! and is the product of n × n-1 × n-2 × ... × 3 × 2 × 1. In other words, the factorial of n is equal to n times the factorial of n-1. By definition, the factorial of 0 is 1. Examples:
(factorial 0) → 1 (factorial 4) → 24 (factorial 5) → 120 (factorial 10) → 3628800
Write the function (power base exponent), which raises the number base to the power of exponent. By definition, any base raised to the power of 0 is 1. You are not allowed to use Scheme's expt function for this exercise. Examples:
(power 2 0) → 1 (power 2 5) → 32 (power 10 3) → 1000 (power 4 1) → 4 (power 3 5) → 243
Write the function (laugh n), which takes a number n and constructs a list containing n ha symbols. Examples:
(laugh 0) → () (laugh 4) → (ha ha ha ha) (laugh 1) → (ha)
Write the function (copies n x), which takes a number n and an item x and constructs a list containing n copies of x. Examples:
(copies 4 'practice) → (practice practice practice practice) (copies 3 '(heh)) → ((heh) (heh) (heh)) (copies 1 42) → (42) (copies 0 'whatever) → ()
Write the function (range start end), which takes two numbers start and end as input, and returns a new list of numbers in sequence from start to end. If start > end, then an empty list is returned. Examples:
(range 1 8) → (1 2 3 4 5 6 7 8) (range 2 8) → (2 3 4 5 6 7 8) (range 8 8) → (8) (range 9 8) → ()
Write the function (wrap n x), which takes a number n and an item x and wraps n sets of parentheses around x. Examples:
(wrap 0 'banana) → banana (wrap 1 'surprise) → (surprise) (wrap 3 'apple) → (((apple)))
Write the function (count-all ls), which takes a list and counts all of the elements in the list. Examples:
(count-all '(apple banana cherry) → 3 (count-all '(nine 90 9 90 nine)) → 5 (count-all '(a rose is a rose is a rose)) → 8 (count-all '()) → 0
Write the function (count sym ls), which takes a symbol sym and a list of symbols ls and returns the number of times sym appears in ls. Examples:
(count 'yes '(oh yes yes yes)) → 3 (count 'yes '(oh no no no)) → 0 (count 'rose '(a rose is a rose is a rose)) → 3 (count 'is '(a rose is a rose is a rose)) → 2 (count 'whatever '()) → 0
Write the function (replace-last sym ls), which takes a symbol and a list of symbols as input, and returns a new list with the last symbol in the list replaced by the input symbol. As a special case, if the list is empty, the empty list should be returned. Examples:
(replace-last 'water '(we all scream for ice cream)) → (we all scream for ice water) (replace-last 'gold '(silver)) → (gold) (replace-last 'frog '(red fish blue fish)) → (red fish blue frog) (replace-last 'water '()) → ()
Write the function (remove-odds nums), which takes a list of numbers and returns a new list with all of the odd numbers removed. Hint: use the function multirember from The Little Schemer as a model (but not as a helper function). You can use the built-in function odd? to test if a number is odd. Examples:
(remove-odds '(1 2 3 4 5 9)) → (2 4) (remove-odds '(2 4 6)) → (2 4 6) (remove-odds '(1 3 5)) → ()
Write the function (x-odds nums), which takes a list of numbers and returns a new list with all of the odd numbers replaced by the literal symbol x. Hint: use the function multisubst from The Little Schemer as a model (but not as a helper function). You can use the built-in function odd? to test if a number is odd. Examples:
(x-odds '(1 2 3 4 5 9)) → (x 2 x 4 x x) (x-odds '(2 4 6)) → (2 4 6) (x-odds '(1 3 5)) → (x x x)
Write the function (keep-odds nums), which takes a list of numbers and returns a new list containing just the odd numbers. You can use the built-in function odd? to test if a number is odd. Examples:
(keep-odds '(0 1 2 3 4 5 6 7 8)) → (1 3 5 7) (keep-odds '(2 4 6 8)) → () (keep-odds '(3 5 7 8)) → (3 5 7)
Write the function (classify-nums nums), which takes a list of numbers and returns a new list with all odd numbers replaced by the symbol odd and all even numbers replaced by the symbol even. You can use the built-in functions odd? and even? to test if a number is odd or even. Example:
(classify-nums '(1 2 3 5 4)) → (odd even odd odd even) (classify-nums '(0)) → (even) (classify-nums '(1 3 5)) → (odd odd odd)
Write the function (times-ten nums), which takes a list of numbers and returns a new list with each number multiplied by 10. Examples:
(times-ten '(1 2 3 4 5)) → (10 20 30 40 50) (times-ten '(25)) → (250)
Write the function (times-all n nums), which takes a number n and a list of numbers and returns a new list with each number multiplied by n. Examples:
(times-all 10 '(1 2 3 4 5)) → (10 20 30 40 50) (times-all 2 '(1 2 3 4 5)) → (2 4 6 8 10) (times-all 3 '(25)) → (75)
Write the function (flip ls), which takes a list ls and returns a new list with the elements in reverse order. You are not allowed to use Scheme's built-in reverse function for this problem, but you may define and use snoc as a helper function. Examples:
(flip '()) → () (flip '(a b c d e f g)) → (g f e d c b a)
Write the function (concat ls1 ls2), which takes two lists ls1 and ls2 and returns the concatenation of the lists, namely a new list containing all of the elements of ls1 followed by all of the elements of ls2, in their original order. You are not allowed to use Scheme's built-in append function for this problem. Examples:
(concat '() '(w x y z)) → (w x y z) (concat '(a b c d) '()) → (a b c d) (concat '(a b c d) '(w x y z)) → (a b c d w x y z) (concat '(1 2 3) '(four five six seven)) → (1 2 3 four five six seven)
Write the function (biggest nums), which takes a non-empty list of numbers and returns the biggest number in the list. Hint: if the list has only one element, then just return that element. Otherwise, if the first element is bigger than the biggest remaining element, return the first element. If not, return the biggest remaining element. Examples:
(biggest '(9 1 5 3 2 2 7 1 4)) → 9 (biggest '(6 0 4 3 12 1 9)) → 12 (biggest '(5)) → 5
Write the function (double sym ls), which takes a symbol sym and a list ls and "doubles" all of the sym's in ls. Examples:
(double 'hot '()) → () (double 'hot '(texas hot chili)) → (texas hot hot chili) (double 'fish '(one fish two fish)) → (one fish fish two fish fish) (double 'double '(double toil and trouble)) → (double double toil and trouble)
Write the function (remove-duplicates ls), which takes a list ls of symbols and removes all of the duplicate elements. The ordering of elements in the resulting list does not matter. Hint: define and use member? as a helper function. Examples:
(remove-duplicates '(a b c c b d)) → (a b c d) (remove-duplicates '(a a a a)) → (a) (remove-duplicates '(a b a b b b a)) → (a b) (remove-duplicates '(x y z)) → (x y z)
Write the function (swap sym1 sym2 ls), which swaps all occurrences of the symbols sym1 and sym2 within a list ls of symbols. Examples:
(swap 'red 'blue '(red fish blue fish)) → (blue fish red fish) (swap 'orange 'blue '(red fish blue fish)) → (red fish orange fish) (swap 'blue 'orange '(red fish blue fish)) → (red fish orange fish) (swap 'spam 'ham '(green eggs and ham)) → (green eggs and spam) (swap 'eggs 'ham '(green eggs and ham and eggs)) → (green ham and eggs and ham)
Write the function (add-lists nums1 nums2), which takes two lists of numbers, which you may assume will always be of the same length, and returns a new list containing the sums of the numbers in corresponding positions in the input lists. Examples:
(add-lists '(1 2 3) '(10 10 10)) → (11 12 13) (add-lists '(1 2 3 4 5) '(10 15 20 25 30)) → (11 17 23 29 35) (add-lists '(6 7) '(2 2)) → (8 9) (add-lists '(9) '(0)) → (9) (add-lists '() '()) → ()
Write the function (add-lists2 nums1 nums2), which is just like add-lists, except that the input lists are not required to be the same length. Any numbers left over from the longer of the two input lists are included as-is in the answer list. Examples:
(add-lists2 '(1 2 3) '(10 10 10)) → (11 12 13) (add-lists2 '(1 2 3) '(10 10 10 10 10)) → (11 12 13 10 10) (add-lists2 '(1 2 3) '(10)) → (11 2 3) (add-lists2 '(5) '(1 2 3 4)) → (6 2 3 4) (add-lists2 '() '(1 2 3)) → (1 2 3)
Write the function (every-other ls), which takes a list ls and returns a list containing every other element, starting with the first element. Hint: this problem has more than one base case. Examples:
(every-other '(a b c d e f)) → (a c e) (every-other '(b c d e f))) → (b d f) (every-other '(a b)) → (a) (every-other '(x)) → (x)
Write the function (increasing-order? nums), which takes a list of numbers and returns #t if all numbers in the list are in increasing order from left to right, or #f otherwise. Adjacent numbers that are equal should be considered to be in "increasing" order. Examples:
(increasing-order? '(1 2 3 4 7 9)) → #t (increasing-order? '(1 1 1 5 5 8)) → #t (increasing-order? '(7 9 8 10 12)) → #f
Write the function (firsts lists), which takes a list of lists, each of which contains exactly two items, and returns a new list consisting of the first item from each list in lists. Examples:
(firsts '((paella spanish) (wine red) (and beans))) → (paella wine and) (firsts '()) → () (firsts '((red hot) (chili dogs))) → (red chili)
Write the function (seconds lists), which takes a list of lists, each of which contains exactly two items, and returns a new list consisting of the second item from each list in lists. Examples:
(seconds '((paella spanish) (wine red) (and beans))) → (spanish red beans) (seconds '()) → () (seconds '((red hot) (chili dogs))) → (hot dogs)
Write the function (pair-up a set), which takes an element a and a set (a list containing no duplicate elements), and returns a new list consisting of a paired up with each element of set, where each "pair" is a list. Examples:
(pair-up 'x '(a b c d)) → ((x a) (x b) (x c) (x d)) (pair-up 'fish '(one two three)) → ((fish one) (fish two) (fish three)) (pair-up 'hee '(hee)) → ((hee hee))
Write the function (cross-product set1 set2), which takes two sets (lists containing no duplicates) and returns all elements from set1 paired up with all elements from set2. Hints: use pair-up as a helper function. Scheme's built-in append function may also be useful, which does the same thing as concat. Examples:
(cross-product '(a b c) '(1 2)) → ((a 1) (a 2) (b 1) (b 2) (c 1) (c 2)) (cross-product '(a b c) '()) → () (cross-product '() '(a b c)) → ()
Write the function (zip ls1 ls2), which takes two lists of the same length and forms a new list by combining the corresponding elements of ls1 and ls2 into "pairs". Examples:
(zip '(1 2 3) '(a b c)) → ((1 a) (2 b) (3 c)) (zip '(a) '(b)) → ((a b))
Write the function (insert num ls), which takes a number num and a list of numbers already in order from smallest to largest, and returns a new list with num inserted in the correct position. Examples:
(insert 6 '(1 2 3 4 5 7 8)) → (1 2 3 4 5 6 7 8) (insert 2 '(7 9 15)) → (2 7 9 15) (insert 20 '(7 9 15)) → (7 9 15 20)
Using insert as a helper function, write the function (sort-nums nums), which takes an unsorted list of numbers and returns a new list in sorted order. Examples:
(sort-nums '(7 4 6 2 1 9 4)) → (1 2 4 4 6 7 9) (sort-nums '(3 3 3 2 2 1)) → (1 2 2 3 3 3)
Write the function (merge-nums nums1 nums2), which takes two lists of numbers already in sorted order and returns a new list containing all of the numbers in order. Hint: use insert as a helper. Examples:
(merge-nums '(1 4) '(1 2 8)) → (1 1 2 4 8) (merge-nums '(2 6 7 8 9) '(3 4 7 9)) → (2 3 4 6 7 7 8 9 9)
Write the function (wrap-all ls), which takes a list ls and wraps a pair of parentheses around each top-level element of ls. Examples:
(wrap-all '(1 2 3)) → ((1) (2) (3)) (wrap-all '((a) (fine) (idea))) → (((a)) ((fine)) ((idea))) (wrap-all '(a (more (complicated)) object)) → ((a) ((more (complicated))) (object))
Write function (unwrap-all ls), which takes a list ls and removes a pair of parentheses from around each top-level element of ls. If a top-level element is not a list, it should be included in the result as-is. The built-in function list? can be used to test if an object is a list. Note: (unwrap-all (wrap-all ls)) is equivalent to ls, but (wrap-all (unwrap-all ls)) is not necessarily the same as ls. Examples:
(unwrap-all '((1 2) (3 4) 5)) → (1 2 3 4 5) (unwrap-all '((x (y)) z)) → (x (y) z) (unwrap-all '(() a 2 (()) ())) → (a 2 ())
Write the function (cons-code nums), which takes a flat list of numbers and returns a piece of Scheme code consisting of the appropriate cons operations needed to construct nums. You may assume that nums will contain at least one number. Don't forget to quote the empty list in your constructed code! Examples:
(cons-code '(1 2 3)) → (cons 1 (cons 2 (cons 3 '()))) (cons-code '(5)) → (cons 5 '()) (cons-code '(7 8)) → (cons 7 (cons 8 '())) (cons-code '(7 3 3 3)) → (cons 7 (cons 3 (cons 3 (cons 3 '()))))
Write the function (car-cdr-code sym ls), which takes a symbol sym and a flat list ls, and returns a piece of Scheme code consisting of the appropriate combination of car and cdr operations on ls needed to retrieve the first occurrence of sym from ls. You may assume that sym appears somewhere in ls. Hint: define a helper function that constructs the cdr's separately. Examples:
(car-cdr-code 'a '(a b c d e)) → (car ls) (car-cdr-code 'b '(a b c b b b)) → (car (cdr ls)) (car-cdr-code 'c '(a b c d e)) → (car (cdr (cdr ls))) (car-cdr-code 'd '(a b c d e)) → (car (cdr (cdr (cdr ls))))
Write the function (addup-numbers* ls), which takes an arbitrarily-nested list containing numbers and symbols, and adds up all of the numbers in the list, ignoring any symbols that may be present. Examples:
(addup-numbers* '(a b c 1 d e 2 3 4 f g 5 h)) → 15 (addup-numbers* '(1 (a 2) b (3 (c (4))) (d 5) e)) → 15 (addup-numbers* '(((apple 40) 30) (20 10))) → 100 (addup-numbers* '(w (x (y (z))))) → 0 (addup-numbers* '(20 x y (z (20)) 10)) → 50 (addup-numbers* '((((2 (4) (()) (6 8)))))) → 20
Write the function (times-ten* nums), which takes an arbitrarily-nested list of numbers and returns a new list with the same structure, but with each number multiplied by 10. Examples:
(times-ten* '(1 2 3)) → (10 20 30) (times-ten* '(1 (2 3) 4 (5))) → (10 (20 30) 40 (50)) (times-ten* '((7 7 7) (1) ((2)) (3))) → ((70 70 70) (10) ((20)) (30)) (times-ten* '(((9 (8 (7 6 5) 4) 3) 2) 1)) → (((90 (80 (70 60 50) 40) 30) 20) 10) (times-ten* '(((25)))) → (((250)))
Write the function (double* sym ls), which takes a symbol sym and an arbitrarily-nested list ls and "doubles" all of the sym's in ls. Examples:
(double* 'hot '()) → () (double* 'hot '(texas (hot chili))) → (texas (hot hot chili)) (double* 'fish '(one (fish (two (fish))))) → (one (fish fish (two (fish fish)))) (double* 'double '(((double)) (toil) and (((trouble))))) → (((double double)) (toil) and (((trouble)))) (double* 'a '(a 1 (and a 2) ((and ((a 3)))) and (a) 4)) → (a a 1 (and a a 2) ((and ((a a 3)))) and (a a) 4)
Write the function (swap* sym1 sym2 ls), which swaps all occurrences of the symbols sym1 and sym2 within an arbitrarily-nested list of symbols. Examples:
(swap* 'red 'blue '((red fish) (blue) fish)) → ((blue fish) (red) fish) (swap* 'orange 'blue '((red (fish (blue (fish)))))) → ((red (fish (orange (fish))))) (swap* 'blue 'orange '(red (((fish blue))) fish)) → (red (((fish orange))) fish) (swap* 'spam 'ham '((((green) eggs) and) ham)) → ((((green) eggs) and) spam) (swap* 'eggs 'ham '((green) (eggs) and (ham) (and (eggs)))) → ((green) (ham) and (eggs) (and (ham)))
Write the function (flatten ls), which takes an arbitrarily-nested list containing numbers and symbols, and returns a flat version of the list, with all of the elements in their original order, but without any internal parentheses. Hint: the append function will be helpful. Examples:
(flatten '()) → () (flatten '(1 (a 2) b (3 (c (4))) (d 5) e)) → (1 a 2 b 3 c 4 d 5 e) (flatten '(((apple 40) 30) (20 10))) → (apple 40 30 20 10) (flatten '(w (x (y (z))))) → (w x y z) (flatten '((((2 (4) (()) (6 8)))))) → (2 4 6 8)
Write the function (x-ray ls), which takes an arbitrarily-nested list and returns a new version of it with the same internal structure, but with all elements replaced by x's. Examples:
(x-ray '()) → () (x-ray '(1 (a 2) b (3 (c (4))) (d 5) e)) → (x (x x) x (x (x (x))) (x x) x) (x-ray '(((apple 40) 30) (20 10))) → (((x x) x) (x x)) (x-ray '(w (x (y (z))))) → (x (x (x (x)))) (x-ray '((((2 (4) (()) (6 8)))))) → ((((x (x) (()) (x x)))))
Write the function (ns-ray ls), which takes an arbitrarily-nested list and returns a new version of it with the same internal structure, but with all symbols replaced by s's and all numbers replaced by n's. Examples:
(ns-ray '()) → () (ns-ray '(1 (a 2) b (3 (c (4))) (d 5) e)) → (n (s n) s (n (s (n))) (s n) s) (ns-ray '(((apple 40) 30) (20 10))) → (((s n) n) (n n)) (ns-ray '(w (x (y (z))))) → (s (s (s (s)))) (ns-ray '((((2 (4) (()) (6 8)))))) → ((((n (n) (()) (n n)))))
Write the function (skeleton ls), which takes an arbitrarily-nested list and returns a new version of it with the same parentheses structure, but with all symbols and numbers removed. Examples:
(skeleton '()) → () (skeleton '(a b c d)) → () (skeleton '((a b) c d (e))) → (() ())) (skeleton '(1 (a 2) b (3 (c (4))) (d 5) e)) → (() ((())) ()) (skeleton '(((apple 40) 30) (20 10))) → ((()) ()) (skeleton '(w (x (y (z))))) → (((()))) (skeleton '((((2 (4) (()) (6 8)))))) → ((((() (()) ()))))
Write the function (contains-null? ls), which takes an arbitrarily-nested list and returns #t if the list contains an empty list somewhere inside of it, or #f if it does not. Note that an empty list itself does not contain anything. Examples:
(contains-null? '()) → #f (contains-null? '(a b c d)) → #f (contains-null? '((a b) c d ())) → #t (contains-null? '(1 (a 2) b (3 (c ())) (d 5) e)) → #t (contains-null? '(((apple 40) 30) (0))) → #f (contains-null? '(() (x (y (z))))) → #t (contains-null? '((((2 (4) (()) (6 8)))))) → #t