Scheme: basic-level questions

If you need help reviewing Scheme, take a look at these resources:

• Albert's and Robert's slides

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

What would Scheme print

Question 1

scm> (+ 4 3)
______7
scm> (4 + 3)
______Error
scm> (+ 1 2 3 4)
______10
scm> (- 1 2 3 4)
______-8

Question 2

scm> (if True (+ 2 3))
______5
scm> (if False (+ 2 3))
______okay   ; i.e. returns nothing
scm> (if False (/ 1 0) 4)
______4
scm> (and True False True)
______False
scm> (and True 0 True)
______True
scm> (and 3 5 2)
______2
scm> (or True False True)
______True
scm> (or False 4 True)
______4

Question 3

scm> (define x 2)
______x
scm> x
______2
scm> (define (f x) (* x x))
______f
scm> (f 4)
______16
scm> (define (g x) (lambda (y) (* x y)))
______g
scm> ((g 4) 5)
______20

Question 4

scm> (cons 1 (cons 2 nil))
______(1 2)
scm> (cons 1 2)
______(1 . 2)
scm> (car (cons 1 (cons 2 nil)))
______1
scm> (cdr (cons 1 (cons 2 nil)))
______(2)
scm> (cdr (cons 1 2))
______2
scm> (null? (cons 1 nil))
______False
scm> (null? (cdr (cons 1 nil)))
______True
scm> (list 1 2 3 4)
______(1 2 3 4)
scm> (cdr (list 1 2 3 4))
______(2 3 4)

Code-Writing Questions

Question 5

Implement the function filter, which takes a predicate and a Scheme list as arguments. filter will return a new list that only contains elements of the original list that satisfy the predicate.

(define (filter pred lst)
    ; YOUR CODE HERE
    )

; Tests
scm> (define (less-3 x) (< x 3))
less-3
scm> (filter less-3 (list 1 2 3 4))
(1 2)

(define (filter pred lst)
    (cond ((null? lst) nil)
          ((pred (car lst)) (cons (car lst)
                                  (filter pred (cdr lst))))
          (else (filter pred (cdr lst)))))

Question 6

Implement the function interleave, which takes a two lists as arguments. interleave will return a new list that interleaves the elements of the two lists, with list1 starting first. Refer to the tests for sample input/output.

(define (interleave list1 list2)
    ; YOUR CODE HERE
    )

; Tests
scm> (interleave (list 1 3 5) (list 2 4 6))
(1 2 3 4 5 6)
scm> (interleave (list 1 3 5) nil)
(1 3 5)
scm> (interleave (list 1 3 5) (list 2 4))
(1 2 3 4 5)

(define (interleave list1 ist2)
    (if (or (null? list1) (null? list2))
        (append list1 list2)
        (cons (car list1)
              (cons (car list2)
                    (interleave (cdr list1) (cdr list2))))))

Question 7

Implement the function count-stairways, which takes a number (of steps). Assuming we can take 1 or 2 steps, return the number of ways we can climb up the stairs.

(define (count-stairways n)
    ; YOUR CODE HERE
    )

; Tests
scm> (count-stairways 4)
5
scm> (count-stairways 5)
8

(define (count-stairways n)
    (cond ((= n 1) 1)
          ((= n 2) 2)
          (else (+ (count-stairways (- n 1))
                   (count-stairways (- n 2))))))