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
Differences between pattern matching and unification
pattern matchingunification
Related Solutions
The low level can be explored with a disassembler but the short answer is that it's a bunch of if/elses where the predicate depends on the pattern
case Sum(l,r) // instance of check followed by fetching the two arguments and assigning to two variables l and r but see below about custom extractors
case "hello" // equality check
case _ : Foo // instance of check
case x => // assignment to a fresh variable
case _ => // do nothing, this is the tail else on the if/else
There's much more that you can do with patterns like or patterns and combinations like "case Foo(45, x)", but generally those are just logical extensions of what I just described. Patterns can also have guards, which are additional constraints on the predicates. There are also cases where the compiler can optimize pattern matching, e.g when there's some overlap between cases it might coalesce things a bit. Advanced patterns and optimization are an active area of work in the compiler, so don't be surprised if the byte code improves substantially over these basic rules in current and future versions of Scala.
In addition to all that, you can write your own custom extractors in addition to or instead of the default ones Scala uses for case classes. If you do, then the cost of the pattern match is the cost of whatever the extractor does. A good overview is found in http://lamp.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf
In a nutshell, patterns are like defining piecewise functions in math. You can specify different function bodies for different arguments using patterns. When you call a function, the appropriate body is chosen by comparing the actual arguments with the various argument patterns. Read A Gentle Introduction to Haskell for more information.
Compare:
with the equivalent Haskell:
fib 0 = 1
fib 1 = 1
fib n | n >= 2
= fib (n-1) + fib (n-2)
Note the "n ≥ 2" in the piecewise function becomes a guard in the Haskell version, but the other two conditions are simply patterns. Patterns are conditions that test values and structure, such as x:xs, (x, y, z), or Just x. In a piecewise definition, conditions based on = or ∈ relations (basically, the conditions that say something "is" something else) become patterns. Guards allow for more general conditions. We could rewrite fib to use guards:
fib n | n == 0 = 1
| n == 1 = 1
| n >= 2 = fib (n-1) + fib (n-2)
Best Answer
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
XandY, this will work fine:In Erlang (which uses pattern-matching with syntax close to Prolog), the line
X = Ywill produce an error:variable 'Y' is unbound. Note thatXbeing 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 equationA ++ X == B, or 3) solve the equationX ++ A == Bfor given listsAandB, you need to write 3 separate functions; in Prolog, all these jobs (and more!) are done by one predicate.