Programming Paradigms
• Course overview
•Introduction to programming paradigms
Copyright By PowCoder代写 加微信 powcoder
• Review: The object-oriented
paradigm in Java •Imperative and concurrent
programming paradigm: Go. • Logic paradigm: Prolog.
• Functional paradigm: Scheme.
Acknowledgment
The slides posted through the term are based of the slides offered by:
Prof. Jochen Lang
Demo code: https://www.site.uottawa.ca/~jl ang/CSI2120/demoCode.html
Scheme: Functional Programming
• Treerepresentations • Binarysearchtrees
List Representation for Trees
• Abinarytreecanberepresentedwithnestedlists
(a b (c d e))
(a (b () ()) (c (d () ()) (e () ()))
(a b.(c d.e))
‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())))
‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ()))) ‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())))
Test for Binary Tree
• Testifalistconfirmstothetreerepresentation
(define tree? (lambda (t)
((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? ‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ()))) => #t
Inorder Traversal
• Inorder traversal on a binary search tree will produce a sorted list
(define inorder (lambda (t)
(append (inorder (cadr t))
(cons (car t) (inorder (caddr t)))) )))
(inorder ‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ()))) ;(5 31 73 83 97 101)
(inorder ‘(73 (31 (5 () ()) ()) (101 (83 () (97 () ()))
=> (5 31 73 83 97 101)
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
(insert-BST (caddr tree) value)))))
(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)
((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)
((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) )))
(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 () ())))
Scheme: Functional Programming
• Treerepresentations • Binarysearchtrees
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com