Due at 5pm on Fri Mar 5, 1999

Except where otherwise specified you may use recursion, higher-order functions, etc in solving the below. Choose the right tool for the job! (5 points each)

- 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. - 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.)- Using recursion:
`largest-prefer-odd-a` - Using higher-order functions:
`largest-prefer-odd-b`

- Using recursion:
- 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.) - 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)

- Use
`to-leaves`to define`exaggerate`, eg`(exaggerate '(my 1 foot (no 18 inch) fish))`yields`(my 2 foot (no 36 inch) fish)`. - 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))

*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))`.

Barak Pearlmutter <bap@cs.unm.edu>