Write the following recursive Scheme programs. Place them in a file called a1.scm and submit it to Vincent. All solutions must be recursive or credit will not be given. You may not use built-in functions that handle the bulk of the work. All brainteasers are optional.
increment that takes a list of numbers and returns a new list whose elements are equal to the elements of the original list incremented by one.
(increment '(1 2 3 4 5)) => (2 3 4 5 6)
insertl that takes as input two symbols and a list, and inserts the second symbol before each occurrence in the list of the first symbol.
(insertl 'x 'y '(x z z x y x)) => (y x z z y x y y x)
last-eq? that takes a symbol and a non-empty list and returns the result of the comparison between the symbol and the last element of that list.
(last-eq? 'f '(a b c d e f)) => #t
remove that takes a symbol and a list, and returns a new list with the same elements as the original list, but with all instances of the input symbol removed.
(remove 'x '(z x y x y z)) => (z y y z)
count-between that takes two integers m and n where m < n and returns a list counting up from m to n, including m but not including n.
(count-between 2 5) => (2 3 4)
occurs that takes as input a symbol and a list, and returns the number of times the symbol occurs in the list.
(occurs 'x '(x y z x x)) => 3
filter that takes a predicate and a list, and returns a new list containing the elements that satisfy the predicate. A predicate is a function that takes a single input and returns either #t or #f. number?, for example, returns #t if the input is a number and #f otherwise. The input satisfies the predicate, then, if the predicate returns #t for that input.
(filter even? '(1 2 3 4 5 6)) => (2 4 6)
zip that takes two lists of equal length and forms a new list, each element of which is the two-element list formed by combining the corresponding elements of the two input lists.
(zip '(1 2 3) '(a b c)) => ((1 a) (2 b) (3 c))
function sum-to that takes an integer and sums the integers from one to the input number.
(sum-to 4) => 10
map that takes a procedure p of one argument and a list ls, and returns a new list containing the results of applying p to the elements of ls. Do not use Scheme's built-in map in your definition.
(map add1 '(1 2 3 4)) => (2 3 4 5)
append that takes two lists, ls1 and ls2, and appends ls2 to ls1.
(append '(a b c) '(1 2 3)) => (a b c 1 2 3)
reverse that takes a list and returns the reverse of that list.
(reverse '(a 3 x)) => (x 3 a)
fact that takes a single integer and computes the factorial of that number. The factorial of a number is computed by multiplying it by every positive integer less than it.
(fact 5) => 120
count-symbols that takes a (potentially deep) list of symbols, and returns the number of symbols in the list.
(count-symbols '(a b c)) => 3
(count-symbols '((a ((b)) ((c) d c)))) => 5
fib that takes a single integer n as input and computes the nth number, starting from zero, in the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, 21, ...). Each number in the sequence is computed by adding the two previous numbers.
(fib 0) => 0
(fib 1) => 1
(fib 7) => 13
even-layers? and odd-layers? that take an onion of the form (((...))). even-layers? should return #t if the onion has an even number of layers and #f otherwise, and odd-layers? should return #t if the input has odd number of layers and #f otherwise. The onion () has zero layers.
(even-layers? '()) => #t
(even-layers? '(())) => #f
(odd-layers? '(((((((((((())))))))))))) => #t
(even-layers? '(((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))) => #f
Brainteaser 1: write another variant of the fib
function, fib-acc, that is not doubly recursive
(hint: this function should take three arguments).
Brainteaser 2: Package your assignment as an R6RS library. Your code must load and run under Ikarus Scheme.