University of Virginia Computer ScienceCS150: Computer Science, Fall 2005 |
(none)7 September 2005 |

- Friday, 9 September: PS2

- Be optimistic.
- Assume you can solve it.
- If you could, how would you solve a bigger problem.

- Think of the simplest version of the problem, something you can already solve. (This is the base case.)
- Combine them to solve the problem.

- Be
*very*optimistic. Since lists themselves are recursive structures, we should be able to come up with a recursive definition for almost anything we can think of doing with a list.- Assume we can solve a smaller version of the problem.
- Break the problem into the original list and its
`cdr`.

- Think of the simplest version of the problem, something you can
solve already. For lists, this is usually the
list. (Sometimes, it might be the length 1 list.)`null` - Combine them to solve the problem. For lists, we will usually do
combine the result of the recursive evaluation on the
`cdr`with the result of doing something with the`car`of the list.

For example:(define (listproc lst) (if (null? lst)[[[ insert base case here ]]]([[[ f ]]](car lst) (listproc (cdr lst)))))

(define (sumlist lst) (if (null? lst) 0 (+ (car lst) (sumlist (cdr lst)))))

(define (insertl lst f stopval) (if (null? lst) stopval (f (car lst) (insertl (cdr lst) f stopval)))) (define (sumlist lst) (insertl lst + 0)) (define (productlist lst) (insertl lst * 1)) (define (length lst) (insertl lst (lambda (head rest) (+ 1 rest)) 0))

(define (remove cf lst) ;; operands: cf is a comparison function that takes one operand and ;; evaluates to #t or #f ;; lst is a list of values ;; result: evaluates to a list containing the only elements of lst for ;; which (cfCould you define) evaluates to #f (if (null? lst) _________________________ (if (cf (car lst)) ______________________________ ;; discard first element ______________________________))) ;; keep first element

Could you define `remove` using just an `insertl` application?
(Explain how or why it is impossible.)

(define (filter cf lst) ;; operands: cf is a comparison function that takes one operand and ;; evaluates to #t or #f ;; lst is a list of values ;; result: evaluates to a list containing the only elements of lst for ;; which (cfThere are many ways to define) evaluates to #t )

**Challenge:** Define a procedure `(intsto n)` that
evaluates to a list containing the integers less than or equal to

*
In mathematics you don't understand things, you just get used to them.
*

John Von Neumann

CS 150: Computer ScienceUniversity of Virginia |
evans@cs.virginia.eduUsing these Materials |