• Which pairs of lists are equal?
[1, 2, 3] vs. [2, 1, 3]
Not Equal: Same number of elements, but different sequence
[1, 1, 2] vs. [1, 2]
Not Equal: Different number of elements
[1, [2, 3] ] vs. [1, 2, 3]
Not Equal: Different number of elements (2 vs. 3)
[1, [2, [3] ] ] vs. [1, 2, 3]
Not Equal: Different number of elements (2 vs. 3)
•• Execute the equality testing algorithm on the following two lists: [1, [2, 3], 4], and [1, [2], [3, 4]].
To test equality of two lists: a. If both lists are empty, the two lists are equal.
Not True: We can proceed
b. If one list is empty, the two lists are not equal.
Not True: We can proceed
c. If the first elements of the lists are unequal, then the lists are not equal.
Not True: 1 == 1, We can proceed
d. The answer to the equality of the two lists is the same as the answer to whether the rests of the two lists are equal.
Take the rests of the two lists ( [[2,3],4] and [[2],[3,4]] ) and apply steps a-c.
a. Are both lists empty? No. Proceed
b. Is only one list empty? No. Proceed
c. Are the first elements of the lists unequal? Yes. [2,3] is not equal to [2].Therefore the lists are unequal.
••• Although lists are not the same as sets, lists can be used to represent sets. We simply ignore the ordering and possibility of duplication in the lists when thinking of them as sets. Present an equality testing algorithm for two sets represented as lists.
• What is the length of the list [1, [2, 3], [4, 5, 6] ]?
[ 1, [2,3] , [4, 5, 6] ]
The length of a list is determined by the number of elements at its top level. Each element is represent above by a different color. The answer then is 3.
•• For all possible pairs of pattern vs. list below, which patterns match which lists, and what bindings are defined as a result of a successful match? For those pairs that don't match, indicate why.
| patterns | lists | matches | ||
| A | [F | R] | 1 | [1, 2, 3] | A-> 1,2,3,4,5,6 |
| B | [F, S | R] | 2 | [1, [2, 3] ] | B-> 1,2,3,4,5,6 |
| C | [F, S, T] | 3 | [ [1], 2, 3] | C-> 1,3,4,6 |
| D | [ [F], S] | 4 | [1, 2 | [3] ] | None |
| E | [ [F, S] | R] | 5 | [ [1, 2], 3] | E-> 5 |
| F | [F, S, T | R] | 6 | [1, 2, [3, 4] ] | F-> 1,3,4,6 |
Explanation
Patterns C and F both require at least three elements. Lists 2 and 5 only have two elements, so they don't work.
Pattern D requires a list of two elements whose first element is another list of exactly one element. None of the given lists satisfy this.
Pattern E requires a list whose first element is another list with exactly two elements. Only List 5 satisfies this.
•• For the patterns above, give a word description for the lists which they match.
| patterns | description |
| [F | R] | A list of at least one element |
| [F, S | R] | A list of at least two elements |
| [F, S, T] | A list of at exactly three elements |
| [ [F], S] | A list of two elements, the first of which is a list of exactly 1 element |
| [ [F, S] | R] | A list such that the first element is a list of exactly 2 elements |
| [F, S, T | R] | A list of at least 3 elements |
••• Give an algorithm for determining whether a pattern matches a list. It should be something like the equality checking algorithm.
| Return |