Other built-in Operators

32
Shorthand for nested car, cdr
◼ Scheme provides shorthands for expressions consisting of
successive application of car and cdr
◼ (car (cdr x)) -> (cadr x)
◼ (cdr (car x)) -> (cdar x)
◼ (car (cdr (car x))) -> (cadar x)
expression shorthand Value
x x ((it seems that) you (like) me)
(car x) (car x) (it seems that)
(car (car x)) (caar x) it
(cdr (car x)) (cdar x) (seems that)
(cdr x) (cdr x) (you (like) me)
(car (cdr x)) (cadr x) you
(cdr (cdr x)) (cddr x) ((like) me)
33
The let construct
◼ ( let ((x1 E1) (x2 E2) … (xk Ek)) F )
◼ E1, E2, … , Ek are all evaluated
◼ Then F is evaluated with xi
◼ the result is the value of F
◼ The let constructor
◼ Allows subexpressions to be named
◼ Can be used to factor out common subexpression
◼ ex) (let (( three-sq (square 3))) (+ three-sq three-sq))
; (+ (square 3) (square 3)) = 18

34
The let* construct
◼ The sequential variant of the let
( let* ((x1 E1) (x2 E2) … (xk Ek)) F )
◼ Binds xi to the value of Ei before Ei+1
◼ ex) (define x 0)
(let (( x 2 ) ( y x )) y ) ;0
(let* (( x 2 ) ( y x )) y ) ;2

35
The let* construct
◼ The sequential variant of the let
( let* ((x1 E1) (x2 E2) … (xk Ek)) F )
◼ Binds xi to the value of Ei before Ei+1
◼ ex)

(let ((a 1)(b (+ a 2))) b) ; Unbound variable: a

(let* ((a 1)(b (+ a 2))) b);3

36
List Manipulation

37
 Getting the length of a list :
length
◼ E.g.(length ‘(1 2 3)) → 3
◼ Length of an empty list) = 0
◼ (length ‘()) ≡ 0
◼ Length of a nonempty list (cons a y) = length (y) + 1
◼ (length (cons a y))≡ (+ 1 length y))
◼ Let (cons a y) ➔ x, (cdr x) ➔ y
(length x) ≡ (+ 1 (length (cdr x)))

(define (length x)
(cond ((null? x) 0)
(else (+ 1 (length (cdr x)))) ))

38
 Appending two lists : append
◼ e.g.
◼ (append ‘() ‘(a b c d)) → (a b c d )
◼ (append ‘(a b c) ‘(d) ) → (a b c d )
◼ (cons ‘a (append ‘(b c) ‘(d))) → (a b c d)
◼ (append ‘() z)) ≡ z
◼ (append (cons a y) z) ≡ (cons a (append y z))
➔ (append x z) ≡ (cons (car x) (append (cdr
x) y)))))

(define (append x y)
(cond ((null? x) y)
(else (cons (car x) (append (cdr x) y)))))

39
 Getting a flattened form of a list :
flatten
◼ E.g.
◼ ((a) ((b b)) (((c c c ))) → (a b b c c c)
◼ Use Scheme function pair?
◼ Test whether its argument is a list
◼ E.g. (pair? 1) → #f, (pair? ‘(1)) → #t

(define (flatten x)
(cond ((null? x) ‘())
((not (pair? x)) (list x))
(else (append (flatten (car x) )
(flatten (cdr x))))))

40
 Mapping a function across list
elements : map
◼ E.g.
◼ (map square ‘(1 2 3 4 5)) → (1 4 9 16
25)
◼ (define (square x) (* x x))
◼ (map car ‘((a 1) (b 2) (c 3) (d 4)))
→ (a b c d)

(define (map f x)
(cond ((null? x) '())
(else (cons (f (car x))
( map f (cdr x))))))

41
Lists of subexpressions
◼ (+ 2 3) → 5, (+ 2 3 5) → 10
◼ One subexpression : (+ 2) → 2, (* 2) → 2
◼ No subexpression : (+) → 0, (*) → 1
◼ Proper-sum : builds a sum by consing a + onto the
list
◼ E.g. (proper-sum ‘(a b c)) → (+ a b c)
(define (proper-sum x) ;; x is a list
(cond ((null? x) 0)
((null? (cdr x)) (car x))
(else (cons ‘+ x)) ))

42
A parameterized function
◼ E.g. Parameterized function

◼ (proper make-sum 0 ‘(a b c))

Parameterized function
→ (+ a b c)
◼ (proper make-product 1 ‘(a b c))
→ (* a b c)
◼ (proper make-sum 0 ‘())→ 0
◼ (proper make-product 1 ‘(a))→ a
(define (proper make-kind id x)
(cond ((null? x) id)
((null? (cdr x)) (car x))
(else (make-kind x)) ))

43
Storage Allocation For Lists

44
Storage Allocation For Lists
◼ A list is made up of cells.
◼ A cells with pointers to the head and
tail of a list.

to tail

to head

◼ Cons allocates a single cell

45
Cons Allocates Cells (1)
◼ Lists are built out of cells capable of
holding pointers to the head(car) and
tail(cdr) of a list.
◼ car : “Contents of the Address part of
Register”
◼ cdr : “Contents of the Decrement part of
Register”
◼ Cons : allocates a word and stuffed
pointers to the car and cdr of a list.
46
Cons Allocates Cells (2)
◼ The empty list () is a special pointer.
◼ Think of () as a special address that is not
used for anything else.
◼ (cons ‘it (cons ‘seems (cons ‘that ‘())))

()

it seems that

47
 Cons Allocates Cells (3)
◼ null? : compares its argument for equality
with ().
◼ car : returns the pointer in the first field.
◼ cdr : returns the pointer in the second field.

(car ‘(it seems that)) (cdr ‘(it seems that))

()

it seems that

48
Notions of Equality (1)
◼ equal? : recursively checks whether its
two arguments are lists with “equal”
elements.
◼ eq? : checks whether its two arguments
are identical pointers.

49
Notions of Equality (2)
◼ (equal? ‘hello ‘hello) : #t
(eq? ‘hello ‘hello) : #t
◼ (equal? ‘(hello world) ‘(hello world)) : #t
(eq? ‘(hello world) ‘(hello world)) : #f
()

hello world

()

50
 Notions of Equality (3)
◼ (define x ‘(it seems that))
◼ (define y (cons (car x) (cdr x)))
◼ (equal? x y) : #t
◼ (eq? x y) : #f y

x x
() ()

it seems that it seems that

51
Allocation and Deallocation (1)
◼ Cells that are no longer in use have to be
deallocated.
◼ A standard technique is to link cells on a list
called a free list. (acts like a stack of cells)
◼ pop : returns a freshly allocated cell.
◼ push : returns a cell back onto the stack.
◼ Garbage collection returns cells to the free list
automatically
◼ without explicit instructions from a program.

52
Allocation and Deallocation (2)
◼ Two approaches to deallocation of cells
◼ Lazy approach : Wait until memory runs
out and only then collect dead cells.
◼ Eager approach : Each time a cell is
reached, check whether the cell will be
needed after the operation.

53
Allocation and Deallocation (3)
◼ A simple approach to garbage collection
◼ Mark phase : Mark all the cells that can be
reached by following pointers.
◼ Sweep phase : Sweep through memory,
looking for unmarked cells.

54
Allocation and Deallocation (4)
◼ Copying collector
◼ Avoids the expense of the sweep phase
◼ Divides memory into two halves, the working half
and the free half.
◼ When the working half fills up, the reachable cells
are copied into consecutive locations in the free
half. The roles of the free and working halves are
switched.
◼ Looks only at the reachable cells.

55
Hashing

Introduction to Data Structures

Kyuseok Shim
ECE, SNU.

56
Hash Tables
◼ Static hashing
◼ Dictionary pairs – stored in a hash table
◼ Hash table
◼ Partitioned into b buckets ht[0],…,ht[b-1]
◼ Key
◼ Address of a pair
◼ Determined by a hash function, h
◼ h(k) – integer in the [0, b-1]

57
Hash Tables
◼ Hash function
◼ Easy to compute
◼ Minimize collisions
◼ Uniform hash function gives 1/b
probability of h(x) = i to x.
◼ Synonyms
◼ Two identifiers I1 and I2 if h(I1) = h(I2)

58
Hash Functions
◼ Division
◼ We divide the identifier k by some number D and use the
remainder as the hash address for k.
h(k) = k % D
◼ This gives bucket addresses that range 0 to D - 1, where D

= that table size.

◼ The choice of D is critical.
◼ If D is divisible by 2, then odd keys are mapped to odd

buckets and even keys are mapped to even buckets.

◼ When many identifiers are permutations of each other, a
biased use of the table results.
◼ In practice, choose D such that it has no prime divisors less
than 20.

59
Hash Functions
◼ Mid-Square
◼ Used in many cases.
◼ Square the identifier and use an
appropriate number of bits from the
middle.

◼ r bits used - table size = 2r

60
Hash Functions
◼ Converting Keys to Integers
◼ Keys need to first be converted to
nonnegative integers.

61
Program 8.1:Converting a string
into a non-negative integer

62
Overflow Handling
◼ Two method of overflow handling
◼ Linear probing
◼ Linear open addressing

63
Open Addressing
◼ Linear probing
◼ Inserting a new pair with key k
◼ Search hash table buckets in the order,
ht[h(k)+i%b], 0≤i≤b-1
◼ Terminate when reach the first unfilled
bucket
◼ No unfilled bucket, hash table full and
increase the table size => Must change
hash function as well.
64
Overflow Handling: Open
Addressing
◼ Ex 8.6)
◼ 26-bucket table, one slot per bucket
◼ Hash function h(x) = first character of x
◼ Identifiers : GA, D, A, G, L, A2, A1, A3, A4,
Z, ZA, E

65
Overflow Handling: Open
Addressing
◼ identifiers : GA, D, A, G, L, A2, A1, A3,
A4, Z, ZA, E

66
 Overflow Handling: Open
Addressing
◼ Hash table search for the pair with key k
1. Compute h(k)
2. Examine the hash table buckets in the
order ht[h(k)], ht[h(k)+1]%b],
…,ht[(h(k)+j)%b] until one of the following
happens:
1. The bucket ht[(h(k)+j)%b] has a pair whose
key is k; in this case, the desired pair has been
found.
2. ht[h(k)+j] is empty; k is not in the table.
3. We return to the starting position ht[h(k)]; the
table is full and k is not in the table. 67