# Is it a list ?

Luke Gorrie luke@REDACTED
Thu Jul 10 23:21:22 CEST 2003

```Marc Ernst Eddy van Woerkom <Marc.Vanwoerkom@REDACTED> writes:

> >   and experience: things that have proved to have unfortunate consequences
> >   tend to be called illegitimate by later generations.
>
> It's old cruft, if I understood you and Luke right.

Before drawing conclusions, there are some interesting uses of
improper* lists that are fun to consider.

We all know Erlang's pattern matching, like [A,B,C] = [1,2,3]. But
suppose you want to match patterns that are created at runtime, by
writing an interpreter for pattern matching instead. The pattern
interpreter takes a data structure representing a pattern and a term
to match it with, and returns a list of variable bindings (if it
matches successfully) or the atom 'nomatch'.

Consider a simple form of pattern -- any atom is a variable, lists are
matched recursively, and anything else has to match by
value. Examples:

match(['A','B','C'], [1,2,3]) => [{A,1},{B,2},{C,3}]
match(12345,         12345)   => []
match(['A','B','C'], foo)     => nomatch

Here comes a simple implementation. It will recurse down lists, match
variables with values (if used multiple times, the values must agree),
and match anything else by value.

match(Pattern, Object) -> match(Pattern, Object, []).

%% match(Pattern, Object, Bindings) => Bindings' | nomatch
match([P|Ps], [X|Xs], Bs) ->            % matching a list..
match(Ps, Xs, match(P, X, Bs));
match(_, _, nomatch) ->
%% This tricky clause is to handle the previous one's recursion --
%% it will pass 'nomatch' instead of a bindings list if the first
%% element of a list doesn't match!
nomatch;
match(P, X, Bs) when atom(P) ->         % matching a variable..
case lists:keysearch(P, 1, Bs) of   % is it bound?
false           -> [{P,X}|Bs];  % no -- create binding
{value, {P, X}} -> Bs;          % yes -- existing binding matches
{value, {P, _}} -> nomatch      % yes -- incompatible binding!
end;
match(X, X, Bs) ->                      % successful match of a constant..
Bs;
match(_, _, _) ->                       % failure!
nomatch.

Cute function I think! I knocked it off from the Lisp literature.

Now, suppose you wanted to extend the pattern matcher to handle
patterns like [A,B|C]. How would you do it? (Drum roll..) it already
works!

match(['A','B'|'C'], [1,2,3,4,5]) -> [{'A',1},{'B',2},{'C',[3,4,5]}]

But... how would you code this if you couldn't use improper lists to
represent patterns?

NB: At a glance, it looks like the shell's erlang interpreter
(erl_eval) works basically like this.

NB2: I cheated in the examples above -- the function actually returns
bindings in "reverse" order.

[*]: I think there's a more neutral name for "improper" lists. Anyone
know it?

Cheers,
Luke

```