Problem Set Five, CS 257

1. Define palindrome? which is passed a list and returns true iff that list is a ``palindrome'', ie the first element is equal to the last element, the second is equal to the second-to-last, etc. Eg (palindrome? '(aye bee bee aye)), (palindrome? '(aye)), (palindrome? '()), (palindrome? '((foo bar) (foo bar))) are all true, while (palindrome? '(a y e)), (palindrome? '((foo bar) (bar foo))) are both false.

2. Define a function which takes a list of numbers and returns the ``largest'' number in its argument, where largeness is defined strangely in that any odd number is considered larger than any non-odd number, but otherwise the usual definition of large applies. Eg (largest-prefer-odd-X '(1 3 5 10 12 14 13.5)) yields 5. (Note: only integers can be odd.)

   1. Using recursion: largest-prefer-odd-a

   2. Using higher-order functions: largest-prefer-odd-b

3. Define sort, which takes a binary comparison predicate and a list, and returns a sorted (by the passed predicate) list. Eg (sort < '(2 4 1 3)) yields (1 2 3 4) and (sort > '(2 4 1 3)) yields (4 3 2 1).

   (Extra credit use iota0 and fill-list to make some long lists, and use time to time how long your sort takes on them, and plot the results. Be sure to use lists long enough to give you a significant digit, and repeat your timing tests a couple times to check for consistency. And get enough data points, so we can really see how your code's performance scales.)

4. Define the higher-order function to-leaves which takes a function and an sexpr and returns the same sexpr except each ``leaf'' no matter how deep is replaced by the result of applying the function to it. Eg

   (define add1 (lambda (x) (+ x 1)))
   (to-leaves add1 '(1 (1000 2000) 5))        ; (2 (1001 2001) 6)
   

5. Use to-leaves to define exaggerate, eg (exaggerate '(my 1 foot (no 18 inch) fish)) yields (my 2 foot (no 36 inch) fish).

6. Define ineval which takes an ``infix expression'' of the sort shown below and evaluates it. This ``infix expression'' little language is defined by example - if you have any question about it email me and I'll put the answers below. It has number, binary operators + and *, the unary operator -, and all binding is right-to-left. There is no notion of ``precedence,'' and the - operator is unary only, not binary, and binds right-to-left like everything else

   (ineval '(23))                          ; 23
   (ineval '(1 + 2))                       ; 3
   (ineval '-17)                           ; -17
   (ineval '(1 + 2 * 3))                   ; 7   = 1+(2*3)
   (ineval '(1 * 2 + 3))                   ; 5   = 1*(2+3)
   (ineval '(2 * 2 + 3 * 3))               ; 22  = 2*(2+(3*3))
   (ineval '((1 + 1) * (2 + 2)))           ; 8
   (ineval '(1 + (2 * 2 * 2) + 1000))      ; 1009
   (ineval '(- 1000))                      ; -1000
   (ineval '(- 1 + 17))                    ; -18   = -(1+17)
   (ineval '(10 + - 1 + 1))                ; 8     = 10+-(1+1)
   (ineval '(10 + (- 1 + 1) + 1000))       ; 1008  = 10+-(1+1)+1000
   (ineval '(2 * - 3 + 4))                 ; -14
   ;;; These are examples of malformed ineval expressions - you do not
   ;;; have to handle them.
   (ineval '(2 - * 3 + 4))
   (ineval '-)
   (ineval '+)
   (ineval '*)
   (ineval '())
   (ineval #t)
   (ineval '(* 2))
   (ineval '(3 - 1))
   

7. Extra credit: define deep-palindrome? which takes an sexpr and returns true iff its argument is the same when flipped over, eg it would be true of the following sexprs #t, 12, ((foo bar) baz (bar foo)) but false of ((foo bar) baz (foo bar)).

Submission