==> 14
Hand in the code and the output of the test cases.
1. Rmv. Add :key and :test keywords to the recursive Rmv function you wrote last week. This should work just like the built-in remove function except that there are still some missing keywords (feel free to add them!) and you may have the default test be equal instead of eql.
(Rmv 'A '(B A N A N A)) ==> (B N N) (Rmv 'A '((A B) (B A) (C A D) (D C A)) :key #'second) ==> ((A B) (D C A)) (Rmv 5 '(2 4 6 8) :test #'<) ==> (2 4) (Rmv 5 '((1 2) (1 4) (1 6) (1 8)) :key #'second :test #'<) ==> ((1 2) (1 4))
2. Cnt-If. Reproduce the behavior of the built-in count-if function, including the :key keyword. It returns the number of elements of a list that satisfy a predicate. Don't use any of the remove family of functions.
(Cnt-If #'oddp '(1 2 3 4 5 6 7)) ==> 4 (Cnt-If #'oddp '((1 A) (2 B) (3 C) (4 D) (5 E) (6 F) (7 G)) :key #'first) ==> 4
3. Cnt-If-Not. Given that you already have Cnt-If, reproduce the behavior of the built-in function count-if-not, which returns the number of elements of a list that fail a given predicate. [Hint: simple!]
(Cnt-If-Not #'numberp '(A B C D 1 2)) ==> 4 (Cnt-If-Not #'numberp '((A 5) (B 4) (C 3) (D 2) (1 A) (2 B)) :key #'first) ==> 4
4. Sum. Generalize the Square-Sum and Pi-Sum routines covered in class to come up with a general summation routine. It should take the function to apply to each term, the starting point, the ending point, and the function that calculates the next term from the current. This last function should default to adding one to the previous term.
(defun Square (X) (* X X))
(Sum #'Square 1 3) =
(defun 2+ (X) (+ X 2)) (Sum #'Square 1 5 #'2+) ===> 35
5. Integral. Now that you have a general summation routine, it can be used to define a numeric integration routine quite easily. A simple definition that, for small values of dx, approximates the integral moderately closely is the midpoint rule:
Define an "integral" function that takes f, a, b, and dx above, and uses Sum to compute the above approximation.
(Integral #'log 1 11 1) ==> 16.41278... ; log is base e by default (Integral #'log 1 11 1/10) ==> 16.37722... (Integral #'log 1 11 1/100) ==> 16.37685...The actual value is (11log(11) - 11) - (1log(1) - 1), which is 16.376848... on my machine. The exact values you get may vary depending on what types of numbers (integers, single-precision floats, or double-precision floats) you use internally. You will want to compile before trying this with very small step sizes. A recommended way of choosing the step size is by dividing the range into a certain number of pieces. Otherwise, especially if the step size is large compared to the range, the number of steps may not come out evenly, and your answer may be off. Also, you math types out there feel free to try other approximations instead (or in addition) for more accurate results.
6. [*] Self-Reproducing Form. A lambda form can be used almost anywhere in Lisp that a function name can be used. We will see more powerful uses of this when we discuss lexical closures, but for simple examples:
(defun Square (X) (* X X)) (mapcar #'Square '(1 2 3)) == (mapcar #'(lambda (X) (* X X)) '(1 2 3)) ==> (1 4 9) (Square 3) == ((lambda (X) (* X X)) 3) ==> 9
The problem here is to use this capability to make a single (non-empty) Lisp list that returns itself. I.e. define a list X such that (equal X (eval X)) ==> T I.e. type it in and you get the same thing back. For non-lists, this is easy: 9, :Foo, or "Bar" all return the same thing (themselves) when evaluated. For a list, if you could define Foo first it would be easy to arrange it so that evaluating the list (Foo 3) returned the list (Foo 3). The trick here is to do something similar without relying on any previous user-defined functions. The only Lisp constructs you need are lambda, list, and quote, and you should not try to make use of the "*" or "+" variables. Reminder: 'A is the same as (quote A).
Bonus. The original Lisp design borrowed some of the notation of the "lambda calculus" a formalism for representing functions that pre-dated computers. Who developed the lambda calculus? What other CS-related result is he (most) famous for?