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:
--0015175d020ad8206104836ec2e4
Content-Type: text/plain; charset=ISO-8859-1

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.

 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); } );

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 --0015175d020ad8206104836ec2e4 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Sun, Apr 4, 2010 at 17:18, Lutger <sp= an dir=3D"ltr">&lt;<a href=3D"mailto:lutger.blijdestijn gmail.com">lutger.b= lijdestijn gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_qu= ote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 20= 4, 204); padding-left: 1ex;"> <div class=3D"im">bearophile wrote:<br> <br> &gt; I&#39;m not currently asking to implement pattern matching in D3 (as p= resent<br> &gt; for example in Scala), but it&#39;s positive to think how to solve sim= ilar<br> &gt; problems in D2, because even if pattern matching is not available in D= 2,<br> &gt; the problems it is asked to solve solve can be real.<br> &gt;<br> &gt; Walter or Andrei has recently shown here a possible implementation ide= a,<br> &gt; but I don&#39;t remember where the post is and what the implementation= was. And<br> &gt; it wasn&#39;t a small compilable program.<br> <br> </div>It was a subthread under the &#39;is D a cult&#39; thread, this was t= he basic<br> example:<br> <br> foo( =A0v,<br> =A0 =A0 =A0(int i) { writeln(&quot;I saw an int &quot;, i); },<br> =A0 =A0 =A0(string s) { writeln(&quot;I saw a string &quot;, s); ),<br> =A0 =A0 =A0(Variant any) { writeln(&quot;I saw the default case &quot;, an= y); }<br> =A0 =A0);<br><br></blockquote><div><br>I went the other way round and wrot= e something more compile-time oriented:<br><br>usage:<br><br>match!(fun1, f= un2, fun3)(someValues...); // as many values as you wish<br><br>where the f= unX can be template functions (or anything template-y _and_ callable), to h= arness the pattern matching inherent in templates, variadic templates, and = so on.<br> <br>For example, given:<br><br>string any(T...)(T t) { return &quot;any: &q= uot; ~ typeof(t).stringof;}<br><br>T one(T)(T t) { return t;}<br><br>T[] tw= oEqual(T)(T t1, T t2) { return [t1,t2];}<br><br>Tuple!(T,U) twoDiff(T,U)(T = t, U u) { return tuple(t,u);}<br> <br>string three(T)(T t1, T t2, T t3) { return T.stringof ~ &quot; thrice&q= uot;;}<br><br>you can do:<br><br>alias match!(one, twoEqual, twoDiff, three= , any) matcher;<br><br>auto m =3D matcher(1);=A0=A0=A0=A0 // 1<br>auto m = =3D matcher(1,2); // [1,2]<br> auto m =3D matcher(1,&#39;a&#39;); // Tuple!(int,char)(1,&#39;a&#39;)<br>au= to m =3D matcher(1,2,3,4); // string &quot;any: (int,int,int,int)&quot;<br>= <br>You can also use standard functions, of course, and mix templates and f= unctions.<br> I used this to create trees of tuples (tuples of values and tuples) and pat= tern-match on them. It&#39;s far from being as beautiful as Haskell code, b= ut it&#39;s enough for my needs.<br><br>One interest compared to function o= verload is that you can have different return types depending on the functi= on you give it as params.<br> <br>I have another version that deconstruct the values: if you send it a st= ruct containing two ints and one of your function has two ints as params, i= t will match. But it&#39;s buggy as hell and I sould have a look at it befo= re posting it.<br> <br>For match, here is the code:<br><br>template match(alias fun, Rest...) = {<br>=A0=A0=A0 auto match(M...)(M m) { // curried template...<br>=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0 return Matcher!(fun, M.length, M, Rest)(m)();<br>= =A0=A0=A0 }<br>}<br><br> struct Matcher(alias fun, size_t n, Rest...) {<br> =A0=A0=A0 TypeTuple!(Rest[0..n]) _m;<br> =A0=A0=A0 this(TypeTuple!(Rest[0..n]) m) { _m =3D m;}<br> =A0=A0=A0 auto opCall() {<br> =A0=A0=A0=A0=A0=A0=A0 static if (is(typeof(fun(_m))))<br> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 return fun(_m);<br> =A0=A0=A0=A0=A0=A0=A0 else static if (n =3D=3D 1 &amp;&amp; is(typeof(fun(_= m[0])))) // I&#39;m not sure this is necessary<br> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 return fun(_m[0]);<br> =A0=A0=A0=A0=A0=A0=A0 else static if (Rest.length &gt; n) {<br> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 return Matcher!(Rest[n], n, Rest[0..n], R= est[n+1..$])(_m)();<br> =A0=A0=A0=A0=A0=A0=A0 }<br> =A0=A0=A0=A0=A0=A0=A0 else { // no match found, we are at the end of Rest<b= r> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 string s;<br> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 foreach(i, Type; TypeTuple!(Rest[0..n])) = s ~=3D=20 to!string(_m[i]);<br> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 throw new NoMatchException(&quot;No match= for &quot; ~ s ~ &quot; of type &quot; ~ typeof(_m).stringof);<br> =A0=A0=A0=A0=A0=A0=A0 }<br> =A0=A0=A0 }<br> }<br> <br>Half the complexity and ugliness comes from my wanting to have a variad= ic function in the end: I did_not_ want have to wrap my arguments in a tupl= e, as it&#39;s done for std.concurrency, IIRC.<br>Also, I use functions lik= e (...) { some code } or (T...)(T t) { } to get a function that matches eve= rything, not a (Variant v) { }<br> =A0<br>Philippe<br><br></div></div> --0015175d020ad8206104836ec2e4--
Apr 04 2010