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. The brainteaser is extra credit and is not required; extra credit will not be given unless all normal problem definitions show substantial effort.

1. Define a function 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)

2. Define a function 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)

3. Define a function 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

4. Define a function 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)

5. Define a function 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)

6. Define a function 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

7. Define a function 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)

8. Define a function 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))

9. Define a function sum-to that takes an integer and sums the integers from one to the input number.

   (sum-to 4) => 10

10. Define a function mapit 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.

    (mapit add1 '(1 2 3 4)) => (2 3 4 5)

11. Define a function 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)

12. Define a function reverse that takes a list and returns the reverse of that list.

    (reverse '(a 3 x)) => (x 3 a)

13. Define a function 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

14. Define a function 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

15. Define two functions even? and odd? that are mutually recursive; even? should return #t if the input is even and #f otherwise, and odd? should return #t if the input is odd and #f otherwise.

    (even? 3) => #f

    (even? 4) => #t

    (odd? 3) => #t

16. Brainteaser: write another variant of the fib function, fib-acc, that is not doubly recursive (hint: this function should take three arguments).

17. Extra Credit for R6RS h4x0rz: Package your assignment as an R6RS library. Your code must load and run under Ikarus Scheme.