Purpose
The goal of this part of Problem Set 1 is to explore our constructive recursive definition of Natural Numbers. The programs you will write will be similar to both "definitions" and "proofs", but as executable code. (Of course, one should be very careful in considering a "program" to be a "proof", especially without proving the program is correct.)
We will use Python strings to represent our Natural Numbers. The main point of this is to show that the "0" and "S" used in the definition are just symbols: we only use string concatenation, extraction, and comparison to build our Natural Number represetation. Of course, this is a ridiculously silly way to represent Natural Numbers if we were actually doing computations on them (especially as Python already provides a built-in integer datatype, which could be naturally used to approximate the Natural Numbers).
def makeZero():
return '🍩'
def isZero(n):
return n == '🍩'
def makeSuccessor(n):
return '+' + n # String concatenation
def getPredecessor(n):
assert n[0] == '+' # must be a S(p)
return n[1:] # returns the rest of the string
(feel free to replace the emojis we used to your favorites, but be wary of multi-byte unicode characters!)
makeZero()
'🍩'
makeSuccessor(makeSuccessor(makeZero()))
'++🍩'
assert(isZero(makeZero()))
assert(not isZero(makeSuccessor(makeZero())))
assert(isZero(getPredecessor(makeSuccessor(makeZero()))))
zero = makeZero()
one = makeSuccessor(zero)
one
'+🍩'
print(getPredecessor(one))
🍩
Here's a definition of equality using our Natural Numbers from Class 2.
Note that we could have just defined equality using Python string equality, but that would be tied to our string representation and assume we know what Python's string equality does. Although we are using strings for our representation now, we don't want to rely on anything other than the makeZero, isZero, makeSuccessor and getPredecessor functions we defined.
def equalNumbers(n, m):
"""Returns true iff n and m represent the same number."""
if isZero(n):
return isZero(m)
else:
if isZero(m):
return False
else:
return equalNumbers(getPredecessor(n), getPredecessor(m))
two = makeSuccessor(one)
three = makeSuccessor(two)
four = makeSuccessor(three)
assert(equalNumbers(zero, zero))
assert(not equalNumbers(one, zero))
assert(equalNumbers(four, four))
assert(not equalNumbers(four, three))
assert(not equalNumbers(three, four))
Problem J1. Define a function addNumbers that takes as input two Natural Numbers (as represented here) and returns a Natural Number that represents the sum of the two inputs.
def addNumbers(a, b):
"""Takes two Natural Numbers as input, and outputs a
Natural Number that represents their sum."""
pass # fill in with your code for Problem J1
# Here are some examples to test your addNumbers function. None of the assertions should fail.
assert(equalNumbers(addNumbers(two, zero), two))
assert(equalNumbers(addNumbers(zero, two), two))
assert(equalNumbers(addNumbers(one, one), two))
assert(equalNumbers(addNumbers(two, two), four))
print ("All tests passed!")
Problem J2. Define a function greaterNumber that takes as input two Natural Numbers (as represented here) and returns a Boolean that denotes whether the first input is greater than the second.
def greaterNumber(a, b):
"""Takes two Natural Numbers as input, and outputs a Boolean indicating
if the number represented by the first input is greater than (>) the
number represented by the second."""
pass # fill in your code for Problem J2
# Here are some examples to test your greaterNumber function. None of the assertions should fail.
assert(greaterNumber(four, three))
assert(not greaterNumber(addNumbers(two, zero), two))
assert(not greaterNumber(addNumbers(zero, zero), two))
assert(not greaterNumber(four, four))
assert(greaterNumber(addNumbers(two, three), four))
print ("All tests passed!")
Next, we explore a recursive constructive definition of trees.
We will say that a Tree is either the empty tree, which we will represent with an acorn: '🌰', or it will be a pair of Trees where the first element of the pair is the left branch and the second element of the pair is the right branch.
def makeEmptyTree():
"""Returns the empty tree."""
return '🌰'
def isEmpty(t):
"""Takes a Tree as input, and outputs a Boolean indicating if the input is
the empty tree."""
return t == '🌰'
def makeBranchedTree(l, r):
"""Takes two Trees as inputs, and outputs a Tree whose left branch is the
first input, and whose right branch is the second input."""
# Python note: this makes a tuple, which is essentially an immutable list.
return (l, r)
def getLeftBranch(t):
"""Takes a non-empty Tree as input, and outputs the left branch of that Tree.
(Note that this is a partial function. It is not defined for the empty tree,
and fails with an error on that input.)"""
assert(not isEmpty(t))
return t[0]
def getRightBranch(t):
"""Takes a non-empty Tree as input, and outputs the right branch of that Tree."""
assert(not isEmpty(t))
return t[1]
We can make a few example trees.
emptyTree = makeEmptyTree()
print(emptyTree)
fullHeight1 = makeBranchedTree(emptyTree, emptyTree)
fullHeight2 = makeBranchedTree(fullHeight1, fullHeight1)
print(fullHeight2)
fullHeight3 = makeBranchedTree(fullHeight2, fullHeight2)
unbalancedHeight4 = makeBranchedTree(fullHeight1, fullHeight3)
print(unbalancedHeight4)
🌰
(('🌰', '🌰'), ('🌰', '🌰'))
(('🌰', '🌰'), ((('🌰', '🌰'), ('🌰', '🌰')), (('🌰', '🌰'), ('🌰', '🌰'))))
Problem J3. Define treeSize, treeHeight, and leafCount functions which that all take a single Tree as their input, and output an int (the regular Python integer type, not our (un)Natural Number type from the earlier problems) that represents the total number of nodes in the tree, the height of the tree, and the total number of leaves in the tree respectively. You may use standard int operations including +, -, *, <, etc.).
(Hint: a leaf is a Tree whose children are both empty trees, so it may be helful to also write an isLeaf function.)
def treeSize(t):
"""Takes a Tree as input, and outputs an int representing the total number of nodes in the tree."""
pass # replace with your code
# Some tests for treeeSize
assert(treeSize(emptyTree) == 0)
assert(treeSize(fullHeight1) == 1)
assert(treeSize(fullHeight2) == 3)
assert(treeSize(fullHeight3) == 7)
assert(treeSize(unbalancedHeight4) == 9)
print("Zuka Zama!")
def treeHeight(t):
"""Takes a Tree as input, and outputs the height of that tree."""
pass # replace with your code
assert(treeHeight(emptyTree) == 0)
assert(treeHeight(fullHeight1) == 1)
assert(treeHeight(fullHeight2) == 2)
assert(treeHeight(fullHeight3) == 3)
assert(treeHeight(unbalancedHeight4) == 4)
print("Wahoowa!")
def leafCount(t):
"""Takes a Tree as input, and outputs the total number of leaves of that tree."""
pass # replace with your code
assert(leafCount(emptyTree) == 0)
assert(leafCount(fullHeight1) == 1)
assert(leafCount(fullHeight2) == 2)
assert(leafCount(fullHeight3) == 4)
assert(leafCount(unbalancedHeight4) == 5)
print("Yippee!")
We can show two sets are the same size by demonstrating a bijection between the elements in these sets. Intuitively, a bijection shows two sets to be the same size --- since it is injective every input element maps to a unique output element; since it is surjective, every possible output element is mapped to by some input. Combined, these two properties cause elements to form matched pairs.
Here, we are going to show that the number of binary strings of length n is equal to 2_n_ by giving a bijection with the natural numbers up to 2_n_, i.e., by making these matched pairs. To do this, your goal is to write a function bitstringToNaturalNumber which will convert a binary string to a Natural Number (using our constructive definition from earlier in this notebook).
Your function should be a one-to-one mapping: there should be some binary string input that produces every natural number, and there should not be any two different binary string inputs that ouput the same natural number. (Note, however, that it is not necessary to assume any particular way of interpreting a bitstring as a number.)
Problem J4. Write this bitstringToNaturalNumber function.
def bitstringToNaturalNumber(binaryString):
pass
The following code checks that every bitstring of length n maps to a different natual number:
def isOneToOne(n):
allBitStrings = ['']
for i in range (n):
tempBitStrings = []
for bitstring in allBitStrings:
tempBitStrings.append(bitstring + '0')
tempBitStrings.append(bitstring + '1')
allBitStrings = tempBitStrings
allNaturals = []
for bitstring in allBitStrings:
natural = bitstringToNaturalNumber(bitstring)
if natural in allNaturals:
return False
allNaturals.append(natural)
return True
assert(isOneToOne(0))
assert(isOneToOne(1))
assert(isOneToOne(4))
print("YESSSSS!!!")
Make sure to save your completed notebook, and submit it along with your PDF file with the answer to the other problems in ps1.tex.