Pairs

1
2
3
4
5
6
7
8
9
10
11
12
> (cons 1 2)
(1 . 2)
> (cons (cons 1 2) 3)
((1 . 2) . 3)
> (define foo (cons 1 2))
> foo
(1 . 2)

> (car foo)		; car gets the first element in a pair.
1
> (cdr foo)		; while cdr gets the second
2

Lists

Pair is basically a little list.

The definition of a list is a set of pairs and the last pair in that has null on the right hand side. If you don’t believe that, check out the code below.

1
2
3
4
5
6
7
8
9
10
11
12
> (cons 1 null)		; it's indeed a pair of 1 and null but the way the interpreter writes it is a list containing only 1.
(1)

> (cons 1 2)
(1 . 2)		; it's a pair.
> (cons 1 (cons 2 null))
(1 2)		; it's a list
> (cons 1 (cons 2 (cons 3 null)))
(1 2 3)

> (equal? (cons 1 (cons 2 null)) (list 1 2))
#t

List is a bunch of pairs cascading down and ending in null.

car & cdr

1
2
3
4
5
6
7
8
9
10
11
12
13
> (define mylist (cons 1 (cons 2 (cons 3 null))))
> mylist
(1 2 3)

> (car mylist)
1		; the first element 1 in the pair mylist
> (cdr mylist)
(2 3)		; the second element (cons 2 (cons 3 null)) in the pair mylist, which is precisely the rest of the list mylist.

> (cadr mylist)		; d, then a.
2	
> (caddr mylist)		; double d, then a.
3

list-ref

1
2
3
4
> (list-ref (list "a" "b" "c") 1)
"b"
> (list-ref (list "a" "b" "c") 2)
"c"

“Loops”

Loops are actually recursion.

A bad implementation of list-ref.

1
2
3
4
5
6
> (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

Map applies the function you give it to every element in the list you give it. Difference between it and Python’s map is the latter one returns a map object which is a kind of iterator, but Scheme’s map directly give you a list.

1
2
3
4
5
6
7
> (define baz (list 1 2 3))
> (define (double x) (* x 2))
> (map double baz)
(2 4 6)

> baz
(1 2 3)

A bad implementation of map.

1
2
3
4
5
6
7
8
1 ]=> (define (my-map fn lst)
        (if (equal? () lst)
                ()
                (cons (fn (car lst)) (my-map fn (cdr lst)))))

1 ]=> (my-map double baz)

;Value: (2 4 6)

Fold

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
> (define qux (list 1 2 3 4))
> (foldr + 0 qux)	; 4 + 3 + 2 + 1 + 0
10
> (foldr + 2000 qux)	; 1 + (2 + (3 + (4 + 2000)))
2010
> (foldr + -100 qux)	; 1 + (2 + (3 + (4 + -100)))
-90

> (foldr - 0 qux)	; 1 - (2 - (3 - (4 - 0)))
-2
> (foldr - 2000 qux)	; 1 - (2 - (3 - (4 - 2000)))
1998

> (foldr * 1 qux)	; 1 * (2 * (3 * (4 * 1)))
24
> (foldr * 0 qux)
0

>> (my-foldr / 1 qux)	; 1 / (2 / (3 / (4 / 1)))
3/8

A bad implementation of foldr.

1
2
3
4
> (define (my-foldr fn start lst)
    (if (null? lst)
        start
        (fn (car lst) (my-foldr fn start (cdr lst)))))