In [3]:
def is_empty(xx):
assert type(xx) is list, "Argument to 'is_empty' was not a list"
return len(xx) == 0
def head(xx):
assert type(xx) is list, "Argument to 'head' was not a list"
return xx[0]
def tail(xx):
assert type(xx) is list, "Argument to 'tail' was not a list"
assert len(xx) > 0, "List was empty"
return xx[1:]
def cons(x, xx):
assert type(xx) is list, "Second argument to 'cons' was not a list"
return [x] + xx
def is_atom(x):
return type(x) in [int, float, bool, str]
def is_seq(x, y):
assert type(x) is str, 'First argument to is_equal was not a str'
assert type(y) is str, 'Second argument to is_equal was not a str'
return x == y
def add1(x):
assert type(x) is int
return x + 1
def sub1(x):
assert type(x) is int
assert x > 0, "Argument to 'sub1' was zero (or negative)"
return x - 1
def is_zero(x):
assert type(x) is int
return x == 0
def is_str(x):
return type(x) == str
def is_num(x):
return type(x) == int
s = [1,2]
s.insert(0,99)
print s
print cons(1, [4,5,6])
print type(1) is int,type(1.5) is float,type(True) is bool,type('gg') is str
print [is_atom(x) for x in [1,1.5,True,'gg']]
#print is_equal([1], [1])
print is_seq('a', 'a')
print is_seq('a', 'b')
Numbers: 0, 1, 2, 3, ... (i.e., no negative numbers or decimals)
Strings: '', 'a', 'b', ..., 'aa', 'ab', ...
Booleans: True
, False
Lists: []
, but you can make lists (see 'cons' below)
is_seq(x, y)
: x
and y
must both be strings; returns whether x
equals y
is_empty(xx)
: xx
must be a list; returns whether the xx
is the empty list
head(xx)
: xx
must be a non-empty list; returns the first item
tail(xx)
: xx
must be a non-empty list; returns a list with everything after the head
cons(h, tl)
: returns a list whose first item is h
and whose remaining items are the items of tl
(i.e. it put backs a list taken apart by head
and tail
)
add1(n)
: n
must be a number; returns a number one bigger than n
sub1(n)
: n
must be a number greater than zero; returns a number one less than n
is_zero(n)
: n
must be a number; returns whether n
is zero
is_str(x)
: returns whether x
is a string
is_num(x)
: returns whether x
is a number
In [4]:
is_seq('a', 'a')
Out[4]:
In [5]:
is_seq('a', 'ab')
Out[5]:
In [6]:
is_seq(42, 42)
In [7]:
is_empty([])
Out[7]:
In [8]:
is_empty([1,2]) # not really allowed
Out[8]:
In [9]:
is_empty(99)
In [10]:
head([1,2])
Out[10]:
In [11]:
head([1])
Out[11]:
In [12]:
head([])
In [13]:
tail([1,2,3])
Out[13]:
In [14]:
tail([1,2])
Out[14]:
In [15]:
tail([1])
Out[15]:
In [18]:
tail([])
In [20]:
cons(1, [2,3])
Out[20]:
In [22]:
cons(1, [2])
Out[22]:
In [23]:
cons(1, [])
Out[23]:
In [24]:
cons(1, cons(2, cons(3, [])))
Out[24]:
In [27]:
add1(56)
Out[27]:
In [28]:
add1(0)
Out[28]:
In [29]:
sub1(100)
Out[29]:
In [2]:
sub1(0)
In [32]:
is_zero(9)
Out[32]:
In [33]:
is_zero(0)
Out[33]:
In [4]:
is_zero('kk')
In [5]:
is_str('hello')
Out[5]:
In [6]:
is_str(99)
Out[6]:
In [8]:
is_str(['hello'])
Out[8]:
In [9]:
is_num(9)
Out[9]:
In [10]:
is_num('9')
Out[10]:
In [11]:
is_num([99])
Out[11]:
In [35]:
is_atom(9)
Out[35]:
In [36]:
is_atom('bla')
Out[36]:
In [37]:
is_atom([])
Out[37]:
In [12]:
is_atom([89,90])
Out[12]:
In [13]:
# is_lnums([1,2,3]) is True
# is_lnums([1,2,'ff']) is False
# is_lnums([]) is True
def is_lnums(xx):
if is_empty(xx):
return True
else:
# head(xx) and tail(xx)
# is_num(head(xx))
if is_num(head(xx)):
return is_lnums(tail(xx))
else:
return False
In [14]:
is_lnums([1,2,3])
Out[14]:
In [15]:
is_lnums([1,2,'a'])
Out[15]:
In [16]:
is_lnums([])
Out[16]:
In [17]:
# is_mem(x, l)
# is_mem('a', ['a', 'b']) is True
# is_mem('a', ['b']) is False
def is_str_mem(x, l):
if is_empty(l):
return False
else:
# head(l), tail(l)
if is_seq(head(l), x):
return True
else:
return is_str_mem(x, tail(l))
In [18]:
is_str_mem('a', ['a', 'b'])
Out[18]:
In [19]:
is_str_mem('a', ['b', 'a'])
Out[19]:
In [20]:
is_str_mem('a', ['b'])
Out[20]:
In [25]:
# remove_str_mem('a', ['a', 'b', 'c']) gives ['b', 'c']
# remove_str_mem('a', ['b', 'c']) gives ['b', 'c']
# remove_str_mem('a', ['a', 'b', 'a']) gives ['b', 'a']
def remove_str_mem(x, l):
if is_empty(l):
return []
else:
# head(l), tail(l)
if is_seq(x, head(l)):
return tail(l)
else:
return cons(head(l), remove_str_mem(x, tail(l)))
In [26]:
remove_str_mem('a', ['a', 'b'])
Out[26]:
In [27]:
remove_str_mem('a', ['b'])
Out[27]:
In [28]:
remove_str_mem('a', ['b', 'a', 'c'])
Out[28]:
In [29]:
remove_str_mem('a', ['a', 'a'])
Out[29]:
In [ ]:
In [39]:
# Do we have a listof atoms?
# Example: [1,'a', 99] : yes
# [1, []] : no
def is_lat(l):
if is_empty(l):
return True
else:
return is_atom(head(l)) and is_lat(tail(l))
In [40]:
is_lat([1,2,3])
Out[40]:
In [41]:
is_lat([])
Out[41]:
In [42]:
is_lat([1,2,[]])
Out[42]:
In [44]:
# is_mem(x, l)
# is_mem('a', ['a', 'b']) is True
# is_mem('a', ['b'])
def is_mem(x, l):
if is_empty(l):
# do something
# is_mem('a', [])
return False
else:
# do something with head(l) and tail(l)
# is_mem('a', ['a', 'b'])
# head(l) is 'a'
# tail(l) is ['b']
if is_seq(x, head(l)):
return True
return is_mem(x, tail(l))
In [45]:
is_mem('a', ['a', 'b'])
Out[45]:
In [46]:
is_mem('a', ['b', 'a'])
Out[46]:
In [47]:
is_mem('a', ['b', 'c'])
Out[47]:
In [54]:
# remove_member('a', ['a', 'b', 'c']) is ['b', 'c']
# remove_member('a', []) is []
# remove_member('a', ['a', 'b', 'a', 'c']) is ['b', 'a', 'c']
def remove_mem(x, l):
if is_empty(l):
return []
else:
if is_seq(head(l), x):
return tail(l)
else:
return cons(head(l),remove_mem(x, tail(l)))
In [55]:
remove_mem('a', ['a', 'b', 'c'])
Out[55]:
In [56]:
remove_mem('b', ['a', 'b', 'c'])
Out[56]:
In [ ]:
In [29]:
def is_lat(xx):
if is_empty(xx):
return True
elif is_atom(head(xx)):
return is_lat(tail(xx))
else:
return False
print is_lat([])
print is_lat([1])
print is_lat([1, 2])
print is_lat([1, 2, []])
In [34]:
def is_member(x, lst):
if is_empty(lst):
return False
else:
return is_str_equal(x, head(lst)) or is_member(x, tail(lst))
print is_member('a', [])
print is_member('a', ['a'])
print is_member('a', ['b'])
print is_member('a', ['b', 'a'])
In [58]:
def remove_member(x, lst):
if is_empty(lst):
return []
else:
h = head(lst)
tl = tail(lst)
if is_seq(x, h):
return tl
else:
return cons(h, remove_member(x, tl))
print remove_member('a', [])
print remove_member('a', ['a'])
print remove_member('a', ['b'])
print remove_member('a', ['a', 'x'])
print remove_member('a', ['a', 'x'])
print remove_member('a', ['x', 'a'])
print remove_member('a', ['a', 'x', 'a'])
In [31]:
# last([1,2,3]) is 3
# last([1,2]) is 2
# last([1]) is 1
# last([]) is error
def last(l):
if is_empty(tail(l)):
return head(l)
else:
return last(tail(l))
In [33]:
last([1,2,3])
Out[33]:
In [35]:
last([])
In [38]:
# firsts([[1,2], ['apple', 'pear', 'peach']]) is [1, 'apple']
# firsts([]) is []
# firsts([[99]]) is [99]
def firsts(l):
if is_empty(l):
return []
else:
return cons(head(head(l)), firsts(tail(l)))
In [39]:
firsts([[1,2], ['apple', 'pear', 'peach']])
Out[39]:
In [40]:
# add1_to_list([1,10,100]) = [2,11,101]
# add1_to_list([]) = []
In [59]:
def firsts(xx):
if is_empty(xx):
return []
else:
h = head(xx)
tl = tail(xx)
return cons(head(h), firsts(tl))
In [60]:
firsts([[1,2], [3,4]])
Out[60]:
In [62]:
def insert_right(x1, x2, xx):
if is_empty(xx):
return []
else:
h = head(xx)
tl = tail(xx)
if is_seq(h, x1):
return cons(x1, cons(x2, tl))
else:
return cons(h, insert_right(x1, x2, tl))
In [64]:
insert_right('a', 'x', ['a', 'b', 'c'])
Out[64]:
In [65]:
insert_right('a', 'x', ['a', 'b', 'c', 'a'])
Out[65]:
In [ ]: