9
$\begingroup$

GCD has attribute OneIdentity, so why doesn't GCD[a] evaluate to a?

$\endgroup$
21
$\begingroup$

GCD[a] returns unevaluated because the definitions of GCD only apply when all arguments are numeric. The presence of even one non-numeric argument yields an unevaluated result:

ClearAll[a]
GCD[1, 2, 3, a]
(* GCD[1, 2, 3, a] *)

This is true even when the sole argument is non-numeric:

GCD[a]
(* GCD[a] *)

The attribute OneIdentity has no bearing on this behaviour because that attribute only modifies pattern-matching, not evaluation. This is in contrast to an attribute like Flat which actually introduces an evaluation step to flatten expressions.

The way that OneIdentity modifies pattern-matching is... unusual. The documentation states:

OneIdentity is an attribute that can be assigned to a symbol f to indicate the f[x], f[f[x]], etc. are all equivalent to x for the purpose of pattern matching.

This statement does not tell the whole story, and neither do the examples in the comments (at least, in the documentation so far up to v10).

The missing information concerns a further restriction on the pattern. There must be at least one Optional argument and no more than one non-optional argument in the pattern f[...].

The simple case shown in the description of OneIdentity does not work:

ClearAll[f, a]
SetAttributes[f, OneIdentity]

MatchQ[a, f[x_]]
(* False *)

One must add an optional argument before OneIdentity will act:

MatchQ[a, f[x_:0]]
(* True *)

Unlike Flat, the operation of OneIdentity does not change the form of the matched component:

ClearAll[f, g, a]
SetAttributes[f, OneIdentity]

g[m:f[x_:0, y_]] := {m, x, y}

g[a]
(* {a, 0, a} *)

Note how m does not become "wrapped" in f.

Also, OneIdentity only operates when f appears in the pattern. It is not enough for it to appear only in the expression being matched:

MatchQ[f[a], a]
(* False *)

Thus, nestings of f are never "fully unwrapped", even for pattern-matching.

The following examples show various use cases of OneIdentity. The common theme is that OneIdentity only operates when at least one Optional argument appears in the first two pattern argument positions:

ClearAll[f, a]
SetAttributes[f, OneIdentity]

MatchQ[a, f[x_:0]]             === True &&
MatchQ[a, f[x_:0, y_]]         === True &&
MatchQ[a, f[x_, y_:0]]         === True &&
MatchQ[a, f[x_:0, y_:0]]       === True &&
MatchQ[a, f[x_:0, y_:0, z_:0]] === True &&
MatchQ[a, f[x_:0, y_:0, ___]]  === True &&
MatchQ[a, f[x_:0, ___]]        === True &&
MatchQ[a, f[x___:0]]           === True &&
MatchQ[a, f[a, x_:0]]          === True &&
MatchQ[a, f[x_:0, a]]          === True &&
MatchQ[a, f[x_:0, y_, z_:0]]   === True &&
MatchQ[a, f[_:f[_:f[x_:0]]]]   === True &&
MatchQ[f[a], f[f[_:f[x_:0]]]]  === True &&

MatchQ[a, f[a]]                === False &&
MatchQ[a, f[x_]]               === False &&
MatchQ[a, f[x_, ___]]          === False &&
MatchQ[a, f[x_, ___, y_:0]]    === False &&
MatchQ[a, f[a, ___]]           === False &&
MatchQ[a, f[x___]]             === False &&
MatchQ[a, f[x_:0, y_, z_]]     === False &&
MatchQ[a, f[f[f[x_:0]]]]       === False &&
MatchQ[f[a], f[f[f[x_]]]]      === False &&
MatchQ[f[a], a]                === False

(* True *)

The examples with nested f show that the optional arguments must appear at all nested levels in order to allow OneIdentity to take effect.

As to why OneIdentity operates according to such arcane rules, and why the documentation does not spell out those rules, I must pass over in silence.

$\endgroup$
  • 1
    $\begingroup$ Great answer. I knew some of this but e.g. f[f[f[x_:0]]] came as a surprise; I guess I've never tested that? $\endgroup$ – Mr.Wizard Jan 14 '15 at 20:19
  • $\begingroup$ @WReach I think the definition in not quite right. For example, MatchQ[a,f[x_: 0, y_, __]] returns False even though there is one optional argument in the first two pattern argument positions. A more correct definition would be: there has to be at least one optional argument of f[...] and besides optional arguments there can be at most one argument that is not optional. $\endgroup$ – Praan Jul 21 '15 at 10:16
  • $\begingroup$ @Praan Yes, that is a better way to phrase the rule. I have adjusted the wording and added two more examples. Thanks. $\endgroup$ – WReach Jul 21 '15 at 14:26
13
$\begingroup$

OneIdentity is a poorly, and I think incorrectly, documented attribute. It is not an attribute that would have the effect that f[x]=x, as can be seen in your GCD example. According to the documentation, it is an attribute that can be assigned to a symbol f to indicate that f[x], f[f[x]], etc. are all equivalent to x for the purpose of pattern matching. Therefore, I would expect that the following result to be True:

ClearAll[f];
Attributes[f] = {OneIdentity};
MatchQ[x, f[_]]

(* False *)

After a lot of playing with this attribute, I think that a very prudent attempt to describe the attribute OneIdentity could be:

OneIdentity is an attribute that can be assigned to a symbol f to indicate that f[x, optional value] is used for x for pattern matching.

Here is an example demonstrating this behaviour. Without OneIdentity:

ClearAll[f];
f[x_, y_: 0] := x 2^y;
f[x]
MatchQ[x, HoldPattern[f[_, _ : 0]]]
(* x *)
(* False *)

With OneIdentity:

ClearAll[f];
SetAttributes[f, OneIdentity]
MatchQ[x, HoldPattern[f[_, _ : 0]]]
x /. HoldPattern[ f[a_, b_: 0]] :> {a, b}
(* True *)
(* {x, 0} *)
$\endgroup$
  • $\begingroup$ So what is the "optional value" for GCD[x, optional value] in pattern-amtching? $\endgroup$ – axelclk Jan 11 '15 at 12:35
  • $\begingroup$ @axwlclk The pattern for a default value is _. (underscore dot), so you are looking for the pattern GCD[x, _.]. But MatchQ[x, GCD[x,_.]] returns False, because no default values are defined for GCD. I must admit that I have no idea why GCD has the attribute OneIdentity. It seems to work as well without it. $\endgroup$ – Fred Simons Jan 11 '15 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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