


Part 2 Summer 2014 Web.pdf
Part_2_Summer_2014_Web.pdf
Showing 4146 out of 53
Part 2 Summer 2014 Web.pdfPart II: Functional Pro...
Part_2_Summer_2014_Web.pdfPart II: Functional Programming with LISP
Part 2 Summer 2014 Web.pdfPart II:...
Part_2_Summer_2014_Web.pdfPart 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 (N1)'th member of
(cdr L).
84
N’th Member of a List L
•
(defun listnth (N L)
•
(cond
•
((null L) nil)
•
((zerop N) (car L))
•
(t (listnth ( 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 removefirst (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 removefirst (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 removefirst (s lst)
(if (null lst)
‘()
(if (equal (car lst) s)
(cdr lst)
(cons (car lst)
(removefirst s (cdr lst))))))
> (removefirst 'b los)
a c d e f g
> (removefirst '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 myremove (s los)
•
(if (null los)
•
'()
•
(if (equal (car los) s)
•
…
•
(cons (car los)
•
(myremove 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 myremove (s los)
•
(if (null los)
•
'()
•
(if (equal (car los) s)
•
(myremove s (cdr los))
•
(cons (car los)
•
(myremove s (cdr los))))))
Page 46
46
91
Executing Function Remove
> (myremove 'a '())
nil
> (myremove 'a '(a b c d a))
(list 'b 'c 'd)
> (myremove 'a '(b c d))
(list 'b 'c 'd)
92
Example: listappend
•
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:
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
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