Programming Paradigms CSI2120
Jochen Lang
EECS, University of Ottawa Canada
Scheme: Functional Programming
• Tree representations
• Binary search trees
• Lazy evaluations • Examples
– Towers of Hanoi – Tic Tac Toe
CSI2120: Programming Paradigms
List Representation for Trees
• A binary tree can be represented with nested lists
a
(a b (c d e))
bc
(a (b () ()) (c (d () ()) (e () ()))
de
CSI2120: Programming Paradigms
or
or
(a b.(c d.e))
Test for Binary Tree
• Test if a list confirms to the tree representation (define tree?
(lambda (t)
(cond
((not (list? t)) #f)
((null? t) #t)
((not (= (length t) 3)) #f) ; node has 3 entries ((not (tree? (cadr t))) #f) ; recurse left subtree ((not (tree? (caddr t))) #f) ; recurse right subtree (else #t)
)))
=> tree?
(tree? ‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ()))) => #t
CSI2120: Programming Paradigms
Inorder Traversal
• Inorder traversal on a binary search tree will produce a sorted list (define (inorder t)
(define traverse
(lambda (t)
))) (if
(if (null? t) ‘()
(append (traverse (cadr t)) (cons (car t)
(not (tree? t))
(list ‘not-a-tree t)
(traverse t)
))
(traverse (caddr t))))
=> inorder
(inorder ‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ()))
())))
=> (5 31 73 83 97 101)
CSI2120: Programming Paradigms
Count the Type and Number of Elements in a Tree or List
• Tree representation is a list (define (nsymbols tree)
(if (pair? tree)
(+ (nsymbols (car tree))
(nsymbols (cdr tree)))
(if (symbol? tree) 1 0)))
=> nsymbols
(nsymbols ‘(+ a (* b c)))
=> 5
• Note the use of pair? instead of list?
• We could also use char? or number? for corresponding
predicates
CSI2120: Programming Paradigms
Instead with Partial Tail Recursion
(define (nsymbols tree) (nsymbolst tree 0))
=> nsymbols
(define (nsymbolst tree n)
(begin
(display tree)(display ” “)
(display n)(newline) ; just to visualize
(if (pair? tree)
(nsymbolst (cdr tree)
(nsymbolst (car tree) n))
(+ n (if (symbol? tree) 1 0)))))
=> nsymbolst
CSI2120: Programming Paradigms
Tail Recursion
(nsymbols ‘(+ a (* b c)))
;;;;;;;;;;;;;;;;;
(+ a (* b c)) 0
(a (* b c)) 1
((* b c)) 2
(* b c) 2
(b c) 3
(c) 4 ;;;;;;;;;;;;;;;;; 5
The partial tail recursive version needs 6 tail recursive calls and 6 non tail recursive calls (compared to 12 with the double recursion)
CSI2120: Programming Paradigms
Conversion of a Tree into a List
(define (tree->list tree)
(reverse (tree->list2 tree ‘())))
(define (tree->list2 tree lst)
(if (pair? tree)
(tree->list2 (cdr tree)
(tree->list2 (car tree) lst))
(if (null? tree) lst (cons tree lst) )))
=> tree->list
(tree->list ‘(73 (31 (5 () ()) ()) (101 (83 ()
(97 () ())) ())))
=> (73 31 5 101 83 97)
CSI2120: Programming Paradigms
Searching in a BST
(define search-BST
(lambda (x t)
(define search
(lambda (x t)
73
(cond
((null? t) #f)
((equal? x (car t)) #t)
((precedes? x (car t)) (search x (cadr t)))
((precedes? (car t) x) (search x (caddr t)))
(else #f)
)))
31
101
(if
(not (tree? t))
(list ‘not-a-tree t)
(search x t)
)))
5
83
=> search-BST
(define precedes? (lambda (x y) (< x y)))
=> precedes?
(search-BST 83 ‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ()))) => #t
97
CSI2120: Programming Paradigms
Insertion into a BST
(define (insert-BST tree value)
(cond ((null? tree) (list value ‘() ‘()))
=> insert-BST
((< value (car tree))
(list (car tree) (insert-BST (cadr tree) value)
(caddr tree)))
(else (list (car tree) (cadr tree)
(insert-BST (caddr tree) value)))))
(insert -BST '(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())) 86)
=> (73 (31 (5 () ()) ()) (101 (83 () (97 (86 () ()) ())) ()))
CSI2120: Programming Paradigms
Remove the Maximum from a BST
(define removemax-BST
(lambda (t)
(cond
((null? (caddr t)) (cons (cadr t) (car t)))
(else
(let ((r (removemax-BST (caddr t))))
(cons (list (car t) (cadr t) (car r)) (cdr r))
)) )))
=> removemax-BST
(removemax-BST ‘(73 (31 (5 () ()) ()) (101 (83 ()
(97 () ())) ())))
=> ((73 (31 (5 () ()) ()) (83 () (97 () ()))) . 101)
CSI2120: Programming Paradigms
Removal of a Node from a BST
(define delete
(lambda (x t)
(cond
((null? t) ())
((and (equal? x (car t)) (null? (cadr t))) (caddr t)) ((and (equal? x (car t)) (null? (caddr t))) (cadr t)) ((equal? x (car t))
(let ((r (removemax-BST (cadr t)))) (list (cdr r) (car r) (caddr t))
))
((precedes? x (car t)) (list (car t)
(delete x (cadr t)) (caddr t))) ((precedes? (car t) x) (list (car t) (cadr t)
(else t) )))
CSI2120: Programming Paradigms
(delete x (caddr t))))
Main Routine: Removal of a Node
(define delete-BST
(lambda (x t)
(if
(not (tree? t))
(list ‘not-a-tree t)
(delete x t)
)))
=> delete-BST
(delete-BST 101 ‘(73 (31 (5 () ()) ()) (101 (83
() (97 () ())) ())))
=> (73 (31 (5 () ()) ()) (83 () (97 () ())))
CSI2120: Programming Paradigms
Lazy Evaluation
• Lazy evaluation delays the evaluation of an expression
• Two commands
(delay expression)
– Returns a promise of evaluation
(force promise)
– Forces the evaluation of the promise
CSI2120: Programming Paradigms
Example: Lazy Evaluation
• Member of a Series
– In some cases, it is possible to obtain a result without having
to calculate all the elements of a series. • Define a series
(define (series n1 n2 N)
(begin
(if (zero? N) ()
(cons (+ n1 n2)
(series n2 (+ n1 n2) (- N 1))))))
=> series
(series 0 1 10)
=> (1 2 3 5 8 13 21 34 55 89)
CSI2120: Programming Paradigms
Membership Test Without Lazy Evaluation
(define (in-seq x L)
(cond ((null? L) ())
(
((< x (car L)) ())
((= x (car L)) x)
(#t (in-seq x (cdr L)))))
=> in-seq
(in-seq 15 (series 0 1 200))
=> ()
• Will cause 200 recursive calls to series, even though 7 calls would be enough
CSI2120: Programming Paradigms
Series with Lazy Evaluation
(define (series n1 n2 N)
(if (zero? N) ()
(cons (+ n1 n2)
(delay (series n2 (+ n1 n2) (- N 1))))))
=> series
(series 0 1 200)
=> (1 . #[promise 1])
• Get a promise which we can force (cons (car(series 0 1 200))
(force (cdr(series 0 1 200))))
=> (1 2 . #[promise 2])
CSI2120: Programming Paradigms
Lazy Evaluation
(define (in-seq x L)
(let ((tmp (car L)))
(cond ((null? L) ())
((< x tmp) ())
((= x tmp) x)
(#t (in-seq x (force (cdr L)))))))
=> in-seq
(in-seq 15 (series 0 1 200))
=> ()
• The series evaluation will only have to be forced until a value greater or equal the number x is reached.
CSI2120: Programming Paradigms
Towers of Hanoi
(define (towers n to from using)
(if (> n 0)
(begin
(towers (- n 1) using from to)
(display “move “)(display from)
(display ” –> “)(display to)(newline)
(towers (- n 1) to using from) )
))
=> towers
(define (hanoi n)
(towers n 3 1 2))
=> hanoi
CSI2120: Programming Paradigms
Example: Towers of Hanoi
(hanoi 3)
move 1 –> 3
move 1 –> 2
move 3 –> 2
move 1 –> 3
move 2 –> 1
move 2 –> 3
move 1 –> 3
=>
CSI2120: Programming Paradigms
Tic Tac Toe: Representation
(definestart ‘((123)(456)(789) (1 4 7) (2 5 8) (3 6 9)
(1 5 9) (3 5 7)))
• One move by X:
((X 2 3) (4 5 6) (7 8 9) (X 4 7) (2 5 8) (3 6 9) (X 5 9) (3 5 7))
• One move by O:
((X 2 3) (4 5 6) (7 O 9) (X 4 7) (2 5 O) (3 6 9) (X 5 9) (3 5 7))
123 X 456
789 O
CSI2120: Programming Paradigms
Tic Tac Toe: Making a Move
• Occupying a field – substituting a number for X or O everywhere (define subst
(lambda (new old l)
(cond ((null? l) (quote ()))
((not (list? (car l)))
(cond ((eq? (car l) old)
(cons new (subst new old (cdr l))))
(else (cons (car l)
(subst new old (cdr l))))))
(else (cons (subst new old (car l))
=> subst
(subst ‘X 1 start)
(subst new old (cdr l)))))))
=> ((x 2 3) (4 5 6) (7 8 9) (x 4 7) (2 5 8) (3 6 9) (x
5 9) (3 5 7))
CSI2120: Programming Paradigms
Tic Tac Toe: Winning Condition
• Equality of all elements in a list (define (all-equal? list)
(cond ((null? list) ’())
((null? (cdr list)) (car list))
((equal? (car list) (cadr list))
(else #f)))
=> all-equal?
(define (winner board)
(map all-equal? board))
=> winner
CSI2120: Programming Paradigms
(all-equal? (cdr list)))
Tic Tac Toe: Helper Functions
(define (play board player position)
(subst player position board))
=> play
(define (number-of-member x list)
(cond ((null? list) 0)
((equal? x (car list))
(+ 1 (number-of-member x (cdr list))))
(else (number-of-member x (cdr list)))))
=> number-of-member
CSI2120: Programming Paradigms
Tic Tac Toe: Evaluating State
• Using our helper function
(map (lambda (list) (number-of-member ‘X list))
(1 2 0 1 1 1 2 1)
‘((X 2 3) (4 X X) (7 O O) (X 4 7)
(2 X O) (3 X O) (X X O) (3 X 7))))
CSI2120: Programming Paradigms
X
XX
OO
Scheme: Functional Programming
• Tree representations
• Binary search trees
• Lazy evaluations • Examples
– Towers of Hanoi – Tic Tac Toe
CSI2120: Programming Paradigms