Daniel's Blog

Pattern Matching and Unification

Posted by Daniel Lyons Sat, 19 May 2007 03:58:00 GMT

For fun during my meeting with Baird the other day at the Flying Star on Central, I gave him a toy problem I read somewhere on the internet.

Problem: In Prolog, write a predicate len_three/1 which succeeds when its parameter is a list of three items.

A crummy answer looks like this:

len_three(X) :-
   length(X, Len),
   Len = 3.

Of course there are always many crummy answers. Here’s another crummy one:

len_three(X) :-
   length(X, 3).

The best answer is to let the unification algorithm do the work:

len_three([_,_,_]).

Erlang isn’t a far cry from Prolog syntactically, so it’s no surprise that this is valid Erlang:

len_three([_,_,_]) -> true.

To illustrate using the remainder of a list, I showed him how to write head and tail in various languages:

 -- Haskell
head (x:_) = x
tail (_:xs) = xs

(* OCaml *)
let head (x::_) = x  
let tail (_::xs) = xs

% Prolog
head([X|_], X).
tail([_|T], T).

% Erlang
head([X|_]) -> X.
tail([_|T]) -> T.

So you see these are all pretty analogous to each other, thanks to the pattern matching or unification functionality of the various languages.

So then Baird wanted to see an example of peeling some items off a list but also using the remainder. So I proposed pairs/1, which takes a list as a parameter and returns a list of lists, each sublist containing two items. Implementations:

-- Haskell
two (x:y:xs) = [x,y] : two xs
two [] = []

(* OCaml *)
let rec two = function
  | (x::y::xs) -> [x;y] :: two xs
  | []         -> []
;;

% Prolog
two([X, Y | Xs], [[X,Y] | Result]) :- two(Xs, Result).
two([], []).

% Erlang
two([X, Y | Xs]) -> [[X, Y] | two(Xs)];
two([]) -> [].

Some observations:

1. Notice how much more obfuscation there is going on in the OCaml version than the Haskell version. Taste that sugary sweetness of Haskell’s syntax.
2. In theory, the Prolog version should be reversible—in other words, you should be able to unify by calling two(X, [[1,2],[3,4]]) and getting X = [1,2,3,4] back. In practice, I have some trouble writing predicates that have that property, and I’m not sure what I’m doing wrong. I should study Prolog more carefully.
3. Notice the Erlang version is shorter than the Prolog version. Shorter and perhaps slightly more readable. I have omitted the module and export declarations, however.
4. The Erlang implementation does something funny if you give it 1-10:

   2> two:two([1,2,3,4,5,6,7,8,9,10]).
   [[1,2],[3,4],[5,6],[7,8],"\t\n"]