Pattern Matching - Prolog vs. Haskell

Question

This is not a homework question, rather an exam study guide question. What is the difference between pattern matching in Prolog Vs Haskell?

I've done some research and reading up on the theories behind them doesn't really give me a solid understanding between the two. I read that in Prolog, pattern matching is different because it has the ability to unify variables and thus be able to deduce through resolution and spit out the possible answer

eg ?- [a,b] = [a,X]
   X = b

Now I'm not sure how to display pattern matching in Haskell. I know that the same query above shown in Prolog will not work in Haskell because Haskell cannot unify like Prolog. I remember somewhere that to get the same answer in Haskell, you have to explicitly tell it through guards.

I know that I am pretty close to understanding it, but I need someone to break it down Barney style for me so I can FULLY understand it and explain it to a 12 year old. This has been bugging me for quite some time and I can't seem to find a solid explanation.

By the way the example shown above was just to display to you guys what I've learned so far and that I'm actually trying to find an answer. My main question does not relate to the examples above but rather a complete understanding on the difference between the two.

Solution 1

Prolog pattern matching is based on unification, specifically the Martelli-Montanari Algorithm (minus the occurs check, by default). This algorithm matches values of the same position, binding variables on one side to a value at corresponding position on the other side. This kind of pattern matching could work both ways, therefore in Prolog you could use arguments as both input and output. A simple example, the length/2 predicate. We could use this to (comment explains the query):

?- length([],0).      % is the length of empty list zero?
?- length([a,b,c],X). % what's the length of list consisting of a,b and c?
?- length(L,5).       % give me all lists that have length of 5

Haskell pattern matching is a one way matching, to bind variables to different parts of given value. Once bound, it carries out the corresponding action (the right hand side). For example, in a function call, pattern matching may decide which function to call. e.g.:

sum []     = 0
sum (x:xs) = x + sum xs

the first sum binds empty list, while the second binds a list of at least 1 element. Based on this, given sum <a list>, the result could be either 0 or x + sum xs depending on whether sum <a list> matches sum [] or sum (x:xs).

Solution 2

The difference between pattern matching as in Haskell and Prolog's unification stems from the fundamentally different rôle of variables in both languages.

In Haskell, variables hold values. Concrete values. Such a value might not have been computed yet, and it might even be ⊥, but otherwise it is one concrete value. In Haskell you cannot take a variable and only state some properties of its value first.

So pattern matching always means that a concrete value is matched against a pattern which contains some variables. The outcome of such a matching is either failure or a binding of the variables to concrete values. In Haskell this is further restricted to avoid the need of general comparison, which would imply that class Eq is defined for the terms being matched.

In Prolog, however, variables may refer to a set of possible solutions. Variables may occur anywhere - also somewhere between other values. Unification now ensures that the stated equalities still hold and the result is represented optimally, i.e. the most general unifier is computed.

| ?- length(L,5).                      
L = [_,_,_,_,_]
| ?- length(L,5), maplist(=(E),L).
L = [E,E,E,E,E]

So Prolog does not answer here with concrete values like L = [1,1,1,1,1] or L = [[],[],[],[],[]] but gives the most general unifier as an answer which contains all those concrete values.

Solution 3

Nobody mentioned the following very important difference. Pattern matching in Prolog is tried for every clause of a predicate, even if one of the previous matches has succeeded (unless stopped short by a cut). But in Haskell pattern matching on clauses is attempted only until the first success. No other alternatives are tried (unless the match was rejected by a guard).

Prolog's pattern matching establishes an equality constraint in most general sense (see answer by @false for details). Sharing is explicit: A=B, A=5 sets B=5 as well. This is possible because Prolog's logvar can be in not-yet-set (i.e. uninstantiated) state. This makes tying-a-knot easy (a basic programming technique actually, viz. difference lists).

In Haskell, any variable is allowed to be defined only once at the syntax level. In Prolog a logvar is set only once too (sans backtracking), but it is allowed to point at an incomplete structure (data), where holes are represented by other not-yet-instantiated logvars which can be set at any later point in time.

In Haskell, a given structure defined with guarded recursion is progressively fleshed out as demanded by access. In Prolog, after the initial instantiation of a variable, any subsequent unification is turned into verification of terms' compatibility and possible further (perhaps partial yet again) instantiation ("filling up" the holes explicitly).

Solution 4

Adding to the answer of LeleDumbo, we could say that Prolog unification builds terms as well as deconstructs them, while in Haskell the build phase is conveniently demanded to returned value.

Of course such feature is what allows in pure Prolog so called 'bidirectional' predicates, exploited for instance in DCGs, that with some restriction, can be used for both parse and generation.

Solution 5

Here is an example I find interesting in Prolog to support @chac (+1 btw) mention about how Prolog's unification "builds" terms that we ran into in the prolog tag yesterday:

swapPairs([],       []).
swapPairs([X],      [X]).
swapPairs([X, Y|T], [Y, X|R]) :- swapPairs(T, R).

This predicate has almost no "body". It only uses unification of its arguments in its head and recursion.

As pointed out by both @chac and @LeleDumbo, that's because Prolog's unification is "both-way".

Here is what A gentle Introduction to Haskell says about it:

Pattern matching in Haskell is different from that found in logic programming languages such as Prolog; in particular, it can be viewed as "one-way" matching, whereas Prolog allows "two-way" matching (via unification), along with implicit backtracking in its evaluation mechanism.

View more solutions

Comments

[luqui]

Good answer. Another point is that Haskell patterns must be linear; i.e. they can mention each bound variable only once. (otherwise you would need unification)

[false]

@luqui: Nonlinear patterns do not require general unification, but they would require Eq to be defined.

[Tanner]

Good post! Sometimes I find thinking of prolog as statements a bit easier. i.e. : length([], ). % An empty list has 0 for length. EDIT: For defining facts, and queries for Prolog

[false]

+1: good point - from the Haskell viewpoint. There, the trying of alternate clauses is part of pattern matching. In Prolog terminology, this is considered part of backtracking.

[Will Ness]

@false I wouldn't phrase it exactly like that. Pattern matching is a unitary action, done per-clause, in both languages IMO. The trying of clauses is an evaluation mechanism in Haskell, and in Prolog, but because Prolog doesn't stop on the first clause that matched it simply means that it backtracks.

[false]

The Haskell Report defines the meaning of case expressions as Pattern Matching. And translates all other uses to it. Including function and pattern bindings. Whereas in Prolog the notion of backtracking is strictly needed.

[Anderson Green]

It's also possible to match patterns in Prolog without unifying them (using subsumes_term/2).