• 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)
```