4/10/2018 Lab05.Solution
Lab Five Solution: List Representation and List Processing in the Style of LISP
You are allowed (and in fact encouraged) to work with others in developing your solutions to these problems! For the rest of the problems in the homework, you must work individually. You may only collaborate on the lab problems!
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 1/15
4/10/2018 Lab05.Solution
Problem One (10 pts) Basic Lisp-Style Lists
The first language to present functional programming with lists implemented as linked lists was LISP, which stands for LISt Processing language. The basic ideas should be familiar from CS 111 and CS 112, but we have to get the basic notations straight. Lists are constructed from “cons cells” which are simply nodes in a singly- linked list which do not contain data, but contain pointers to data and the rest of the list:
We will represent these in MyPython using tuples, as usua, using ‘nil’
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 2/15
4/10/2018 Lab05.Solution
Lists can be nested recursively:
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 3/15
4/10/2018 Lab05.Solution
The following code provides the primitives for creating and doing basic manipulation of lists in this style.
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 4/15
4/10/2018 Lab05.Solution
In [2]:
# Basic primitives for manipulating Lisp-style lists out of "cons" cells (tuples).
# The empty list:
nil = ‘nil’
# the preferred way to create a list
def cons(a,b):
return (‘cons’,a,b)
# extract the first component of the list
def first(L): (_,a,b) = L
return a
# extract the rest of the list
def rest(L): (_,a,b) = L
return b
# An atom is the basic element which is not itself a list, we will use o
nly integers:
def is_atom(a):
return type(a) == int # could add other types of literals
def is_list(L):
return type(L) == tuple and L[0] == ‘cons’
def is_empty(L): return L == nil
# Pretty printing of lists in the Python style:
def list_to_string(L): if L == nil:
return “[]” elif is_atom(L):
return str(L)
return “[” + lts_helper(L)
def lts_helper(L): if L == nil:
return “]”
elif L[2] == ‘nil’: # list with one element
return list_to_string(first(L)) + ‘]’ else:
return list_to_string(first(L)) + ‘,’ + lts_helper(rest(L)) def pprint_list(L):
print(list_to_string(L))
# examples
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 5/15
4/10/2018
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 6/15
Lab05.Solution
Simple list:
('cons', 1, ('cons', 2, ('cons', 3, ('cons', 4, 'nil'))))
[1,2,3,4]
First: 1
1
Rest:
('cons', 2, ('cons', 3, ('cons', 4, 'nil')))
[2,3,4]
Nested list:
('cons', ('cons', 4, 'nil'), ('cons', 13, ('cons', ('cons', 1, ('cons',
2, ('cons', 3, ('cons', 4, 'nil')))), ('cons', ('cons', 7, ('cons', 3,
'nil')), 'nil'))))
[[4],13,[1,2,3,4],[7,3]]
First:
('cons', 4, 'nil')
[4]
Rest:
('cons', 13, ('cons', ('cons', 1, ('cons', 2, ('cons', 3, ('cons', 4,
'nil')))), ('cons', ('cons', 7, ('cons', 3, 'nil')), 'nil')))
[13,[1,2,3,4],[7,3]]
print(“Simple list:”)
lst = cons(1,cons(2,cons(3,cons(4,nil))))
print(lst)
pprint_list(lst)
print(‘\nFirst:’)
print(first(lst))
pprint_list(first(lst))
print(‘\nRest:’)
print(rest(lst))
pprint_list(rest(lst))
print(“\nNested list:”)
nested_lst = cons(cons(4,nil),cons(13, cons(lst,cons(cons(7,cons(3,nil )),nil))))
print(nested_lst)
pprint_list(nested_lst)
print(‘\nFirst:’)
print(first(nested_lst))
pprint_list(first(nested_lst))
print(‘\nRest:’)
print(rest(nested_lst))
pprint_list(rest(nested_lst))
4/10/2018 Lab05.Solution
TODO for Problem 1
Complete the following function definitions, which should be familiar to you from CS 111 and CS 112, under the following requirements:
You may not use any assignment statements in your code (I’ve used them in the test cases, but YOU can’t use any)!
You may not use any loops, so recursion is your only option!
You may may ONLY use the functions defined above, plus normal arithmetic, and max(..) and min(…), and those you define yourself. No shortcuts!
Lists may or may not be nested (see the test cases).
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 7/15
4/10/2018 Lab05.Solution
In [52]:
# Fill in these functions such that they pass the tests
# returns the number of elements in the list at the top level
def length(L):
if is_empty(L):
return 0 else:
return 1 + length(rest(L))
# returns the number of "atoms" occurring anywhere in L
def size (L):
if is_empty(L):
return 0 elif is_atom(L): return 1
else:
return size(first(L)) + size(rest(L))
# Add all the members of L2 to a copy of L1 and return it
def append(L1,L2):
print(str(L1) + ” ” + str(L2)) if is_empty(L1):
return L2 else:
return cons(first(L1), append(rest(L1),L2))
# recursively reverse every list in L
def reverse(L):
print(‘\t’ + str(L))
if is_empty(L) or is_atom(L):
return L else:
return append( reverse(rest(L)), cons(reverse(first(L)),nil))
# generate a list of all atoms in list in order
def flatten(L):
if is_atom(L) or is_empty(L):
return L
elif is_atom(first(L)):
return cons(first(L), flatten(rest(L))) else:
return append(flatten(first(L)), flatten(rest(L)))
# Take two lists of same length, and pair up corresponding elements into
a list of two-element lists
def zip(L1,L2):
if is_empty(L1) and is_empty(L2):
return nil
elif is_empty(L1) or is_empty(L2):
return nil else:
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 8/15
4/10/2018
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 9/15
Lab05.Solution
Out[52]: In [4]:
('cons', 1, ('cons', 2, ('cons', 3, 'nil')))
('cons', 2, ('cons', 3, 'nil'))
('cons', 3, 'nil')
nil
3
nil ('cons', 3, 'nil')
2
('cons', 3, 'nil') ('cons', 2, 'nil')
nil ('cons', 2, 'nil')
1
('cons', 3, ('cons', 2, 'nil')) ('cons', 1, 'nil')
('cons', 2, 'nil') ('cons', 1, 'nil')
nil ('cons', 1, 'nil')
('cons', 3, ('cons', 2, ('cons', 1, 'nil')))
a = cons(1, cons(2,cons(3,nil))) b = cons(4,cons(5,nil)) c = cons(10,cons(9,cons(8, cons(7, cons(6,nil))))) d = cons(a,cons(b,cons(9,nil))) e = cons(c,cons(nil, cons(d,nil))) f = cons(6, cons(a, cons(-2, cons(e,nil))))
pprint_list(a) pprint_list(b) pprint_list(c) pprint_list(d) pprint_list(e) pprint_list(f)
[1,2,3]
[4,5]
[10,9,8,7,6]
[[1,2,3],[4,5],9]
[[10,9,8,7,6],[],[[1,2,3],[4,5],9]]
[6,[1,2,3],-2,[[10,9,8,7,6],[],[[1,2,3],[4,5],9]]]
In [5]:
In [6]:
# Test 1
print("Should be: 5")
print(length(c))
Should be: 5 5
# Test 2
print("Should be: 3")
print(length(e))
Should be: 3 3
return cons(cons(first(L1),cons(first(L2),nil)), zip(rest(L1), r est(L2)))
a = cons(1, cons(2,cons(3,nil))) reverse(a)
4/10/2018 Lab05.Solution
# Test 3
print("Should be: 11")
print(size(e))
In [7]:
Should be: 11 11
# Test 4
print("Should be: 16")
print(size(f))
In [8]:
In [9]:
In [10]:
In [11]:
In [12]:
In [13]:
Should be: 16 16
# Test 5
print(“Should be:\n[1,2,3,4,5]”) pprint_list(append(a,b))
Should be: [1,2,3,4,5] [1,2,3,4,5]
Should be: [10,9,8,7,6,[1,2,3],[4,5],9] [10,9,8,7,6,[1,2,3],[4,5],9]
Should be: [6,7,8,9,10] [6,7,8,9,10]
Should be: [[9,[5,4],[3,2,1]],[],[6,7,8,9,10]] [[9,[5,4],[3,2,1]],[],[6,7,8,9,10]]
Should be: [6,1,2,3,-2,10,9,8,7,6,1,2,3,4,5,9] [6,1,2,3,-2,10,9,8,7,6,1,2,3,4,5,9]
# Test 6
print(“Should be:\n[10,9,8,7,6,[1,2,3],[4,5],9]”) pprint_list(append(c,d))
# Test 7
print(“Should be:\n[6,7,8,9,10]”) pprint_list(reverse(c))
# Test 8
print(“Should be:\n[[9,[5,4],[3,2,1]],[],[6,7,8,9,10]]”) pprint_list(reverse(e))
# Test 9
print(“Should be:\n[6,1,2,3,-2,10,9,8,7,6,1,2,3,4,5,9]”) pprint_list(flatten(f))
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 10/15
4/10/2018 Lab05.Solution
# Test 10
x = cons(1,cons(2,cons(3,cons(4,nil))))
y = cons(10,cons(20,cons(30,cons(40,nil)))) print(“Should be:\n[[1,10],[2,20],[3,30],[4,40]]”) pprint_list(zip(x,y))
In [14]:
Should be:
[[1,10],[2,20],[3,30],[4,40]]
[[1,10],[2,20],[3,30],[4,40]]
Problem Two (10 pts)
In this problem you will write a series of functions to perform useful operations on nested sets. A set will be represented by a list (created from cons cells), in which there are no duplicates, and order is assumed not to matter (for example when testing for equality). This is true recursively, so the set:
[2,[3,4],[[5]]] = [[[5]],2,[4,3]] =[[[5]],2,[4,3,3]]
</pre> The last case is not one we will worry about too much. You must write the fo llowing functions, so that they pass the tests given at the end of the problem.
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 11/15
4/10/2018 Lab05.Solution
In [15]:
# If both are ints and equal, return true, if one is int and one is lis t, return false; # else check if each is a subset of the other
def equals(L1,L2):
if is_atom(L1) and is_atom(L2):
return L1 == L2
elif is_atom(L1) or is_atom(L2):
return False else: # both sets
return subset(L1,L2) and subset(L2,L1)
# See if s is a member of L, but use equals to check whether s is equal
to an element in L
def member(s,L):
if is_empty(L):
return False else:
return equals(s,first(L)) or member(s,rest(L))
# Check if each member of L1 is a member of L2 (use equals to check)
def subset(L1,L2): if is_empty(L1):
return True else:
return member(first(L1),L2) and subset(rest(L1),L2)
# If s is a member of L, return L, else return L union { s }
def insert(s,L): if member(s,L):
return L else:
return cons(s,L)
# If s is not a member of L, return L, else return copy of L fro which s
has been removed.
def delete(s,L):
if is_empty(L):
return L
elif equals(s,first(L)):
return delete(s,rest(L)) else:
return cons(first(L),delete(s,rest(L))) # Return union of L1 and L2
def union(L1,L2):
if is_empty(L1):
return L2
elif member(first(L1),L2):
return union(rest(L1),L2) else:
return cons(first(L1),union(rest(L1),L2))
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 12/15
4/10/2018
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 13/15
Lab05.Solution
# Test 1
print(“Should be:\nTrue”) print(equals(a,b))
In [16]:
In [17]:
In [18]:
[10,6,9,7] [6,7,10,9] [10,9,8,7,6] [[10,6,9,7],[6,7,10,9],9] [[6,7,10,9],[],[[10,6,9,7],[6,7,10,9],9]]
Should be: True True
Should be: False False
Should be: True True
# Test 2
print(“Should be:\nFalse”) print(equals(a,c))
# Test 3
print(“Should be:\nTrue”) print(member(a,d))
# Return intersection of L1 and L2
def intersection(L1,L2): if is_empty(L1):
return L1
elif member(first(L1),L2):
return cons(first(L1),intersection(rest(L1),L2)) else:
return intersection(rest(L1),L2)
a = cons(10,cons(6,cons(9, cons(7, nil)))) b = cons(6,cons(7,cons(10, cons(9, nil)))) c = cons(10,cons(9,cons(8, cons(7, cons(6,nil))))) d = cons(a,cons(b,cons(9,nil))) e = cons(b,cons(nil, cons(d,nil)))
pprint_list(a) pprint_list(b) pprint_list(c) pprint_list(d) pprint_list(e)
4/10/2018 Lab05.Solution
# Test 4
print(“Should be:\nTrue”) print(member(a,e))
In [19]:
# Test 5
print(“Should be:\nTrue”) print(subset(a,c))
In [20]:
In [29]: Out[29]:
In [28]:
In [22]:
In [23]:
In [24]:
Should be: True True
Should be: True True
(1, 2, 3)
Should be: False False
Should be: [[3],10,6,9,7] [[3],10,6,9,7]
Should be: [[10,6,9,7],[6,7,10,9],9] [[10,6,9,7],[6,7,10,9],9]
Should be: [9] [9]
tuple([1,2,3])
# Test 6
print(“Should be:\nFalse”) print(subset(d,e))
# Test 7
print(“Should be:\n[[3],10,6,9,7]”) pprint_list(insert(cons(3,nil),a))
# Test 8
print(“Should be:\n[[10,6,9,7],[6,7,10,9],9]”) pprint_list(insert(a,d))
# Test 9
print(“Should be:\n[9]”) pprint_list(delete(a,d))
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 14/15
4/10/2018 Lab05.Solution
# Test 10
print(“Should be:\n[10,6,7,[10,6,9,7],[6,7,10,9],9]”) pprint_list(union(a,d))
In [25]:
# Test 11
print(“Should be:\n[[6,7,10,9]]”) pprint_list(intersection(e,d))
In [26]:
Should be: [10,6,7,[10,6,9,7],[6,7,10,9],9] [10,6,7,[10,6,9,7],[6,7,10,9],9]
Should be: [[6,7,10,9]] [[6,7,10,9]]
In [47]: Out[47]: True
‘bb’ > ‘ba’
http://localhost:8888/nbconvert/html/Desktop/CS320/solution/Lab05.Solution.ipynb?download=false 15/15