Scheme Basics

Pairs, lists and recursion

Andy Balaam

Contents

• Pairs
• Lists
• "Loops"
• Map
• Fold
• Discussion

Pairs

> (cons 1 2)
(1 . 2)

> (cons (cons 1 2) 3)
((1 . 2) . 3)

> (define foo (cons 1 2))

> foo
(1 . 2)

> (car foo)
1

> (cdr foo)
2

Lists

(cons 1 null)
(1)

(define bar (cons 1 null))

bar
(1)

(car bar)
1

(cdr bar)
()

null
()

Lists (2)

> (cons 1 (cons 2 null))
(1 2)

> (cons 1 (cons 2 (cons 3 null)))
(1 2 3)

> (define mylist (cons 1 (cons 2 (cons 3 null))))

> mylist
(1 2 3)

> (car mylist)
1

> (cdr mylist)
(2 3)

Lists (3)

> (cadr mylist)
2

> (caddr mylist)
3

> (equal? (list 1 2 3) mylist)
#t

> (list-ref (list "a" "b" "c") 1)
"b"

> (list-ref (list "a" "b" "c") 2)
"c"

"Loops"

• How would we implement list-ref?

"Loops" (2)

(define (my-list-ref lst n)
    (if (zero? n)
        (car lst)
        (my-list-ref (cdr lst) (- n 1))))

> (my-list-ref (list "a" "b" "c") 1)
"b"

Map

> (define baz (list 1 2 3))

> (define (double x) (* x 2))

> (map double baz)
(2 4 6)

> (define (double-all x) (map double x))

> (double-all baz)
(2 4 6)

Map (2)

• How would we implement map?

Map (3)

(define (my-map fn lst)
    (if (null? lst)
        null
        (cons (fn (car lst)) (my-map fn (cdr lst)))))

> (my-map double baz)
(2 4 6)

Fold

> (define qux (list 1 2 3 4))

> (foldr + 0 qux)
10

> (foldr + 2000 qux)
2010

> (foldr * 1 qux)
24

> (foldr * 0 qux)
0

Fold (2)

• How would we implement foldr?

Fold (3)

(define (my-foldr fn start lst)
    (if (null? lst)
        start
        (fn (car lst) (my-foldr fn start (cdr lst)))))

>  (my-foldr + 0 qux)
10
> (my-foldr * 1 qux)
24

Note

; mzscheme calls it null, but really it's nil
(define nil null)

Discussion