module load soft/pythonThis works on all the Solaris and Linux machines. You can avoid typing the module load command by adding it to youe .cshrc file. You can start python in three ways:
pythonThis starts Python in the interactive mode. In interactive mode you type to the Python interpreter, which will read and execute your commands.
file.py
, type
python file.py. Python will read the file, execute it, and exit.
python -i file.py.
import <module_name>, any identifier (variable or function) defined in the module is placed in a namespace identical to module_name. This means that each of the identifiers has to be referenced using the notation
<module_name >.<identifier>
. For instance, if you
have a file named A.py where the variable b is defined, you can import it
into Python by typing
import Aand you use the variable b by saying
A.b
This avoids conflicts in names of variables among different modules.
from <module_name> import *. Since the identifiers are imported into the namespace of the module that does import, there is no need to use the module_name as a prefix to the identifiers. In the previous example, if you say
from A import *you can then use the variable b by simply referring to it as
b
>>> b=['a','c','k','z'] >>> b[0] # car 'a' >>> b[1:] # cdr ['c', 'k', 'z'] >>> b[-1] # last element 'z' >>> b[::2] # only elements with even index ['a', 'k'] >>> b[::-1] # reverse order ['z', 'k', 'c', 'a'] >>>c=b[:] # often used because it creates a new copy of the list >>> b[2]=['d','e'] # replaces 2nd element with list >>> b ['a', 'c', ['d', 'e'], 'z'] >>> b[1:1]=['f','g'] # inserts the new elements before item with index 1 >>> b ['a', 'f', 'g', 'c', ['d', 'e'], 'z'] >>> b[4]='z' # replaces the 4th element ['a', 'f', 'g', 'c', 'z', 'z'] >>> len(['a', 'f', 'g', 'c', ['d', 'e'], 'z']) 6 >>> b+c # append ['a', 'f', 'g', 'c', 'z', 'z', 'a', 'c', 'k', 'z'] >>> b+= c # append c to b and assign result to b >>> b ['a', 'f', 'g', 'c', 'z', 'z', 'a', 'c', 'k', 'z'] >>> 'a' in b # member True
>>> d=[[1,7],[3,8],[10,5]] >>> d[2][0] # take the 0th element of the 2nd element of the list 10
>>> a=range(7,9) >>> a [7, 8] >>> a.append(20) # attaches one element to the end of a >>> a [7, 8, 20] >>> a.extend([22]) # appends a list to a >>> a [7, 8, 20, 22] >>> a.append([30,32]) >>> a [7, 8, 20, 22, [30, 32]] >>> a.index(20) # returns the index of 20 2 >>> a.insert(3, 88) # adds element 88 at index 3 >>> a [7, 8, 20, 88, 22, [30, 32]] >>> a.pop() # returns the last element and removes it [30, 32] >>> a [7, 8, 20, 88, 22] >>> a.pop(2) # removes element at index 2 20 >>> a [7, 8, 88, 22] >>> a += a # appends a list to itself >>> a [7, 8, 88, 22, 7, 8, 88, 22] >>> a.count(8) # count number of occurrences of 8 in a 2The notation for using methods is L.method(arguments), where L is the list object, method is the operation you want (such as append. extend, pop, etc), and arguments are the arguments (if any) to the method. Many methods are mutating, which means they modify the list. For lists, the methods include:
Non-mutating methods -- they can be applied to immutable sequences
L.count(x) | returns the number of occurrences of x in L |
L.index(x) | returns the index of the first occurrence of x in L, and raises an exception if x is not in L |
L.append(x) | attaches x to the end of L |
L.extend(x) | appends all the items in x to the end of L |
L.insert(i,x) | inserts item x at index i in L |
L.remove(x) | removes the first occurrence of x in L |
L.pop(i) | returns the value of the item at index i and removes it from L. If i is missing, returns and removes the last item from L |
L.reverse() | reverses in place L |
L.sort([f]) | sorts in place the list L using f to compare the elements. If f is missing uses a default comparison function |
>>> dir(l) ['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__delslice__', '__doc__', '__eq__', '__ge__', '__getattribute__', '__getitem__', '__getslice__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__iter__', ' __le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__setslice__', '__str__', 'append', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']
def fib(n): """return a Fibonacci series up to n.""" result=[] # initialize list a, b = 0, 1 while b < n: result.append(b) a, b = b, a+b return result # return value (by default no value is returned)
for
clause and zero or more if
clauses.
The result is a list obtained by evaluating the expression in the context
of the for and if clauses that follow it. Multiple for
and
multiple if
can be used.
>>> [x*x for x in range(4)] # square elements in range [0, 1, 4, 9]This is the same as
>>> def mapsquare(lst): ... result = [] # create a list variable ... for x in lst: ... result +=[x*x] # append to it ... return result ... >>> mapsquare(range(4)) [0, 1, 4, 9]but it is more concise and easier to read. The notation += is the same as
result = result + [x*x]
where + is overloaded to
mean append or result.append([x*x]).
for
or using list comprehensions rather than as recursive
functions.
>>> [x*x for x in range(4) if x%2==0] # square the multiples of 2 [0, 4] >>> [x*x for x in range(4) if x%2==0 if x%3==0] # square the multiples of 2 and 3 [0] >>> [x*x for x in range(4) if x%2] # square the odd elements [1, 9] # note that 0 is considered False >>> [x for x in range(4)] # returns the same list [0, 1, 2, 3]Multiple
for
can be used in the same list comprehension.
The innermost for
is executed for each value of the outermost
for
. This produces something like:
>>> [x for x in range(3) for y in range(2)] [0, 0, 1, 1, 2, 2] # each value of x is repeated y timesWe can see the values of the variable y if we return tuples as in
>>> [(x,y) for x in range(3) for y in range(2)] [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]or lists as in
>>> [[x,y] for x in range(3) for y in range(2)] [[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]]If we add square brackets to the outermost
for
, the result
of the bracketed expression is returned as many times as the innermost
for
requires:
>>> [[x for x in range(3)] for y in range(2)] [[0, 1, 2], [0, 1, 2]] >>> [[0 for x in range(3)] for y in range(2)] # useful to make/initialize array [[0, 0, 0], [0, 0, 0]]
>>> str="another attempt" >>> a=[(x,str.count(x)) for x in str] # build list of tuples of char and count [('a', 2), ('n', 1), ('o', 1), ('t', 4), ('h', 1), ('e', 2), ('r', 1), (' ', 1), ('a', 2), ('t', 4), ('t', 4), ('e', 2), ('m', 1), ('p', 1), ('t', 4)]
>>> def even(x): ... """ convoluted way of defining even. In Python 0 is False, so ... when x%2 is 0, i.e. the number is even, the condition is false. ... if x%2: # when x is even x%2 is 0, i.e. False ... return False ... else: ... return True ... >>> def even(x): ... """better definition: when x%2 is False the number is even""" ... return not x%2 ... >>> def even(x): ... """better definition: checks explicitely if x%2 is 0""" ... return x%2==0 ...
>>> d=[[1,7],[3,8],[10,5]] >>> g=d[:] # make a copy >>> g.reverse() # reverse the copy >>> g [[10, 5], [3, 8], [1, 7]] >>> d # d is unchanged [[1, 7], [3, 8], [10, 5]]
>>> a=[1,2] >>> b=a >>> c=ba, b, c are bound to the same list. A change made to one variable affects all the others:
>>> a[1]=100 # this is like (set-car! (cdr a) 100) >>> a [1, 100] >>> b [1, 100] >>> c [1, 100]The assignment of a new binding to a variable does not change the list object the variable was bound to, it just rebinds the variable
>>> b=[7,8] >>> b # b is changed -- this is like (set! b (list 7 8)) [7, 8] >>> c # but c and a are not [1, 100] >>> a [1, 100]However, an augmented assignment, such as += or L.append, changes the list object, so causing changes in all the variables that are bound to it:
>>> a += [30] # change a by attaching 30 to the end of a >>> a [1, 100, 30] >>> c # c changes too! [1, 100, 30]
count=0 # this is a global counter def incf_count(x=1): # x=1 means that 1 is the default value of x """ increments the global variable count by x (1 default value)""" global count # we want to access the global variable count +=x return count
def f(y): """ Python passes variables by value (unless they are sequences or objects) so non local variables can be read but not modified""" x = 0 def g(y): x = x+y # this generates an error return x return g(y) # we can see the error when we try it >>> f(1) Traceback (most recent call last): File "This is useful if we want to create an object that keeps its own state.", line 1, in ? File "test.py", line 8, in f return g(y) File "test.py", line 6, in g x = x+y; # this generates an error UnboundLocalError: local variable 'x' referenced before assignment # we get around the problem by using a list instead of a simple variable def f(y): """ a closed variable can be modified if it is a sequence or object. Sequences and objects are passed by reference""" x = [0] # x is a list def g(y): x[0] += y # so we can modify it return x[0] return g(y)
>>> def make_accumulator(n): ... """makes an accumulator -- specify how much you want to increment """ ... acc=[n] # need to use a list to allow rewrite of the variable ... def incf(x): ... acc[0] += x ... return acc[0] ... return incf ... >>> acc1 = make_accumulator(2) 2 >>> acc1(10) 12
>>> def attach(x,y): ... x.append(y) # this modifies the variable passed for x ... return x ... >>> a=[1,2,3] >>> attach(a,33) [1, 2, 3, 33] >>> a [1, 2, 3, 33]
QUESTION 1: You are given the following two functions to attach an element to the end of a list. def attach(x,y): """attaches element y to the end of list x""" x.append(y) return x def attach2(x,y): """attaches element y to the end of list x""" x += [y] return x Fill in the answers: >>> a = [1,2,3] >>> b = [4,5] >>> attach(a,33) ......................................................... >>> a ......................................................... >>> attach2(b,55) ......................................................... >>> b ......................................................... QUESTION 2: Fill in the blanks assuming these are evaluated in sequence >>> a=[1,2] >>> b=a >>> c=b >>> a[0]=100 >>> a ......................................................... >>> b ......................................................... >>> b=[7,8] >>> b ......................................................... >>> a ......................................................... >>> a += [30] # attaches [30] to end of a >>> c .........................................................
>>> subst('a',o','nice warm day') nice worm doyHere are sone of the solutions suggested by students:
def subs(old,new,lst): """substitutes old with new in lst modifying the sequence""" counter = -1 # counter is used as index in lst for element in lst: counter += 1 if element == old: lst[counter]=new return lst def subs2(old,new,lst): """substitutes old with new in lst modifying the sequence""" for x in range(len(lst)): if lst[x]==old: lst[x]=new return lst def subs3(old,new,lst): """substitutes old with new in lst creating a new sequence""" result = [] for x in lst: if x==old: result.append(new) else: result.append(x) return resultNotice the difference between a function that creates a new sequence, and so works on immutable sequences, and a function that modifies the sequence, and so works only on mutable sequences.
key:value
, where the
elements of a pair are a (unique) key and the value associated to it.
Keys are immutable, so a string, number, or tuple of immutable things can
be used for key.dict
>>> phone_list={} # create dictionary >>> phone_list['john']=457 # add key/value >>> phone_list {'john': 457} >>> phone_list['bill']=767 # add another key/value >>> phone_list {'john': 457, 'bill': 767} >>> phone_list['john']=657 # change value >>> phone_list {'john': 657, 'bill': 767} >>> new_phones=dict([['joe',457],['mary',587],['joe',357]]) >>> new_phones # the last value is used in dictionary {'joe': 357, 'mary': 587}
>>> phone_list.items() # returns a copy of the list of items [('john', 657), ('bill', 767)] >>> phone_list.keys() # a copy of the list of keys ['john', 'bill'] >>> phone_list.values() # a copy of the list of values [657, 767] >>> phone_list.get('joe') # get value for given key >>> phone_list.get('john') 657 >>> phone_list.has_key('joe') # check if key exists False >>> for key in phone_list.keys(): ... print key, phone_list[key] ... john 657 bill 767A powerful method for dictionaries is update.
D.update(D1)
for eack key k
in
D1
, sets D[k]
equal to D1[k]
.
This allows merging dictionaries:
>>> phone_list.update(new_phones) # update phone_list with values in new_phones >>> phone_list {'mary': 587, 'john': 657, 'bill': 767, 'joe': 357} >>> phone_list.items() # returns a copy of the list of items [('mary', 587), ('john', 657), ('bill', 767), ('joe', 357)]The Methods defined on dictionaries are:
>>> dir(phone_list) ['__class__', '__cmp__', '__contains__', '__delattr__', '__delitem__', '__doc__', '__eq__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__init__', '__iter__', '__le__', '__len__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__str__', 'clear', 'copy', 'fromkeys', 'get', 'has_key', 'items', 'iteritems', 'iterkeys', 'itervalues', 'keys', 'pop', 'popitem', 'setdefault', 'update', 'values']
dict
. The advantage of this is that duplicate keys are
removed:
>>> a="this is too long" >>> [(x,a.count(x)) for x in a] [('t', 2), ('h', 1), ('i', 2), ('s', 2), (' ', 3), ('i', 2), ('s', 2), (' ', 3), ('t', 2), ('o', 3), ('o', 3), (' ', 3), ('l', 1), ('o', 3), ('n', 1), ('g', 1)] >>> d = dict([(x,a.count(x)) for x in a]) >>> d # characters and occurrences {' ': 3, 'g': 1, 'i': 2, 'h': 1, 'l': 1, 'o': 3, 'n': 1, 's': 2, 't': 2}
>>> a = 3 # reference a is created and bound to 3 3 >>> a = 4 * a # reference a is rebound to new object 12
>>> b += 3 # error, reference is not bound >>> a += 7 # the object to which referenec a is bound is modified 19
>>> a=3 # this is the first a >>> def f(a): ... a=5 # this is the second a -- it is a different a ... return a ... >>> a # the first a 3 >>> f(a) 5 >>> a # unchanged 3The same happens in Scheme:
STk> (define a 3) ; this is the first a STk> (define (f a) (set! a 5) ; this is the second a -- it is a different a a) f STk> a ; the first a 3We can see what happens when a list is passed:
>>> b=[3] # this is the first b >>> def ff(b): ... b[0]=5 # the second b- bound to the same object as the first ... return b ... >>> ff(b) [5] >>> b # b is changed [5]The same happens in Scheme:
STk> (define b (list 3)) ; this is the first b b STk> (define (ff b) (set-car! b 5) ; the second b- bound to the same object as the first b) ff STk> (ff b) (5) STk> b (5)
class BankAcct: """make a bank account using python's native class structure.""" # a class variable: one per class, not one per instance. # we will use it to keep track in the class of all the instances ListOfAccts=[] # initialization method. Executed every time an instance is created def __init__(self): print 'creating a bank acct.' self.amount = 0 # initialize to 0 amount self.ListOfAccts.append(self) # add to list of accounts def deposit(self,amt): self.amount = self.amount + amt # update amount as needed return self.amount def balance(self): return self.amountNow let's use the class:
>>> bill=BankAcct() # create an instance creating a bank acct. >>> john=BankAcct() creating a bank acct. >>> anne=BankAcct() creating a bank acct. >>> bill.balance() # use a method from the class 0 >>> bill.amount # access directly the class variable, not as clean 0 >>> bill.deposit(50) 50 >>> bill.balance() 50 >>> bill.amount 50 >>> BankAcct.ListOfAccts # this is a class variable not an instance variable [<__main__.BankAcct instance at 0x1bd260>, <__main__.BankAcct instance at 0x1bd558>, <__main__.BankAcct instance at 0x1bd648>] >>> def totalaccounts(): # compute total money in bank ... total=0 ... for x in BankAcct.ListOfAccts: ... total += x.amount ... return total ... >>> totalaccounts() 50
define
to create variables and to create
procedures.
max
.
;;; find the maximum of 3 numbers ;; this is correct but hard to read and verify because of the nested ifs (define (max_of3 x y z) (if (> x y) (if (> x z) x (if (> y z) y z)) (if (> y z) y z))) ;; this solution uses the fact tha > takes more than 2 arguments. ;; It does not work when some of the elements are the same. It can ;; be fixed by replacing > with >= (define (max_of3 x y z) (if (> x y z) x (if (> y x z) y (if (> z y x) z)))) ;; nice and easy to read, but does not handle the case of equal numbers ;; It can be fixed by replacing > with >= (define (max_of3 x y z) (cond ((and (> x y) (> x z)) x) ((and (> y x) (> y z)) y) ((and (> z x) (> z y)) z)))
;; this decomposes the problem into a simpler one - finding the max ;; of 2 numbers. It is easier to check and to extend. ;; define the max of 2 numbers -- recall max is already defined ;; but we define here to understand how to do it. (define (max x y) (if (> x y) x y)) ;; and then the max of 3 numbers (define (max_of3 x y z) (max x (max y z))) ;; this is similar to the previous one. Any reason to chose one over the ;; other? (define (max_of3 x y z) (max (max x y) z))
;; find the median of 3 numbers ;; this is easy to read, but it requires having max_of3 (define (median_of3 x y z) (cond ((= x (max_of3 x y z)) (max y z)) ((= y (max_of3 x y z)) (max x z)) ((= z (max_of3 x y z)) (max x y)))) ;; same as above. Short, easy to read but a bit convoluted, requires max_of3. (define (median_of3 x y z) (- (+ x y z) (max_of3 x y z) (min_of3 x y z))) ;; this uses the same idea as for max_of3 and computes min and max of ;; 2 numbers to build the solution (define (median_of3 x y z) (min (max x y) (min (max y z) (max z x))))
low
to high
, where low
is less or
equal to high
. In the case low=high
add the
number to itself.(define (sumrange low high) (cond ((= low high) high) (else (+ low (sumrange (1+ low) high)))))where
1+
is a predefined procedure that adds 1 to its
argument.(define (sumrange low high) (cond ((= low high) high) (else (+ (sumrange low (1- high)) high))))where
1-
is a predefined procedure that subtracts 1 from its
argument.(define (sumrange low high) (cond ((= low (- high 1) (+ low high)) ;; this is used only when the two arguments are equal ((= low high) (+ low high)) (else (+ low (sumrange (1+ low) high))))))
(define (sumrange low high) (cond ((= low high) high) (else (+ low (sumrange (1+ low) high)))))If the range is huge, there are many recursive calls and a lot of stack space is needed. Can we write this program differently?
Here are the files John used in during his lectures.
STk> (trace sumrange) STk> (sumrange 2 6) .. -> sumrange with low = 2, high = 6 .... -> sumrange with low = 3, high = 6 ...... -> sumrange with low = 4, high = 6 ........ -> sumrange with low = 5, high = 6 .......... -> sumrange with low = 6, high = 6 .......... <- sumrange returns 6 ........ <- sumrange returns 11 ...... <- sumrange returns 15 .... <- sumrange returns 18 .. <- sumrange returns 20 20
(define (sumrange low high) (define (sum-iter a low) (if (= low high) (+ a high) (sum-iter (+ a low) (1+ low)))) (sum-iter 0 low))This procedure uses a nested procedure, sum-iter to do the iteration. The parameter a is used to accumulate the partial sum. The internal procedure sum-iter uses the value of high from the enclosing environment.
(define (sumrange low high) (sum-iter 0 low high)) (define (sum-iter a low high) (if (= low high) (+ a high) (sum-iter (+ a low) (1+ low) high)))We can see what happens while computing by tracing the procedures:
STk> (trace sumrange) sumrange STk> (trace sum-iter) sum-iter Tk> (sumrange 2 6) .. -> sum-iter with a = 0, low = 2, high = 6 .... -> sum-iter with a = 2, low = 3, high = 6 ...... -> sum-iter with a = 5, low = 4, high = 6 ........ -> sum-iter with a = 9, low = 5, high = 6 .......... -> sum-iter with a = 14, low = 6, high = 6 .......... <- sum-iter returns 20 ........ <- sum-iter returns 20 ...... <- sum-iter returns 20 .... <- sum-iter returns 20 .. <- sum-iter returns 20 20
Try solving Exercise 1.16 (page 46), Exercise 1.17 (page 46), Exercise 1.25 (page 55), and Exercise 1.26 (page 55).
(define (sum_l l) (if (null? l) () (+ (car l)(sum_l (cdr l)))))
(let ((x 1) (y 2)) (+ x y))is equivalent to
((lambda (x y) (+ x y)) 1 2)
(define (my-map fn l) (if (null? l) () (cons (fn (car l))(my-map fn (cdr l))))) (define (double-l l) (my-map (lambda (x) (* 2 x)) l)) (define (inc-l l) (my-map 1+ l))and do
STk> (double-l (list 3 4 9)) (6 8 18) STk> (inc-l (list 5 3 8)) (6 4 9) STk> (my-map 1+ (list 5 3 8)) (6 4 9)map is used so many times, that it is already defined. map is more general. It accepts a function of more than 1 argument and as many lists as the number of arguments of the function. The lists have to have the same length. For instance
STk> (map + (list 1 2 3) (list 10 20 30)) (11 22 33)
(define (filter pred l) (cond ((null? l) ()) ((pred (car l)) (cons (car l) (filter pred (cdr l)))) (else (filter pred (cdr l)))))So, we can write things such as
STk> (filter even? (list 3 4 89 6 5)) (4 6) STk> (filter (lambda (x) (= (remainder x 3) 0)) (list 25 3 5 9 33))) (3 9 33)
;; combiner is a procedure of two args that combines the elements of the list ;; null-value specifies what value to use when the elements of the list run out. (define (accumulate combiner l null-value) (if (null? l) null-value (combiner (car l) (accumulate combiner (cdr l) null-value))))We can write things such as
STk> (accumulate + (list 1 2 3) 0) 6 STk> (accumulate * (list 2 6) 1) 12
STk> (double-odd (list -3 8 -1 4 5)) (-6 -2 10) STk> (double-odd (list -2 2 4)) () STk> (double-odd (list -1 3)) (-2 6)Do the following steps:
map |
filter |
accumulate |
(define (filter pred lst) (cond ((null? lst) ()) ((pred (car lst)) (cons (car lst) (filter pred (cdr lst)))) (else (filter pred (cdr lst)))))To generate a linear iterative process, we need to replace (cons (car lst) (filter pred (cdr lst))) with a call to filter and pass the partial result of the computation as an additional argument.
(define (filter pred lst) (filter-i pred lst ())) (define (filter-i pred lst result) (cond ((null? lst) result) ((pred (car lst)) (filter-i pred (cdr lst) (cons (car lst) result))) (else (filter-i pred (cdr lst) result))))We can see how this works by tracing:
STk> (trace filter-i) filter-i STk> (filter odd? '(2 1 5)) .. -> filter-i with pred = #[subr odd?], lst = (2 1 5), result = () .... -> filter-i with pred = #[subr odd?], lst = (1 5), result = () ...... -> filter-i with pred = #[subr odd?], lst = (5), result = (1) ........ -> filter-i with pred = #[subr odd?], lst = (), result = (5 1) ........ <- filter-i returns (5 1) ...... <- filter-i returns (5 1) .... <- filter-i returns (5 1) .. <- filter-i returns (5 1) (9 5 1)The result is in reverse order! this is because every time we find an element which satisfies the filter, we "push" it in front of the resulting list. Think of cons as an operation that pushes something on the top of a stack. The first element that satisfies the filter is the first to be pushed, so it ends up being the one at the bottom of the stack.
(define (filter-i pred lst result) (cond ((null? lst) result) ((pred (car lst)) (filter-i pred (cdr lst) (cons result (car lst)))) (else (filter-i pred (cdr lst) result))))We end up with something that is not a list:
STk> (trace filter-i) filter-i STk> (filter odd? '(2 1 5)) .. -> filter-i with pred = #[subr odd?], lst = (2 1 5), result = () .... -> filter-i with pred = #[subr odd?], lst = (1 5), result = () ...... -> filter-i with pred = #[subr odd?], lst = (5), result = (() . 1) ........ -> filter-i with pred = #[subr odd?], lst = (), result = ((() . 1) . 5) ........ <- filter-i returns ((() . 1) . 5) ...... <- filter-i returns ((() . 1) . 5) .... <- filter-i returns ((() . 1) . 5) .. <- filter-i returns ((() . 1) . 5) ((() . 1) . 5)So, let's go back to our earlier definition and reverse the result. There is a predefined procedure,<reverse, to reverse a list. We can call reverse here
(define (filter pred lst) (reverse (filter-i pred lst ())))or here
(define (filter-i pred lst result) (cond ((null? lst) (reverse result)) ((pred (car lst)) (filter-i pred (cdr lst) (cons result (car lst)))) (else (filter-i pred (cdr lst) result))))
(define (count-leaves tree) (cond ((null? tree) 0) ; null value ((not (pair? tree)) 1) ; got one element (else (+ (count-leaves (car tree)) ; count the elements in the car (count-leaves (cdr tree)))))) ; and the ones in the cdrIf instead we want to add the elements in a tree, the pattern is the same, with small changes:
(define (sum-tree tree) (cond ((null? tree) 0) ; null value ((not (pair? tree)) tree) ; add one element (else (+ (sum-tree (car tree)) ; add the elements in the car (sum-tree (cdr tree)))))) ; and the ones in the cdrTo make a copy of tree:
(define (copy-tree tree) (cond ((null? tree) ()) ; null value ((not (pair? tree)) tree) ; reached a leaf (else (cons (copy-tree (car tree)) ; copy the car (copy-tree (cdr tree)))))) ; and the cdrIf we want to find the largest element in a tree (assuming at least one element is positive):
(define (max-tree tree) (cond ((null? tree) 0) ; null value ((not (pair? tree)) tree) ; reached a leaf (else (max (max-tree (car tree)) ; the max of the elements in car (max-tree (cdr tree)))))) ; and of the ones in cdr
(define (subsets s) (if (null? s) (list ()) (let ((rest (subsets (cdr s)))) (append rest (map ??? rest))))) and the following traces of the complete procedure: STk> (subsets (list 2)) .. -> subsets with s = (2) .... -> subsets with s = () .... <- subsets returns (()) .. <- subsets returns (() (2)) (() (2)) STk> (subsets (list 1 2)) .. -> subsets with s = (1 2) .... -> subsets with s = (2) ...... -> subsets with s = () ...... <- subsets returns (()) .... <- subsets returns (() (2)) .. <- subsets returns (() (2) (1) (1 2)) (() (2) (1) (1 2))Study the traces and look at the difference between
STk> (subsets (list 2)) (() (2)) STk> (subsets (list 1 2)) (() (2) (1) (1 2))1. Mark in the list above the part that corresponds to (subsets (list 2)). 2. Write the rest of the list above after removing the elements that correspond to (subsets (list 2)). 3. Compare the result of question 2 with the result of question 1. Explain how do the two lists differ. 4. Now you should we able to complete the missing code:
(define (subsets s) (if (null? s) (list ()) (let ((rest (subsets (cdr s)))) (append rest (map _______________________________ rest)))))
(define (double-tree tree) (if (pair? tree) (map (lambda (x) (double-tree x)) tree) (* 2 tree)))
(define (tree-map proc tree) (map (lambda (x) (if (pair? x) (tree-map proc x) (proc x))) tree))And now we can simply define
(define (double-tree tree) (tree-map (lambda (x) (* 2 x)) tree)) (define (square-tree tree) (tree-map square tree)) ; assume square is defined
(define (my-append seq1 seq2) (accumulate cons seq2 seq1))
STk> (define bill 'tod) bill STk> bill tod STk> (define john bill) john STk> john bill
(define (accumulate-n op init seqs) (if (null? (car seqs)) () (cons (accumulate op init ??) (accumulate-n op init ??))))It should work like this:
STk> (accumulate-n + 0 '((1 2 3) (4 5 6))) (5 7 9)
STk< (define m (make-tree 6 () ())) m STk> m (6 () ())
STk> (adjoin-tree 5 (adjoin-tree 42 m)) (6 (5 () ()) (42 () ())) STk> (adjoin-tree 0 (adjoin-tree 5 (adjoin-tree 42 m))) (6 (5 (0 () ()) ()) (42 () ())) STk> (adjoin-tree 5 (adjoin-tree 42 (adjoin-tree 0 m))) (6 (0 () (5 () ())) (42 () ()))Even if the set has the same elements in all cases the tree might differ depending on the order in which the elements are inserted into it. If the elements are inserted in order, the tree is completely unbalanced. An unbalanced tree is of limited use, since the search time is proportional to the depth of the tree and an unbalanced tree is deeper than an equivalent balanced one.
;; all children on left branch STk> (adjoin-tree 0 (adjoin-tree 5 (adjoin-tree 6 (make-tree 42 ()())))) (42 (6 (5 (0 () ()) ()) ()) ()) ;; all children on right branch STk> (adjoin-tree 42 (adjoin-tree 6 (adjoin-tree 5 (make-tree 0 ()())))) (0 () (5 () (6 () (42 () ()))))
(define (make-unordered-set lst) (define (empty) (null? lst) ) (define (count) (length lst)) (define (element-of-set? x set) (cond ((null? set) #f) ((eqv? (car set) x) #t) (else (element-of-set? x (cdr set))))) (define (dispatch op) (cond ((eq? op 'empty?) (empty)) ((eq? op 'count) (count)) ((equal? op 'element-of-set?) (lambda (el) (element-of-set? el lst))) (else "unknown op"))) dispatch) (define s1 (make-unordered-set (list 1 2 3)))
STk> (s1 'empty?) #f STk> (s1 'count) 3
STk> (s1 'element-of-set?) #[closure ...]When we get back a procedure #[closure..] in general it means we have to compute the value of the procedure, perhaps passing additional argument(s), as here:
STk> ((s1 'element-of-set?) 6) #f STk> ((s1 'element-of-set?) 2) #t
(define (make-unordered-set2 lst) (define (empty lst) (null? lst) ) (define (count lst) (length lst)) (define (element-of-set? x set) (cond ((null? set) #f) ((eqv? (car set) x) #t) (else (element-of-set? x (cdr set))))) (define (dispatch op) (cond ((eq? op 'empty?) (empty lst)) ((eq? op 'count) (count lst)) ((equal? op 'element-of-set?) (lambda (el) (element-of-set? el lst))) (else "unknown op"))) dispatch)
(define (make-unordered-set3 lst) (define (empty) (null? lst) ) (define (count) (length lst)) (define (helper-element-of-set? x lst) (cond ((null? lst) #f) ((eqv? (car lst) x) #t) (else (helper-element-of-set? x (cdr lst))))) (define (element-of-set? x) (helper-element-of-set? x lst)) (define (dispatch op) (cond ((eq? op 'empty?) empty ) ((eq? op 'count) count ) ((eq? op 'element-of-set?) element-of-set? ) (else "unknown op"))) dispatch)
STk> (define s1 (make-unordered-set3 (list 1 2 3))) s1 STk> (s1 'count) #[closure arglist=() 743c8]What's happening? when the message count is received dispatch returns the procedure count, not its value. We can get its value by doing this:
STk> ((s1 'count)) 3and similarly
STk> ((s1 'element-of-set?) 2) #t STk> ((s1 'element-of-set?) 5) #f
(define (make-unordered-set4 lst) (define (empty) (null? lst) ) (define (count) (length lst)) (define (element-of-set? x) (member x lst)) (define (dispatch op) (cond ((eq? op 'empty?) empty ) ((eq? op 'count) count ) ((eq? op 'element-of-set?) element-of-set? ) (else "unknown op"))) dispatch)
STk> (define s1 (make-unordered-set4 (list 1 2 3))) s1 STk> ((s1 'element-of-set?) 2) (2 3) STk> ((s1 'element-of-set?) 5) #fsince member is not a predicate [did you notice that the name does not end with ?]. We can still use the procedure in the same way as before because anything different than #f is considered true:
STk> (let ((rest ((s1 'element-of-set?) 2))) (if rest (cdr rest) "notfound")) (3) STk> (let ((rest ((s1 'element-of-set?) 5))) (if rest (cdr rest) "notfound"))) "notfound"
(define (make-set-1 lst) (define (make-set-2 lst) (define (el-of-set x) (define (el-of-set x) (member x lst)) (member x lst)) (define (dispatch op) (define (dispatch op) (cond ((eq? op 'empty?) (cond ((eq? op 'empty?) (null? lst)) null?) ((eq? op 'element-of) ((eq? op 'element-of) (lambda (x)(el-of-set x))) el-of-set) (else "unknown op"))) (else "unknown op"))) dispatch) dispatch)and the following definitions:
(define set1 (define set2 (make-set-1 (list 1 7 9 3))) (make-set-2 (list 1 7 9 3)))Recall that (member el lst) returns the list starting at el if el is in the list and #f otherwise. Write Scheme expressions to:
;; use a global variable -- bad choice (define balance 100) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) ;; use a let and a lambda -- problemL we cannot create multiple copies (define new-withdraw (let ((balance 100)) (lambda (amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds"))))
(define (make-counter) (let ((counter 0)) (define (dispatch) (set! counter (1+ counter)) counter) dispatch)) STk> (define c1 (make-counter)) STk> (c1) 1 STk> (c1) 2The second solution takes two messages, one to increment the counter and one to return its value. This will allow reading the value of the counter without changing it.
(define (make-counter2) (let ((counter 0)) (define (dispatch m) (cond ((eq? m 'value) counter) ((eq? m 'inc) (set! counter (1+ counter)) counter) (else "error -- unknown message"))) dispatch)) STk> (define c2 (make-counter2)) STk> (c1 'inc) 1 STk> (c1 'inc) 2 STk> (c1 'value) 2
STk> (replace 'x '8 '(f x (+ y (f 1 x)))) (f 8 (+ y (f 1 8))) STk> (replace 'like 'dislike '(i (do not (like scheme)))) (i (do not (dislike scheme)))Here are two solutions:
(define (replace old new lst) (cond ((null? lst) ()) ((not (pair? lst)) (if (eq? lst old) new lst)) (else (cons (replace old new (car lst)) (replace old new (cdr lst)))))) (define (replace old new lst) (map (lambda (x) (cond ((not (pair? x)) (if (eq? x old) new x)) (else (replace old new x)))) lst))
STk> (remove-2nd! '(a cold happy easter is coming)) (a happy easter is coming) STk> (remove-2nd! '(enjoy it)) (enjoy)Could you write a procedure to remove the first element of list? explain why or why not
Here is a solution that modifies the data structure (note the ! at the end of the procedure name).
(define (remove-2nd! lst) (set-cdr! lst (cddr lst)) lst)The figure shows the environment after the following:
STk> (define a '(a cold happy easter is coming)) a STk> (remove-2nd! a) (a happy easter is coming) STk> (remove-2nd! a) (a easter is coming)
(define (remove-1st! lst) (set-car! lst (cadr lst)) (remove-2nd! lst))or directly
(define (remove-1st! lst) (set-car! lst (cadr lst)) (set-cdr! lst (cddr lst)) lst)
set-car!
and set-cdr!
.
To understand how to write procedures to modify the data structure, make
a graphical representation of it, mark on it the pointers that need
to be changed, and write the corresponding scheme expression for
each change. Make sure your procedures are correct when the queue is
empty and when it becomes empty. You'll see in the procedures in the
textbook two cases, one for the empty queue and another for a non empty
queue. Try using ~boley/stk/runenvdraw to visualize the objects.