www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Pattern matching example

reply bearophile <bearophileHUGS lycos.com> writes:
I'm not currently asking to implement pattern matching in D3 (as present for
example in Scala), but it's positive to think how to solve similar problems in
D2, because even if pattern matching is not available in D2, the problems it is
asked to solve solve can be real.

Walter or Andrei has recently shown here a possible implementation idea, but I
don't remember where the post is and what the implementation was. And it wasn't
a small compilable program.

Recently the RosettaCode site has added a small but real problem to solve with
pattern matching. It can be a quite good example to see how D2 can be used
solve this problem:

http://rosettacode.org/wiki/Pattern_matching

RosettaCode site is nice, because among its various purposes, it can be
advertisement too for the D language. That's why I (and Downs and probably
others here) have written many solutions in D1/D2 for that site. So I even
suggest to put a link to to RosettaCode somewhere in the D section of the
digitalmars site, to turn it into a semi-official thing.

Bye,
bearophile
Apr 03 2010
parent reply Lutger <lutger.blijdestijn gmail.com> writes:
bearophile wrote:


 I'm not currently asking to implement pattern matching in D3 (as present
 for example in Scala), but it's positive to think how to solve similar
 problems in D2, because even if pattern matching is not available in D2,
 the problems it is asked to solve solve can be real.
 
 Walter or Andrei has recently shown here a possible implementation idea,
 but I don't remember where the post is and what the implementation was. And
 it wasn't a small compilable program.


It was a subthread under the 'is D a cult' thread, this was the basic 
example:

foo(  v,
      (int i) { writeln("I saw an int ", i); },
      (string s) { writeln("I saw a string ", s); ),
      (Variant any) { writeln("I saw the default case ", any); }
    );


The criticism was that this only does matching on type. Matching on strings 
and integers should be done with case statements and other values with if-
else.

I don't have the time to implement this, but after some hacking I found that 
something like the following could be made to work, exploiting AA 
initializers.  I'm not sure how efficient it would be though:

void matcher(T, C...)(T value, C Cases)
{
    foreach( Case ; Cases)
    {
        static if ( is(typeof(Case.keys) == T[]))
        {
            if (value in Case)
            {
                auto fun = Case[value];
                fun(value);
            }
        }
    }
}


void main(string[] args)
{
    int i = 12;
    matcher(i,
          [ "aha": (string v) { writeln("I saw a string ", v); } ],
          [ 12   : (int i) { writeln("I saw an int ", i); } ] );

    string v = "aha";      
    matcher(v,
          [ "aha" : (string v) { writeln("I saw a string ", v); } ],
          [ 12    : (int i) { writeln("I saw an int ", i); } ] );
}
Apr 04 2010
next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Lutger wrote:

...

 
 void main(string[] args)
 {
     int i = 12;
     matcher(i,
           [ "aha": (string v) { writeln("I saw a string ", v); } ],
           [ 12   : (int i) { writeln("I saw an int ", i); } ] );
 
     string v = "aha";
     matcher(v,
           [ "aha" : (string v) { writeln("I saw a string ", v); } ],
           [ 12    : (int i) { writeln("I saw an int ", i); } ] );
 }


Forgot to add: it is of course possible to adjust matcher to accept something 
like this:


matcher(v,
     [ "aha" : (string v) { writeln("I saw a string ", v); },
       (string v) { writeln("default case for string ", v); },	
     [ 12    : (int i) { writeln("I saw an int ", i); } ] );
Apr 04 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Apr 4, 2010 at 17:18, Lutger <lutger.blijdestijn gmail.com> wrote:


 bearophile wrote:


 I'm not currently asking to implement pattern matching in D3 (as present
 for example in Scala), but it's positive to think how to solve similar
 problems in D2, because even if pattern matching is not available in D2,
 the problems it is asked to solve solve can be real.

 Walter or Andrei has recently shown here a possible implementation idea,
 but I don't remember where the post is and what the implementation was.


 And

 it wasn't a small compilable program.


 It was a subthread under the 'is D a cult' thread, this was the basic
 example:

 foo(  v,
      (int i) { writeln("I saw an int ", i); },
      (string s) { writeln("I saw a string ", s); ),
      (Variant any) { writeln("I saw the default case ", any); }
    );


I went the other way round and wrote something more compile-time oriented:

usage:

match!(fun1, fun2, fun3)(someValues...); // as many values as you wish

where the funX can be template functions (or anything template-y _and_
callable), to harness the pattern matching inherent in templates, variadic
templates, and so on.

For example, given:

string any(T...)(T t) { return "any: " ~ typeof(t).stringof;}

T one(T)(T t) { return t;}

T[] twoEqual(T)(T t1, T t2) { return [t1,t2];}

Tuple!(T,U) twoDiff(T,U)(T t, U u) { return tuple(t,u);}

string three(T)(T t1, T t2, T t3) { return T.stringof ~ " thrice";}

you can do:

alias match!(one, twoEqual, twoDiff, three, any) matcher;

auto m = matcher(1);     // 1
auto m = matcher(1,2); // [1,2]
auto m = matcher(1,'a'); // Tuple!(int,char)(1,'a')
auto m = matcher(1,2,3,4); // string "any: (int,int,int,int)"

You can also use standard functions, of course, and mix templates and
functions.
I used this to create trees of tuples (tuples of values and tuples) and
pattern-match on them. It's far from being as beautiful as Haskell code, but
it's enough for my needs.

One interest compared to function overload is that you can have different
return types depending on the function you give it as params.

I have another version that deconstruct the values: if you send it a struct
containing two ints and one of your function has two ints as params, it will
match. But it's buggy as hell and I sould have a look at it before posting
it.

For match, here is the code:

template match(alias fun, Rest...) {
    auto match(M...)(M m) { // curried template...
            return Matcher!(fun, M.length, M, Rest)(m)();
    }
}

struct Matcher(alias fun, size_t n, Rest...) {
    TypeTuple!(Rest[0..n]) _m;
    this(TypeTuple!(Rest[0..n]) m) { _m = m;}
    auto opCall() {
        static if (is(typeof(fun(_m))))
            return fun(_m);
        else static if (n == 1 && is(typeof(fun(_m[0])))) // I'm not sure
this is necessary
            return fun(_m[0]);
        else static if (Rest.length > n) {
            return Matcher!(Rest[n], n, Rest[0..n], Rest[n+1..$])(_m)();
        }
        else { // no match found, we are at the end of Rest
            string s;
            foreach(i, Type; TypeTuple!(Rest[0..n])) s ~= to!string(_m[i]);
            throw new NoMatchException("No match for " ~ s ~ " of type " ~
typeof(_m).stringof);
        }
    }
}

Half the complexity and ugliness comes from my wanting to have a variadic
function in the end: I did_not_ want have to wrap my arguments in a tuple,
as it's done for std.concurrency, IIRC.
Also, I use functions like (...) { some code } or (T...)(T t) { } to get a
function that matches everything, not a (Variant v) { }

Philippe
Apr 04 2010