Is it a list ?

[Luke Gorrie]

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