Pattern Matching – Prolog vs. Haskell

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).

Leave a Comment