Pattern matching as a library

[Jacob Carlborg via Digitalmars-d]

On 12/03/16 14:12, Simen Kjaeraas wrote:
> As I once again bemoaned D's lack of pattern matching yesterday, I was
> inspired to create this[0] implementation, that plays to D's strengths,
> allows for user-defined matching, and has a fairly usable syntax. The
> core usage looks like this:
>
> unittest {
>    auto a = tuple(1, "foo");
>    auto b = match(a) (
>      _!(int, "foo") = (int i) => 1,
>      _!(_, _)       = ()      => 0
>    );
>    assert(b == 1);
> }

What kind of syntax is that? Is "match" returning a struct with opCall 
that is called immediately?

> With the user-defined matching implemented as follows:
>
> struct Tuple(T...) {
>     // Implementation
>
>    // Magic happens here
>    bool opMatch(Pattern, Args...)(Pattern p, ref Args args) {
>      foreach (i, e; p.pattern) {
>        static if (isTypeTuple!e) {
>          enum n = countTypes!(p.pattern[0..i]);
>          args[n] = fields[i];
>        } else static if (!ignore!e) {
>          if (fields[i] != e) {
>            return false;
>          }
>        }
>      }
>    }
> }

Is the tuple iterating all patterns to see if there's a match? Shouldn't 
that be the job for the the match function?

> Or for Algebraic:
>
> struct Algebraic(T...) {
>    union {
>      T fields;
>    }
>    size_t which;
>
>    bool opMatch(Pattern, Type)(Pattern p, ref Type args) if
> (staticIndexOf!(Type, T) > -1) {
>      enum index = staticIndexOf!(Type, T);
>      if (index == which) {
>        args = fields[index];
>        return true;
>      }
>      return false;
>    }
> }
>
> The main problem I see is the temporary allocation of function arguments
> on line 124 and their assignment in opMatch, but I currently don't have
> a better solution.
>
> Also, while I very much dislike using _ for an identifier, I feel it may
> be the best alternative here - it conveys the meaning of 'don't care'
> for the pattern, and doesn't stand out like a sore thumb before the
> exclamation mark. Other suggestions are welcome.

I've started implementing a pattern matching function as well. It has a 
syntax that only use compile time parameters, because both types and 
values can be passed. I'm not entirely sure on the syntax yet. I'll have 
to see what's possible to implement. Some suggestions:

auto a = tuple(1, "foo");
auto b = match!(a,
     int, "foo", (int i) => 1,
     _, _, () => 0,
);

If the pull request for inspecting templates ever will be merged it 
won't be necessary to have typed lambdas:

auto b = match!(a,
     int, "foo", (i) => 1,
     _, _, () => 0,
);

If you only want to match types it could look like this:

auto b = match!(a,
     (int a) => 1
);

Matching a value:

auto b = match!(a,
     1, () => 2
);

Matching a pattern:

auto b = match!(a,
     (a, b) => a + b
);

The else pattern (executed if nothing else matches):

auto b = match!(a,
     () => 4,
);

It would be nice if it was possible to verify at compile time if at 
least one pattern will match. For example:

match!("foo",
     (int a) => 1,
);

It's clear that the above pattern can never match.

-- 
/Jacob Carlborg