``````

In [3]:

def is_empty(xx):
assert type(xx) is list, "Argument to 'is_empty' was not a list"
return len(xx) == 0

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

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')

``````
``````

[99, 1, 2]
[1, 4, 5, 6]
True True True True
[True, True, True, True]
True
False

``````

### What You Need to Know

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)

#### Functions

`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]:

True

``````
``````

In [5]:

is_seq('a', 'ab')

``````
``````

Out[5]:

False

``````
``````

In [6]:

is_seq(42, 42)

``````
``````

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-6-f17bf97f6fa2> in <module>()
----> 1 is_seq(42, 42)

<ipython-input-2-432750efb509> in is_seq(x, y)
19
20 def is_seq(x, y):
---> 21     assert type(x) is str, 'First argument to is_equal was not a str'
22     assert type(y) is str, 'Second argument to is_equal was not a str'
23     return x == y

AssertionError: First argument to is_equal was not a str

``````
``````

In [7]:

is_empty([])

``````
``````

Out[7]:

True

``````
``````

In [8]:

is_empty([1,2]) # not really allowed

``````
``````

Out[8]:

False

``````
``````

In [9]:

is_empty(99)

``````
``````

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-9-c6af935a014b> in <module>()
----> 1 is_empty(99)

<ipython-input-2-432750efb509> in is_empty(xx)
1 def is_empty(xx):
----> 2     assert type(xx) is list, "Argument to 'is_empty' was not a list"
3     return len(xx) == 0
4

AssertionError: Argument to 'is_empty' was not a list

``````
``````

In [10]:

``````
``````

Out[10]:

1

``````
``````

In [11]:

``````
``````

Out[11]:

1

``````
``````

In [12]:

``````
``````

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-12-f30cd18eafcb> in <module>()

6     assert type(xx) is list, "Argument to 'head' was not a list"
----> 7     return xx[0]
8
9 def tail(xx):

IndexError: list index out of range

``````
``````

In [13]:

tail([1,2,3])

``````
``````

Out[13]:

[2, 3]

``````
``````

In [14]:

tail([1,2])

``````
``````

Out[14]:

[2]

``````
``````

In [15]:

tail([1])

``````
``````

Out[15]:

[]

``````
``````

In [18]:

tail([])

``````
``````

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-18-0f45faf87aa7> in <module>()
----> 1 tail([])

9 def tail(xx):
10     assert type(xx) is list, "Argument to 'tail' was not a list"
---> 11     assert len(xx) > 0, "List was empty"
12     return xx[1:]
13

AssertionError: List was empty

``````
``````

In [20]:

cons(1, [2,3])

``````
``````

Out[20]:

[1, 2, 3]

``````
``````

In [22]:

cons(1, [2])

``````
``````

Out[22]:

[1, 2]

``````
``````

In [23]:

cons(1, [])

``````
``````

Out[23]:

[1]

``````
``````

In [24]:

cons(1, cons(2, cons(3, [])))

``````
``````

Out[24]:

[1, 2, 3]

``````
``````

In [27]:

``````
``````

Out[27]:

57

``````
``````

In [28]:

``````
``````

Out[28]:

1

``````
``````

In [29]:

sub1(100)

``````
``````

Out[29]:

99

``````
``````

In [2]:

sub1(0)

``````
``````

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-2-9178622a8b6f> in <module>()
----> 1 sub1(0)

<ipython-input-1-aaba59daf732> in sub1(x)
30 def sub1(x):
31     assert type(x) is int
---> 32     assert x > 0, "Argument to 'sub1' was zero (or negative)"
33     return x - 1
34

AssertionError: Argument to 'sub1' was zero (or negative)

``````
``````

In [32]:

is_zero(9)

``````
``````

Out[32]:

False

``````
``````

In [33]:

is_zero(0)

``````
``````

Out[33]:

True

``````
``````

In [4]:

is_zero('kk')

``````
``````

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-4-34e0831c86b4> in <module>()
----> 1 is_zero('kk')

<ipython-input-3-295cbe89fc18> in is_zero(x)
34
35 def is_zero(x):
---> 36     assert type(x) is int
37     return x == 0
38

AssertionError:

``````
``````

In [5]:

is_str('hello')

``````
``````

Out[5]:

True

``````
``````

In [6]:

is_str(99)

``````
``````

Out[6]:

False

``````
``````

In [8]:

is_str(['hello'])

``````
``````

Out[8]:

False

``````
``````

In [9]:

is_num(9)

``````
``````

Out[9]:

True

``````
``````

In [10]:

is_num('9')

``````
``````

Out[10]:

False

``````
``````

In [11]:

is_num([99])

``````
``````

Out[11]:

False

``````
``````

In [35]:

is_atom(9)

``````
``````

Out[35]:

True

``````
``````

In [36]:

is_atom('bla')

``````
``````

Out[36]:

True

``````
``````

In [37]:

is_atom([])

``````
``````

Out[37]:

False

``````
``````

In [12]:

is_atom([89,90])

``````
``````

Out[12]:

False

``````
``````

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:
return is_lnums(tail(xx))
else:
return False

``````
``````

In [14]:

is_lnums([1,2,3])

``````
``````

Out[14]:

True

``````
``````

In [15]:

is_lnums([1,2,'a'])

``````
``````

Out[15]:

False

``````
``````

In [16]:

is_lnums([])

``````
``````

Out[16]:

True

``````
``````

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:
return True
else:
return is_str_mem(x, tail(l))

``````
``````

In [18]:

is_str_mem('a', ['a', 'b'])

``````
``````

Out[18]:

True

``````
``````

In [19]:

is_str_mem('a', ['b', 'a'])

``````
``````

Out[19]:

True

``````
``````

In [20]:

is_str_mem('a', ['b'])

``````
``````

Out[20]:

False

``````
``````

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:
return tail(l)
else:

``````
``````

In [26]:

remove_str_mem('a', ['a', 'b'])

``````
``````

Out[26]:

['b']

``````
``````

In [27]:

remove_str_mem('a', ['b'])

``````
``````

Out[27]:

['b']

``````
``````

In [28]:

remove_str_mem('a', ['b', 'a', 'c'])

``````
``````

Out[28]:

['b', 'c']

``````
``````

In [29]:

remove_str_mem('a', ['a', 'a'])

``````
``````

Out[29]:

['a']

``````
``````

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:

``````
``````

In [40]:

is_lat([1,2,3])

``````
``````

Out[40]:

True

``````
``````

In [41]:

is_lat([])

``````
``````

Out[41]:

True

``````
``````

In [42]:

is_lat([1,2,[]])

``````
``````

Out[42]:

False

``````
``````

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'])
# tail(l) is ['b']
return True
return is_mem(x, tail(l))

``````
``````

In [45]:

is_mem('a', ['a', 'b'])

``````
``````

Out[45]:

True

``````
``````

In [46]:

is_mem('a', ['b', 'a'])

``````
``````

Out[46]:

True

``````
``````

In [47]:

is_mem('a', ['b', 'c'])

``````
``````

Out[47]:

False

``````
``````

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:
return tail(l)
else:

``````
``````

In [55]:

remove_mem('a', ['a', 'b', 'c'])

``````
``````

Out[55]:

['b', 'c']

``````
``````

In [56]:

remove_mem('b', ['a', 'b', 'c'])

``````
``````

Out[56]:

['a', 'c']

``````
``````

In [ ]:

``````
``````

In [29]:

def is_lat(xx):
if is_empty(xx):
return True
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, []])

``````
``````

True
True
True
False

``````
``````

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'])

``````
``````

False
True
False
True

``````
``````

In [58]:

def remove_member(x, lst):
if is_empty(lst):
return []
else:
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'])

``````
``````

[]
[]
['b']
['x']
['x']
['x']
['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)):
else:
return last(tail(l))

``````
``````

In [33]:

last([1,2,3])

``````
``````

Out[33]:

3

``````
``````

In [35]:

last([])

``````
``````

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-35-bee5c42f7665> in <module>()
----> 1 last([])

<ipython-input-31-13406cf6aac7> in last(l)
4 # last([]) is error
5 def last(l):
----> 6     if is_empty(tail(l)):
8     else:

<ipython-input-3-295cbe89fc18> in tail(xx)
9 def tail(xx):
10     assert type(xx) is list, "Argument to 'tail' was not a list"
---> 11     assert len(xx) > 0, "List was empty"
12     return xx[1:]
13

AssertionError: List was empty

``````
``````

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:

``````
``````

In [39]:

firsts([[1,2], ['apple', 'pear', 'peach']])

``````
``````

Out[39]:

[1, 'apple']

``````
``````

In [40]:

``````
``````

In [59]:

def firsts(xx):
if is_empty(xx):
return []
else:
tl = tail(xx)

``````
``````

In [60]:

firsts([[1,2], [3,4]])

``````
``````

Out[60]:

[1, 3]

``````
``````

In [62]:

def insert_right(x1, x2, xx):
if is_empty(xx):
return []
else:
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]:

['a', 'x', 'b', 'c']

``````
``````

In [65]:

insert_right('a', 'x', ['a', 'b', 'c', 'a'])

``````
``````

Out[65]:

['a', 'x', 'b', 'c', 'a']

``````
``````

In [ ]:

``````