程序代写代做代考 Programming Paradigms CSI2120

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