7
$\begingroup$

I am writing a function that will take an expression as input. I want to make sure the expression is valid first before processing it. Looking for a correct to use MatchQ (or if you have better method) to use which will return True or False when given the expression.

Specifications

The expression will have the following form

a1 Cos[x+b1] + a2 Cos[x+b2] + a3 Cos[x+b3] + ....

OR

a1 Sin[x+b1] + a2 Sin[x+b2] + a3 Sin[x+b3] + ....

So if you can parse one, then with some trick, can use the same parser with the other using OR.

There can one or more terms there. Also, the amplitudes (the $a_i$) can be there or not there. Also, there is no need to check what is used for argument to the trig functions. So if expression is Cos[Cos[x]] then that is ok, only FIRST level needs to be validated. The expression will be passed by TrigReduce[] before. Your parser only needs to check for the above top level form.

Hence the following are all valid expression and should return True

Sin[x]
a Sin[x]
a Sin[x] + Sin[x +b]
Sin[x] + Sin[x + b] + c Sin[x]

These are NOT valid:

Sin[x] + Cos[x]  (*mixed*)
a + Sin[x]  (*first term has no sin nor cos *)
Sin[x]+ b + Sin[x + v] 

So the function needed will have this specification

parse[expr_]

and will return either True or False.

What is the most efficient way to do this?

Test suite

To help you in making the parser, here are few expressions that should return True and another set that should return False

ClearAll[x, a1, b1, a2, b2, a3, b3];
trueTests = {
  3 Cos[x],
  a1 Cos[x + b1],
  Cos[x] + a1 Cos[x + b1],
  a1 Cos[x] + a1 Cos[x + b1] + a2 Cos[x + b2],
  3 Sin[x],
  a1 Sin[x + b1],
  Sin[x] + a1 Sin[x + b1],
  a1 Sin[x] + a1 Sin[x + b1] + a2 Sin[x + b2]
  }

falseTests = {
  a1,
  a1 Cos[x + b1] + Sin[x],
  Cos[x] + b1,
  a1 Cos[x] + a1 Cos[x + b1] + a2 Sin[x + b2],
  Cos[x] + Sin[x]
  }
$\endgroup$
4
  • 2
    $\begingroup$ Naming your head with repeated would be the way to go. Something like MatchQ[{2 Sin[x], 4 Sin[2 x], Cos[x]}, {(_. (h : (Sin | Cos))[_. x + _.]) ..}] should work $\endgroup$
    – Greg Hurst
    Aug 16, 2013 at 16:16
  • $\begingroup$ @RiemannZeta Nice going. I am working on an answer now that will use the same thing! (and explain in more detail) $\endgroup$
    – Mr.Wizard
    Aug 16, 2013 at 16:24
  • 1
    $\begingroup$ @RiemannZeta there's mythology about naming things, and one where giving something a name fixes its form. Spooky. :) $\endgroup$
    – rcollyer
    Aug 16, 2013 at 16:49
  • 2
    $\begingroup$ Nasser, congratulations on joining the 10,000 Club! *toot* $\endgroup$
    – Mr.Wizard
    Aug 16, 2013 at 18:04

2 Answers 2

11
$\begingroup$

Here is how I would approach this problem. First, when possible we should make use of the Attributes of the functions in use with regard to their effect on pattern matching.

These attributes follow the natural application of the functions to which they apply so often they make mathematical matching easier. (Sometimes you don't want that.)

The OneIdentity attribute of Times lets this pattern match:

MatchQ[#, _. "X"] & /@ {"X", 5 "X"}

{True, True}

_. is an Optional pattern (it uses the Default value).

Plus in your application is somewhat more tricky because Plus[x] evaluates to x directly. Since I don't know how to both prevent this invalid simplification and preserve the OneIdentity behavior illustrated above I will have to turn to a more manual approach and use Alternatives. Here is my solution (p2):

p1 = (_. (h : Sin | Cos)[_]) ..;
p2 = p1 | Verbatim[Plus][p1];

Test:

MatchQ[#, p2] & /@ trueTests
MatchQ[#, p2] & /@ falseTests

{True, True, True, True, True, True, True, True}

{False, False, False, False, False}

There are several parts to this pattern. The first listed was explained preemptively by RiemannZeta in a comment above.

  • By naming the Pattern Sin | Cos we require all appearances (in any given matching application) of that pattern to be identical for the pattern to match.

  • Repeated is used to match one or more instances of a given pattern

  • The Optional pattern _. is used in an implicit Times, as already illustrated

  • Alternatives is used to match either a raw instance of the pattern p1 or multiple instances within Plus

  • Verbatim is used to prevent Plus[p1] from evaluating to p1 which would then be a raw Repeated object.

Another way to write p1 that might be easier to read is this:

p1 = (_. _Sin) .. | (_. _Cos) ..;

Responding to Leonid's answer, if one prefers not to use "tricks" such as the pattern behavior of functions with OneIdentity it adds very little code to do without that:

p0 = (h : Sin | Cos)[_];
p1 = (p0 | _*p0) ..;
p2 = p1 | Verbatim[Plus][p1];

MatchQ[#, p2] & /@ trueTests
MatchQ[#, p2] & /@ falseTests

{True, True, True, True, True, True, True, True}

{False, False, False, False, False}

Worth noting is that here as well as above the pattern parts need not be assigned e.g. p0, p1 if one prefers to build the pattern in one shot:

p = # | Verbatim[Plus][#] &[(# | _*#) ..] &[(h : Sin | Cos)[_]];

MatchQ[#, p] & /@ trueTests
MatchQ[#, p] & /@ falseTests

{True, True, True, True, True, True, True, True}

{False, False, False, False, False}

$\endgroup$
2
  • 2
    $\begingroup$ Another variant, without Verbatim: p2 = With[{p1 = (_. (h : Sin | Cos)[_]) ..}, HoldPattern[p1 | Plus[p1]]] $\endgroup$ Aug 17, 2013 at 10:09
  • $\begingroup$ @Rolf Yes, that should work too. $\endgroup$
    – Mr.Wizard
    Aug 17, 2013 at 14:21
7
$\begingroup$

Here is a parser that seems to satisfy your specs (with an improvement from Mr.Wizard):

ClearAll[parse, sameQ, reduce];
parse[HoldPattern[Plus[terms__?parse]]] /; sameQ[terms] := True;
parse[(a_: 1) * (_Sin | _Cos)] := True;
parse[x_] := False;

sameQ[terms__] /; MemberQ[{terms}, _Times] := sameQ @@ reduce[{terms}];
sameQ[__Sin | __Cos] := True;
sameQ[__] := False;

SetAttributes[reduce, Listable];
reduce[Times[a_, x : (_Sin | _Cos)]] := x;
reduce[x_] := x;

It is less concise than one could have made it (compared to the answer of Mr.Wizard, for example), but it has an advantage to be completely straight-forward and also extensible, and is along the lines of how one might write parsers in general (use recursion). In general, pattern-matching is akin regexps (but on parsed expressions), and in many instances I've found recursion to be more powerful approach.

$\endgroup$
13
  • $\begingroup$ Leonid, since you are looking at this can you tell me if there is a way to use the OneIdentity attribute of Plus without having Plus[p1] (in my example) "simplify" to p1? $\endgroup$
    – Mr.Wizard
    Aug 16, 2013 at 16:42
  • $\begingroup$ @Mr.Wizard If it exists, I don't see it at the moment. But, you know, for some time now I prefer simple things :). $\endgroup$ Aug 16, 2013 at 16:47
  • 1
    $\begingroup$ @Mr.Wizard But what do you find hard to understand in this code? To me, it looks completely self-explanatory, to the extent that comments might actually make it less clear / explicit (see my edit though, you might be referring to the previous version of the code). $\endgroup$ Aug 16, 2013 at 17:04
  • 2
    $\begingroup$ @Mr.Wizard I just wanted to make this as straight-forward and explicit as possible, and not rely on defaults or any other particularities of the pattern-matcher, to make this code easy to generalize to other heads (if needed). You went into one extreme (using all possible special features to make it most concise), and I sort of went into the other one - use only the most basic pattern-matching and focus on general elements of parser-writing (recursion, case enumeration). I think our answers are quite complementary. $\endgroup$ Aug 16, 2013 at 17:45
  • 1
    $\begingroup$ @Mr.Wizard It is somewhat ironic, that while your code itself is very concise, your answer (fully explaining it) is not. In my case, the code is more verbose, but (arguably) it explains itself to a large extent, so I could save on explanations and ended up with a shorter answer overall :). $\endgroup$ Aug 16, 2013 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.