Differences between pattern matching and unification?

Question

I thought I understand how pattern matching like found in Scala and Haskell is different from unification found in Prolog but my misunderstands of Prolog is great. What is some simple problems solvable by one that cannot be solved by the other? Thank you

Answer 1

Simple statement: pattern matching is one-way, unification is two-way. That is, in Prolog the right-hand side (the one being matched against) can include unbound variables. E.g., if you have two unbound variables X and Y, this will work fine:

X = Y,
X = 5,
%% Y = 5 now as well

In Erlang (which uses pattern-matching with syntax close to Prolog), the line X = Y will produce an error: variable 'Y' is unbound. Note that X being unbound is fine: it is supposed to be pattern-matched.

This can be useful when you want to deal with partially-defined values. A very good example is difference lists.

This is also what allows use of Prolog predicate in multiple modes. E.g. in Scala/Haskell/Erlang, if you want to 1) find A ++ B, 2) solve the equation A ++ X == B, or 3) solve the equation X ++ A == B for given lists A and B, you need to write 3 separate functions; in Prolog, all these jobs (and more!) are done by one predicate.

Answer 2

I think it is useful to formalize the concepts, instead of looking into a specific language. Matching and unification are fundamental concepts that are used in more contexts than pattern matching and prolog.

• A term s matches t, iff there is a substitution phi such that phi(s) = t
• A term s unifies with a term t, iff there is a substitution such that phi(s) = phi(t)

To give an example we inspect the terms s = f(Y,a) and t = f(a,X) where X,Y are variables and a is a constant. s does not match t, because we cannot universally quantify the constant a. However, there is a unifier for s and t: phi = {X\a, Y\a}

Answer 3

The following in Scala would fail to compile, as it's first case branch attempts to declare the variable x twice.

(1, 1) match{
   case (x, x) => println("equals")
   case _      => println("not equals")
}

If Scala used unification instead of pattern matching this would succeed and print "equals" while

(1, 2) match{
   case (x, x) => println("equals")
   case _      => println("not equals")
}

would print "not equals". This is because the unification would fail when attempting to bind the variable x to both 1 and 2.

Answer 4

In Prolog, you can append [3] to [1,2] like this:

?- append([1,2], [3], Z).
Z = [1, 2, 3].

The neat thing about unification is that you can use the same code (the internal definition of 'append'), but instead find the second argument needed to get the result from the first argument:

?- append([1,2], Y, [1,2,3]).
Y = [3].

Rather than coding by writing "do this, then do that", you code in Prolog by saying what you know. Prolog treats the facts you give it as equations. Unification lets it take those equations and solve for whatever variables you don't yet know the values of, whether they're on the right or left side.

So, for instance, you can write a planner in Prolog, and you can run it "forward", giving it a plan and having it predict its results; or you can run it "backward", giving it a set of results and having it construct a plan. You could even run it both ways at once (if you were careful in your coding), specifying a set of goals and a set of constraints on the plan, so that you could say "Find a plan for getting to work that does not involve taking the subway."