|
|
|
Part 2 Summer 2014 Web.pdf
Part_2_Summer_2014_Web.pdf
Showing 41-46 out of 53
Part 2 Summer 2014 Web.pdf-Part II: Functional Pro...
Part_2_Summer_2014_Web.pdf-Part II: Functional Programming with LISP
Part 2 Summer 2014 Web.pdf-Part II:...
Part_2_Summer_2014_Web.pdf-Part II: Functional Programming with LISP
Page 41
41
81
Example: Computing the Power of
a Number
•
We define
x
n
as
pown(x)
:
pow0(x) = 1
pow1(x) = x = x * pow0(x)
pow2(x) = x * x = x * pow1(x)
pow3(x) = x * x * x = x * pow2(x) ...
•
We can define a recursive pattern as follows:
•
Base case:
pow(0,x) = 1
•
Inductive case:
pow(n,x) = x * pow(n-
1,x)
82
•
(defun pow (n x)
•
(if (zerop n)
•
1
•
(* x (pow (- n 1) x))))
•
> (pow 0 3)
1
> (pow 2 2)
4
Example: Computing the Power of a
Number
Page 42
42
83
N’th Member of a List L
•
Case 1: L is nil.
return nil.
•
Case 2: L is constructed by a cons.
Then L has two components: (car L) and (cdr L). There are
two subcases:
–
Case 2.1: N = 0.
The zeroth element of L is simply (car L).
–
Case 2.2: N > 0.
The N'th member of L is exactly the (N-1)'th member of
(cdr L).
84
N’th Member of a List L
•
(defun list-nth (N L)
•
(cond
•
((null L) nil)
•
((zerop N) (car L))
•
(t (list-nth (- N 1) (cdr L)))))
Page 43
43
85
Example: Removing the First
Occurrence of a Symbol from a List
•
Step 1: If the list is empty, the list with the symbol
removed is still empty.
•
(defun remove-first (s los)
•
(if (null los)
•
‘()
•
... ))
86
•
Step 2: What if the list is not empty?
1.
If the first element in the list is the symbol we want to remove
then we return the tail of the list.
(defun remove-first (s lst)
(if (null lst)
‘()
(if (equal (car lst) s)
(cdr lst)
... )))
1.
Otherwise we return a list that has that first element at the
front of what we get when we remove the symbol from the tail
of list.
Page 44
44
87
(setf los (list 'a 'b 'c 'd 'e 'f 'g))
(setf los2 empty)
(defun remove-first (s lst)
(if (null lst)
‘()
(if (equal (car lst) s)
(cdr lst)
(cons (car lst)
(remove-first s (cdr lst))))))
> (remove-first 'b los)
a c d e f g
> (remove-first 'c los2)
nil
88
Example: Remove all Occurrences
of a Symbol from a List of Symbols
•
If the list is empty, we return the empty list.
•
There are two cases to consider when the list isn't
empty.
Page 45
45
89
Function Remove all Occurrences
1.
When the symbol isn't the first member of the
list, we certainly want to do the same thing,
keep the symbol and recur.
•
(defun my-remove (s los)
•
(if (null los)
•
'()
•
(if (equal (car los) s)
•
…
•
(cons (car los)
•
(my-remove s (cdr los))))))
90
Function Remove all Occurrences
2.
When the symbol to remove is the same, we still
want to throw it away, but we must continue
removing the symbol from the result, so we recur
:
•
(defun my-remove (s los)
•
(if (null los)
•
'()
•
(if (equal (car los) s)
•
(my-remove s (cdr los))
•
(cons (car los)
•
(my-remove s (cdr los))))))
Page 46
46
91
Executing Function Remove
> (my-remove 'a '())
nil
> (my-remove 'a '(a b c d a))
(list 'b 'c 'd)
> (my-remove 'a '(b c d))
(list 'b 'c 'd)
92
Example: list-append
•
We implement a recursive version of append. Suppose
we are given two lists L1 and L2. L1 is either nil or
constructed by cons.
•
Case 1: L1 is nil.
Appending L2 to L1 simply results in L2.
•
Case 2: L1 is composed of two parts: (car L1) and (cdr
L1). If we know the result of appending L2 to (cdr L1),
then we can take this result, insert (car L1) to the front,
and we then have the list we want.
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Principles_Of_Programming_Lang
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
