This may be a short assignment in terms of lines of code involved, but because you may not have experience with functional programming, it may demand more thinking time.

The functions described below should be written using MCL. You should drop off an electronic copy of your solutions inside the drop folder in the CS251 folder on the CS file server on Celeste. In addition, hand in a hard copy of your code, along with sample runs of your functions that demonstrate that they work correctly (you can print the contents of the Lisp Listener window). Make sure you have tested your functions thoroughly. Please document your code so that it is clear what it does. In addition to the specific functions requested, you may, in some cases, want to write an additional auxiliary function of some sort.

Problem 1. Write a function (insert x L) that inserts x into L, assuming that L is an ordered list of atoms (ordered by the comparison function < ) and that x is an atom.

? (insert 4 '(2 3 6 7))

(2 3 4 6 7)

? (insert 4 '())

(4)

Problem 2. Write a function (insertsort L) that assumes that L is a list of atoms and sorts it using the insert function from the previous problem.

? (insertsort '(3 5 2 7 1))

(1 2 3 5 7)

Problem 3. Write a function (mymerge L1 L2) that assumes that L1 and L2 are sorted lists and merges them into one sorted list.

? (mymerge '(1 3 5 6) '(2 3))

(1 2 3 3 5 6)

Problem 4. Write a function (mergesort L) that mergesorts list L using the mymerge function from the previous problem.

? (mergesort '(3 2 6 1 34 6 0))

(0 1 2 3 6 6 34)

Problem 5. Write a function (occurs a S) that counts the number of times that the atom a appears in a given S-expression S.

? (occurs 2 '(3 2 5 1 2 4 2))

3

? (occurs 'a '(s a (a) a (b a)))

4

? (occurs 'a '(s (((a))) a))

2

Problem 6. Write a function (atomlist S) to make a list without duplicates of S-expression S.

? (atomlist '(a s f a d s a a a s))

(F D A S NIL)

? (atomlist '(s a (a) a (b a)))

(S B A NIL)