Programming Paradigms CSI2120: Jochen Lang EECS, University of Ottawa Canada

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))
or
(a (b () ()) (c (d () ()) (e () ()))
b c
or
(a b.(c d.e))
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

Inorder Traversal
• Inorder traversal on a binary search tree will produce a sorted list
(define (inorder t)
(define traverse
(lambda (t)
(if (null? t) '()
(append (traverse (cadr t)) (cons (car t)
(traverse (caddr t))))
)))
(if
(not (tree? t))
(list 'not-a-tree t)
(traverse t)
))
=> inorder
(inorder '(73 (31 (5 () ()) ()) (101 (83 () (97 () ()))
())))
=> (5 31 73 83 97 101)

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

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

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)

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)

Searching in a BST
(define search-BST
(lambda (x t)
(define search
(lambda (x t)
(cond 73
((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) 5 83
(search x t)
)))
=> search-BST
(define precedes? (lambda (x y) (< x y)))
=> precedes? 97
(search-BST 83 '(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())))
=> #t

Insertion into a BST
(define (insert-BST tree value)

(cond ((null? tree) (list value '() '()))
((< 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
(insert -BST '(73 (31 (5 () ()) ()) (101 (83 () (97 ()
())) ())) 86)
=> (73 (31 (5 () ()) ()) (101 (83 () (97 (86 () ())
())) ()))

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)

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)
(delete x (caddr t))))
(else 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 () ())))

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

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)

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

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])

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.

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

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
=>

Tic Tac Toe: Representation
(define start ‘((1 2 3) (4 5 6) (7 8 9)

(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))
1 2 3 X
4 5 6
7 8 9 O

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 new old (cdr l)))))))
=> subst
(subst 'X 1 start)
=> ((x 2 3) (4 5 6) (7 8 9) (x 4 7) (2 5 8) (3 6 9) (x
5 9) (3 5 7))

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))
(all-equal? (cdr list)))
(else #f)))
=> all-equal?
(define (winner board)

(map all-equal? board))
=> winner

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

Tic Tac Toe: Evaluating State
• Using our helper function

(map (lambda (list) (number-of-member ‘X list))
‘((X 2 3) (4 X X) (7 O O) (X 4 7)
(2 X O) (3 X O) (X X O) (3 X 7))))
(1 2 0 1 1 1 2 1)
X
X X
O O

Scheme: Functional Programming
• Tree representations
• Binary search trees
• Lazy evaluations
• Examples
– Towers of Hanoi
– Tic Tac Toe

Programming Paradigms CSI2120: Jochen Lang EECS, University of Ottawa Canada

Uploaded by

Copyright:

Available Formats

Programming Paradigms CSI2120: Jochen Lang EECS, University of Ottawa Canada

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Programming Paradigms CSI2120: Jochen Lang EECS, University of Ottawa Canada

Uploaded by

Copyright:

Available Formats

Programming

CSI2120: Programming Paradigms

• A binary tree can be represented with nested lists

CSI2120: Programming Paradigms

• Test if a list confirms to the tree representation

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

(define (nsymbols tree) (nsymbolst tree 0))

CSI2120: Programming Paradigms

(nsymbols '(+ a (* b c)))

CSI2120: Programming Paradigms

(define (tree->list tree)

(define (tree->list2 tree lst)

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

(define (insert-BST tree value)

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

• Lazy evaluation delays the evaluation of an expression

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

(define (towers n to from using)

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

(define start ‘((1 2 3) (4 5 6) (7 8 9)

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

• Equality of all elements in a list

(define (winner board)

CSI2120: Programming Paradigms

(define (play board player position)

(define (number-of-member x list)

CSI2120: Programming Paradigms

• Using our helper function

CSI2120: Programming Paradigms

CSI2120: Programming Paradigms

You might also like