Your program should consist of several functions definitions. One of the functions you should have is one with the name NEXT. Here is an example of using NEXT.

> (next '(1 3 5))
7
> (next '(-2 10 -50))
250
> (next '(0 10 0 11 0 12 0))
13

Another function you should implement is GEN, used as follows:

> (setq f #'(lambda (n) (+ 7 (* n 2))))

> (gen f 10)
(7 9 11 13 15 17 19 21 23 25)

> (findrecog 5 '(10 9 8))

> (gen * 15)
(10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4)

A beta sequence is defined recursively as follows.

• Any arithmetic sequence of integers is a beta sequence. For example 2, 4, 6, ... is a beta sequence.
• Any geometric sequence of integers is a beta sequence. For example 2, 6, 18, 54, ... is a beta sequence.
• Any "interleaved" sequence C made from two beta sequences A and B is a beta sequence. This means that the even-index elements of C (starting with index 0) come from A and the odd-index elements of C come from B. That is, C has the form

  C = (a0, b0, a1, b1, ...)
  where
  A = (a0, a1, a2, ...)
  and
  B = (b0, b1, b2, ...)
  

For up to 5 points of extra credit, implement the following additional function (with any appropriate helper functions): FINDDESC. This function is analogous to findRecog, except that instead of returning a function option, it returns a string. The string describes how the sequence is generated. The description provides three parts: 1. the type of sequence (A.S. = Arithmetic Sequence, G.S. = Geometric Sequence, and I.S. = Interleaved Sequence); 2. a function generating the sequence in the case of A.S. or G.S., and in the case of I.S., a description of the even and odd subsequences (done recursively); and 3. if it is an A.S. or a G.S, then a list showing the first 3 terms of the sequence.

If FINDDESC is not successful in finding the correct description of the sequence within the given search depth, it should return the string "unknown".

You can either use the string notation for sequences suggested in the examples below, or you can use Common Lisp notation for the functions and sequences.

> (next '(3 5 7))
9
> (findDesc 10 '(3 5 7))
"(A.S. f(n)=3+n*2:(3 5 7 ...))"
> (findDesc 10 '(-2  10  -50))
"(G.S. f(n)=-2*(-5)^n:(-2 10 -50 ...))"
> (next '(1  10  2  10))
3
> (findDesc 10 '(1  10  2  10))
"(I.S. of (A.S. f(n)=1+n*1:(1 2 3 ...)) with (A.S. f(n)=10+n*0:(10 10 10 ...)))"
> (next '(1 2 5 43 6))
84
> (findDesc 10 '(1 2 5 43 6))
"(I.S. of (I.S. of (A.S. f(n)=1+n*5:(1 6 11 ...)) with (A.S. f(n)=5: (5 5 5 ...)
)) with (A.S. f(n)=2+n*41:(2 43 84 ...)))"
> (findDesc 2 '(1 2 5 43 6))
"unknown"

Evaluation: Assignment 2 is worth 30 points (not counting extra credit), with 25 for a working program that handles all the test cases and 5 points for style: clear design and implementation, and good comments.

Helpful hints:: 

Breadth-first search is a search technique that searches a tree of possibilities in order of increasing distance from the root. In creating your sequence recognizer, FINDRECOG, you can implement breadth-first search very simply using essentially a depth-first recursive search in which you always check first for the given sequence being arithmetic, second for it being geometric, and only third being an interleaved sequence. Your test for an interleaved sequence should be another function FINDINTERLEAVEDRECOG that also takes two arguments (the same kinds as FINDRECOG) and that calls FINDRECOG on each of the two subsequences obtained by splitting the input list into even and odd-indexed elements. The two functions FINDRECOG and FINDINTERLEAVEDRECOG should be co-recursive; each should have a call to the other within its own definition.

If you need another hint, you can peek at pseudocode for the central functions of the solution.