Exercise Chapter 4.2 on Unification

1. [a,bX]=[A,B,c] succeeds with A=a, B=b and X=[c].

   First, the left and right hand terms are both lists. Now to match their 1st elements: A matches with a. The second elements B matches with b. What happens now? Let us discard the first two elements of each list. We are left with matching X=[c] ---this succeeds.

   Quite a few think the result should be X=c. Remember that the syntax [HT] means that the term following the symbol is a list ---so, the X in the problem is a list. Therefore we cannot have X=c.

2. [a,b]=[b,a] fails.

   Look at the first elements: does a match with b? No ---so the unification fails. Some may see lists as `bags' of things where the order of occurrence is immaterial. This is not so.

3. [a[b,c]]=[a,b,c] succeeds.

   The first elements of the two lists are identical. Throw them away and we are left with [b,c]=[b,c] which succeeds. The main point to note is again that the term following the symbol is a list and that it is specifically [b,c].

4. [a,[b,c]]=[a,b,c] fails.

   We can tell quickly that the unification must fail because the first list has two elements and the second has three. Therefore they cannot unify.

   If we discard the (equal) heads we have [[b,c]]=[b,c]. The left hand side is a list consisting of a single element (which just happens to be a list itself). The right hand side is a list of two elements. Going on, what is the first element of each of these two lists? On the left we have [b,c] and on the right we have b. These terms are not unifiable.

5. [a,X]=[X,b] fails.

   The first element of each list (the heads) can be unified ---with X=a. Looking at the second elements, we need to unify X with b ---but X=a so the process fails.

6. [a[]]=[X] succeeds with X=a.

   The list [a[]] is exactly equivalent to [a]. Therefore the problem becomes [a]=[X]. This unifies with X=a.

7. [a,b,X,c]=[A,B,Y] fails.

   The simple answer is that the left hand list has four elements and the right has three ---therefore these two lists will not unify.

   To see why, we match the head elements ---we get A=a. Throwing away the heads, we end up with [b,X,c]=[B,y]. Repeating, we have B=b. Again, discarding the heads, we have [X,c]=[y]. Repeating we get X=y. We now end up with [c]=[]. Fails.

8. [HT]=[[a,b],[c,d]] succeeds with H=[a,b] and T=[[c,d]].

   The right hand list has two elements: the first (head) is [a,b] and the second element is [c,d]. The head elements unify with H=[a,b]. If we now discard the head elements we are left with deciding whether T unifies with [[c,d]]. Succeeds with T=[[c,d]].

9. [[X],Y]=[a,b] fails.

   If we try to unify the head elements of these lists we have the problem [X]=a. This fails.