haskell代写: List Representation and List Processing in the Style of LISP

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