University of Virginia Computer Science
CS150: Computer Science, Fall 2005
 (none)
5 September 2005

CS150 Notes 6 (5 September 2005)

Assignments Due

List Recursion Practice
Since lists are a recursive data structure, it is natural to define procedures that operate on lists recursively. We typically do this by thinking about two cases:
  1. What should we do when the list is null?
  2. When the list is not null, what should we do with the first element and the rest of the list?

Length

Define a procedure length that takes a list as its operand and evaluates to the number of elements in the list.

  1. What should we do when the list is null?
    The length of an empty list is zero. So, when the list is null, we should evaluate to 0.
  2. When the list is not null, what should we do with the first element and the rest of the list?
    The length of the list, (cons el lst) is one more than the length of the list lst. So, when the list is a pair of an element and a list, we should evaluate to (+ 1 (length (cdr lst))) 
(define (length lst)
  (if (null? lst)

      ___________________________ ; what to do for empty list


      ______________________________________ ; what to do for pair list

      ))

Sumlist

Define a procedure sumlist that takes a list as its operand and evaluates to the sum of elements in the list. 
(define (sumlist lst)






  )

Map

Define a procedure map that takes a procedure as its first operand and a list as its second operand and evaluates to the list containing the values resulting from applying the procedure to each element of the input list.

Examples:

> (map car (list (cons 1 2) (cons 2 3)))

(1 2)

> (map + null)

()

> (map (lambda (x) (* x x)) (list 1 2 3))

(2 4 6)

> (map (lambda (el) (> el 3)) (list 2 4 6))


__________________

> (map (lambda (el) (+ 1 el)) (list 1 2 3))


__________________

(define (map f lst)





   )
The analyze-flop-situation proceudre from PS2 uses map: 
(map (lambda (turn-card) 
       (analyze-turn-situation hole1 hole2 (cons turn-card community)))
     current-deck)))
What is this expression doing?




The choose-n procedure from PS2 uses map: 

 (map (lambda (clst) (cons (car lst) clst)) 
      (choose-n (- n 1) ;;; all possibilities using the first element
		(cdr lst)))))))
What is this expression doing?


"); print ( $res[$first] ) ; print (""); ?>
CS 150: Computer Science
University of Virginia
 evans@virginia.edu
Using these Materials