CS61A: Lecture 26

Scheme Lists

• Scheme lists are written in parentheses with elements separated by spaces
• Procedures
  • cons: Procedure that creates a new list.
  • car: Procedure that prints out the first element of the list
  • cdr: Procedure that prints out the rest of the list
  • nil: The empty list
  • list: Creates a new list
• The reason that we use cons is that we may add an element onto an existing list to the front of it.
• Ex: copying a list:

(define (same-list s)
    (if (null? s) s (cons (car s) (same-list (cdr s))))
)

• Ex: Replace an element at index i

(define (replace s i x)
    (if (= i 0) (cons x (cdr s)) (cons (car s) (replace (cdrs) (- i 1) s)))
)

• Ex: Combine two or more lists

scm> (append (list 1 2 3) (list 4 5 6) (list 7 8 9))
(1 2 3 4 5 6 7 8 9)

• Practice:

(define s (cons 1 (cons 2 nil))) -> (1 2)
(list 3 s) -> (3 (1 2)) correct
(cons 3 s) -> (3 1 2) correct
(append 3 s) -> Error correct
(list s s) -> ((1 2) (1 2)) correct
(cons s s) -> ((1 2) 1 2) correct
(append s s) -> (1 2 1 2) correct

• Ex: Recursive COnstruction:
  • Return a list of two lists; the first n elements of s and the rest
    • (split (list 3 4 5 6 7 8) 3)
    • ((3 4 5) (6 7 8))

(define (split s n)
    (define (prefix s n)
        (if (zero? n) nil (cons (car s) (prefix (cdr s) (- n 1))))
    )
    (define (suffix s n)
        (if (zero? n) s (suffix (cdr s) (- n 1)))
    )
    (list (prefix s n) (suffix s n))
)

Symbolic Programming

• Symbols normally refer to values; how do we refer to symbols?

scm> (define a 1)
scm> (define b 2)
scm> (list a b)
(1 2)

• Quotation is used to refer to symbols directly in Lisp.

scm> (list 'a 'b)
(a b)
scm> (define 'a b)
(a 2)

• Quotation can also be applied to combination to form lists.

scm> `(a b c)
scm> (car `(a b c))
a

• we may also recover the value of a symbol from a quotation by simply eval the symbol.

scm> (define a (+ 3 3)) scm> (define t `(a b c)) scm> (eval (car t)) 6