In this example, we prove that the length of the list [10, [12, [14,[]]]] is 3.
At each step, we pop an element from the front of the list and at the same time, increase the count by 1 (the count starts at 0). When the list is empty, we are done counting.
For instance, the following:
length of remaining stack [ 10, [ 12, [ 14, [ ] ] ] ] with count 0
is equal to:
length of remaining stack [ 12, [ 14, [ ] ] ] with count 1
which is equal to:
length of remaining stack [ 14, [ ] ] with count 2
which is equal to:
length of remaining stack [ ] with count 3
which is finally equal to 3
Quiz (1 point)
- length of stack xs = length of remaining stack xs with count 0
- length of remaining stack [ x, y ] with count count = length of remaining stack y with count (count + 1)
- 0 + 1 = 1
- length of remaining stack [ x, y ] with count count = length of remaining stack y with count (count + 1)
- 1 + 1 = 2
- length of remaining stack [ x, y ] with count count = length of remaining stack y with count (count + 1)
- 2 + 1 = 3
- length of remaining stack [ ] with count count = count
if 0 + 1 = 1, then length of remaining stack [ 12, [ 14, [ ] ] ] with count (0 + 1) = length of remaining stack [ 12, [ 14, [ ] ] ] with count 1
if 1 + 1 = 2, then length of remaining stack [ 14, [ ] ] with count (1 + 1) = length of remaining stack [ 14, [ ] ] with count 2
if 2 + 1 = 3, then length of remaining stack [ ] with count (2 + 1) = length of remaining stack [ ] with count 3
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
then a = c
Please write your proof in the table below. Each row should contain one claim. The last claim is the statement that you are trying to prove.