Let's think about writing a definition of function length(L) that returns the length of list L. For example, length([2,4,6]) = 3 and length([ ]) = 0. It suffices to say how to compute the length of an empty list and how to compute the length of a nonempty list. Here are two facts.
(length.1) length([]) = 0 (length.2) length(L) = 1 + length(tail(L)) (when L is not empty)Here are two important observations.
These are equations just as much as the ones that you have studied in mathematics. For example, you learned that x(y + z) = xy + xz. That tells you that two expressions yield the same value for all values of the variables x, y and z. Similarly, equation length([ ]) = 0 tells you that two expressions, length([ ]) and 0, yield the same value.
As you can see, each equation can have a proviso indicating requirements for it to hold; the second equation only holds when L is not empty. The second equation tells you, for example, that length([2,4,6,8]) = 1 + length([4,6,8]), which should be clear.
The second equation can be written a little more succinctly as follows.
(length.2') length(h:t) = 1 + length(t)It is not necessary to make a note that h:t must not be empty, because it is always nonempty. (After all, h:t is a list whose head is h and whose tail is t. So it has a head and a tail. The empty list does not have a head or a tail.) Let's try an example. Substituting h = 2 and t = [4,6,8] into equation (length.2') yields
length(2:[4,6,8]) = 1 + length([4,6,8])Is that true? Well, length([4,6,8]) = 3, so the right-hand side has value 4. And, since 2:[4,6,8] = [2,4,6,8], the left-hand side is equal to length([2,4,6,8]), which is also 4.
So we have two equations about the length function. But what we really want is an algorithm to compute the length of a list. Is it reasonable to say that those two equations define an algorithm? Let's try to compute length([2,4,6]) using them. The only thing we do is replace expressions with equal expressions, using facts (length.1) and (length.2'), the definition of h:t and a little arithmetic.
length([2,4,6]) = length(2:[4,6]) since [2,4,6] = 2:[4,6]
= 1 + length([4,6]) by (length.2'), with h = 2 and t = [4,6]
= 1 + length(4:[6]) since [4,6] = 4:[6]
= 1 + (1 + length([6])) by (length.2'), with h = 4 and t = [6]
= 1 + (1 + length(6:[])) since [6] = 6:[]
= 1 + (1 + (1 + length([]))) by (length.2') with h = 6 and t = []
= 1 + (1 + (1 + 0)) by (length.1)
= 3 by arithmetic
Let's use equations to define function member(x, L), which is true if x belongs to list L. For example, member(3, [2,6,3,5]) = true and member(4, [2,6,3,5]) is false. Here are some equations. Operator 'or' is the logical or operator, the same as | | in C++.
(member.1) member(x, []) = false (member.2) member(x, h:t) = h == x or member(x,t)The first equation should be clear. The empty list does not have any members. Let's try some examples of the second equation, (member.2). According to that equation,
member(4, 2:[4,6,8]) = 4 == 2 or member(4, [4,6,8])
= false or true
= true
since we know that member(4, [4,6,8]) is true. Also,
member(2, 2:[4,6,8]) = 2 == 2 or member(2, [4,6,8])
= true or member(2, [4,6,8])
= true
Notice that we do not need to evaluate member(2, [4,6,8]) in the last example.
This is a search problem,
and the algorithm does not need
to look at the entire list when the answer is true.
Now let's write equations that define function isPrefix(A, B), which is true if list A is a prefix of list B. For example, isPrefix([1,3], [1,3,5]) is true. A list is a prefix of itself, so isPrefix([2,4,6], [2,4,6]) is true, and the empty list is a prefix of every list. Here are equations for isPrefix.
(isPrefix.1) isPrefix([], B) = true (isPrefix.2) isPrefix(A, []) = false (when A is not []) (isPrefix.3) isPrefix(h1:t1, h2:t2) = h1 == h2 and isPrefix(t1, t2)The first two equations should be evident; they say that the empty list is a prefix of every list and a nonempty list is not a prefix of an empty list. The third equation should be more obvious through an example.
isPrefix([3,5], [3,5,7,9]) = isPrefix(3:[5], 3:[5,7,9])
= 3 == 3 and isPrefix([5], [5,7,9]) by (isPrefix.3) with h1 = h2 = 3,
t1 = [5] and t2 = [5,7,9]
= true and isPrefix([5], [5,7,9])
= isPrefix([5], [5,7,9])
= isPrefix(5:[], 5:[7,9])
= 5 == 5 and isPrefix([], [7,9]) by (isPrefix.3)
= true and isPrefix([], [7,9])
= isPrefix([], [7,9])
= true by (isPrefix.1)
The concatenation function cat(A, B) glues two lists A and B together into a single list. For example,
cat([2,5,7], [3,6]) = [2,5,7,3,6].Two equations should be obvious.
(cat.1) cat([], B) = B (cat.2) cat(A, []) = AIf A is nonempty then the head of cat(A,B) is the same as the head of A. That should be evident from the example, cat([2,5,7], [3,6]) = [2,5,7,3,6]. The tail of the result is cat(tail(A), B). Look at the example above. The tail of result [2,5,7,3,6] is [5,7,3,6], which is equal to cat([5,7], [3,6]). So we get
(cat.3) cat(h:t, B) = h:cat(t, B)Notice that equation (cat.1) tells how to compute cat(A, B) when A is an empty list and equation (cat.3) tells how to compute cat(A, B) when A is not empty. That covers all possibilities, so there is no need for equation (cat.2). So the definition of cat is
(cat.1) cat([], B) = B (cat.3) cat(h:t, B) = h:cat(t, B)Let's uses those equations to compute cat([2,4], [6,8]).
cat([2,4], [6,8]) = 2:cat([4], [6,8]) by (cat.3)
= 2:(4:cat([], [6,8])) by (cat.3)
= 2:(4:[6,8]) by (cat.1)
= 2:[4,6,8] since 4:[6,8] = [4,6,8]
= [2,4,6,8] since 2:[4,6,8] = [2,4,6,8]
Let's write equations that define function evens(L), which yields a list of all members of list L that are even, preserving their order. For example, evens([2,5,6,7,9,10]) = [2,6,10]. First, an obvious equation.
evens([]) = []Now suppose that L starts with an even number. Then that even number will be the first value in the result list, and it will be followed by all even numbers in tail(L).
evens(h:t) = h:evens(t) (when h is even)Finally, if L does not begin with an even number, just ignore that number.
evens(h:t) = evens(t) (when h is odd)Putting those 3 equations together defines an algorithm for evens(L).
The following equation about cat is false. Give a counterexample that shows it is wrong. Evaluate the two sides for your counterexample and show that they are not equal.
cat(h:t, u:v) = h:(u:(cat(t, v)))Answer
The following equation about isPrefix is false. Give a counterexample that shows it is wrong. Evaluate the two sides for your counterexample and show that they are not equal.
isPrefix(h:t, L) = isPrefix(t, L)Answer
Using equations (length.1) and (length.2'), show an evaluation of length([6,5,4,3]) by only replacing expressions by equal expressions. Answer
Using equations (cat.1) and (cat.3), show an evaluation of cat([1,2,3], [4,5,6]) by only replacing expressions by equal expressions. Answer
Using equations (isPrefix.1–isPrefix.3), show an evaluation of isPrefix([2,3,4], [2,4,3]) by only replacing expressions by equal expressions. Answer
Using equations (isPrefix.1–isPrefix.3), show an evaluation of isPrefix([2,3], [2]) by only replacing expressions by equal expressions. Answer
Write equations for function sum(L), which yields the sum of all members of list L. For example, sum([2,3,4]) = 2 + 3 + 4 = 9. The sum of an empty list is 0. Make sure that your equations contain enough information to determine the value of sum(L) for any list of integers L. Answer
Using your equations for sum(L) from the preceding question, do an evaluation of sum([3,5,7]) by only replacing expressions by equal expressions. Answer
Write equations for function smallest(L), which yields the smallest member of nonempty list L. For example, smallest([2,3,4]) = 2 and smallest([6,4,8,7]) = 4. Your equations should not try to define smallest([ ]), since the list is required to be nonempty. You can use function min(x, y) to compute the smaller of two integers x and y. Answer
Write equations for function prefix(L, n), which yields the length n prefix of list L. For example, prefix([2,4,6,8,10], 3) = [2,4,6]. If n is larger than the length of L then prefix(L, n) should return L. For example, prefix([2,4,6,8,10], 50) = [2,4,6,8,10]. Answer