On this page you'll find a series of exercises. We'll be using Python for all the code, but not really. You barely need to know any Python at all. In fact here is all you need to know (at least about Python).
Numbers: 0, 1, 2, 3, ... (i.e., no negative numbers or decimals)
Strings: things like 'hello' and 'the cat on the mat' and the empty string ''
Booleans: True, False
Lists: [], but you can make lists (see cons below)
is_eq_str(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 of xx
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
The above functions, simple though they are, are not built into Python, so you must download a file that defins them. Download basic_functions.py.
In [1]:
from basic_functions import *
In [2]:
is_empty([1,2])
Out[2]:
In [3]:
is_empty([])
Out[3]:
In [4]:
head([1,2])
Out[4]:
In [5]:
head([1])
Out[5]:
Note that head([]) is an error since you can't find the first item in an empty list.
In [6]:
tail([1,2])
Out[6]:
In [7]:
tail([1])
Out[7]:
Note that tail([]) is an error since the tail of a list is what's left over when you remove the head, and the empty list has no head.
In [8]:
cons(1, [2,3])
Out[8]:
In [9]:
cons(1, [])
Out[9]:
In [10]:
is_num(99)
Out[10]:
In [11]:
is_num('hello')
Out[11]:
In [12]:
is_str(99)
Out[12]:
In [13]:
is_str('hello')
Out[13]:
In [14]:
is_str_eq('hello', 'hello')
Out[14]:
In [15]:
is_str_eq('hello', 'goodbye')
Out[15]:
In [16]:
add1(99)
Out[16]:
In [17]:
sub1(99)
Out[17]:
Note that sub1(0) is an error because you can't subtract 1 from 0. (Actually it is possible if you allow negative numbers, but in these exercises we will not allow such numbers.)
In [24]:
from solutions import is_list_of_strings
In [25]:
is_list_of_strings(['hello', 'goodbye'])
Out[25]:
In [27]:
is_list_of_strings([1, 'aa'])
Out[27]:
In [29]:
is_list_of_strings([])
Out[29]:
The last example, is_list_of_strings([]), might seem puzzling at first, but really it's not. Suppose you are flying into a strange island and at customs there is a sign that says "all food in your suitcase must be cooked". Then if you have a ham sanswich in your suitcase then you are ok, since ham is cooked. What about if you have no food in your suitcase? Then clearly you are also ok. This because in normal language (and in more mathematical language too) when we say "every X must be (say) big", then if there are no X's then the statment is true. In normal language it may be less clear what to do with slightly sillier examples; for example, say someone asks you "Are all the coins in your pocket quarters?" and you have no coins in your pocket. Out of politeness you might say "I have no coins in my pocket", but if they forced you to say "yes" or "no", I think you would say "yes".
Follow the pattern below:
# fill in the blanks
def is_list_of_strings(l):
if is_empty(l):
pass
else:
# do something with head(l), tail(l)
pass
Before you try it, here is a hint. You can do something magical in a function: you call yourself! For example when filling in the blanks above, a good place to try this is in the else block. In fact what you want to think about in the else block is this: assuming I've broken the list apart into it's first item (head(l)) and a list with all the other items (tail(l)) how can I figure out the answer in terms of these pieces? If the first item is not a string then we are done (the answer if false). However if the first item is a list then we know we have a list of strings if the rest of the items are all strings. So maybe we can 'cheat' and just call is_list_of_strings on the tail to answer that! And in fact you can, and it's not even cheating. In fact it's called recursion.
In [ ]: