Define an antisymmetric function
Torsten Schoenfeld
set of known objects. I'm having trouble enforcing antisymmetry. Say I
want to define G[_, _] on the objects {a, b, c}:
G[a, b] := f[a, b]
G[a, c] := g[a, c]
G[b, c] := h[b, c]
If I now enforce antisymmetry simply by
G[x_, y_] := -G[y, x]
then it mostly works (e.g., G[b, a] evaluates to -f[a, b]). But if I
apply G to something that is not in {a, b, c}, then I run into an
infinite loop: G[a, f[b]] yields "$RecursionLimit::reclim: Recursion
depth of 256 exceeded."
Ideally, I would like applications to unknown input to stay unevaluated
(e.g., G[a, f[b]] just yields G[a, f[b]]). How can I achieve that while
also enforcing antisymmetry?
Szabolcs Horvát
Hello Torsten,
I do not think that it is possible to do this in a general way. It
might, however, be possible to make it work for the special cases that
you need.
The reason why it is not possible to implement it in a completely
general way is this:
Suppose we input G[a,b], and suppose that there is no definition
associated with G that would allow computing the value of G[a,b]. Now
we need to check if G[b,a] can be computed, and if so, then use the
value -G[b,a] for G[a,b]. But how can we check if G[b,a] "can be
computed", that is, if it evaluates to something different than itself?
If we aim for complete generality, this is only possible by trying to
evaluate G[b,a], which will then trigger the antisymmetry definition
again, and lead to infinite recursion...
So, let's not aim for completely generality. Instead, let's just check
if an *explicit* definition exists for G[b,a] (i.e. for the explicit
values b and a):
G[x_, y_] := -G[y, x] /; hasValue[G[y,x]]
hasValue[f_[args___]] :=
MemberQ[First /@ DownValues[f], Verbatim@HoldPattern[f[args]]]
This will work for simple cases, but it is neither pretty, nor robust.
I hope someone will post a better suggestion.
One more thing that needs to be mentioned is that there is already a
function similar to hasValue[] built into Mathematica: ValueQ[].
However, it cannot be used here because for non-atomic arguments
(anything more complicated than a symbol) it determines if it has a
value by evaluating it and checking whether it has changed. So the
infinite recursion still wouldn't be avoided.
I hope this helps,
Szabolcs
Albert Retey
I think your problem is that G[x_, y_] := -G[y, x] will result in a
infinit recursion, since part of the right hand side will match the left
hand side no matter what arguments you give.
To enforce antisymmetry you could do this, so the pattern will match
only when the arguments are not in canonicial order:
g[b_, a_] /; Not[OrderedQ[{b, a}]] := -g[a, b]
hth,
albert
Leonid Shifrin
here is a little more high-level variation of Szabolcs's solution, which
isn't robust either, since it assumes only Downvalue - based definitions and
that you will not add more general (pattern-based) definitions to G later
on.
ClearAll[G];
G[a, b] := f[a, b]
G[a, c] := g[a, c]
G[b, c] := h[b, c]
G[x_, y_] := -G[y, x] /;
Hold[G[y, x]] =!= (Hold[G[y, x]] /. Most@DownValues[G])
It may however be a little faster since the specific rules (without
patterns) in DownValues are
hash-table based and therefore the rule look-up should be constant time in
the size of the definition list.
Out of curiosity, I also tried to address a different fomulation of your
problem, where for unknown
arguments the function must use antisymmetry, but just once:
G[x,y]->-G[y,x]. The following
hack seems to do it:
In[318]:= Clear[GG];
GG[a,b]:=f[a,b]
GG[a,c]:=g[a,c]
GG[b,c]:=h[b,c]
Module[{tried, reset},
reset[] := (Clear[tried]; tried[_, _] = False);
reset[];
GG[x_, y_] /; ! tried[x, y] := (tried[y, x] = True; -GG[y, x]);
GG[x_, y_] := "" /; reset[];
]
In[323]:= GG[a,b]
Out[323]= f[a,b]
In[324]:= GG[b,a]
Out[324]= -f[a,b]
In[325]:= GG[d,e]
Out[325]= -GG[e,d]
In[326]:= GG[e,d]
Out[326]= -GG[d,e]
One problem with it is that it may keep some garbage in <tried> for
arguments on which
GG has been defined (a,b,c here) - it will still work but consume a little
extra memory.
Regards,
Leonid
2010/2/11 Szabolcs Horv=E1t <szho...@gmail.com>
> On 2010.02.11. 12:53, Torsten Schoenfeld wrote:
Torsten Schoenfeld
> ClearAll[G];
> G[a, b] := f[a, b]
> G[a, c] := g[a, c]
> G[b, c] := h[b, c]
> G[x_, y_] := -G[y, x] /;
> Hold[G[y, x]] =!= (Hold[G[y, x]] /. Most@DownValues[G])
This actually works perfectly fine even if pattern-based definitions are
involved! (Pattern-based definitions appear normally in DownValues.) I
neglected to mention it, but G[_, _] is also supposed to act as a
derivative in both slots, e.g. G[x_, y_^2] := 2 G[x, y] y. Your
approach handles this gracefully: G[x^2, y] yields -2 x G[y, x].
So, thanks a lot! Thanks also for all the other suggestions in this
thread; I learned many nice tricks.
Szabolcs
> On 12.02.10 10:45, Leonid Shifrin wrote:
>
> > ClearAll[G];
> > G[a, c] := g[a, c]
> > G[b, c] := h[b, c]
> > Hold[G[y, x]] =!= (Hold[G[y, x]] /. Most@DownValues[G])
>
> This actually works perfectly fine even if pattern-based definitions are
> involved! (Pattern-based definitions appear normally in DownValues.) I
> neglected to mention it, but G[_, _] is also supposed to act as a
> derivative in both slots, e.g. G[x_, y_^2] := 2 G[x, y] y. Your
> approach handles this gracefully: G[x^2, y] yields -2 x G[y, x].
>
> So, thanks a lot! Thanks also for all the other suggestions in this
> thread; I learned many nice tricks.
I believe that what Leonid referred to when he said that it might not
work if you add pattern based definitions later on was that this
approach assumed that the "antisymmetry definition" is the very last
one in the DownValue list. Mathematica tries to automatically order
definitions from most specific to most general, but this is not always
possible. When it can't do this, it just adds rules to the DownValue
list in the order they were defined. So a general pattern based
definition *may* displace the antisymmetry rule from the very last
position, especially if it is added later. Just be careful with the
order in which definitions are made.
Carl K. Woll
G[a, b] := f[a, b]
G[a, c] := g[a, c]
G[b, c] := h[b, c]
G[a_, b_] /; Signature[{a, b}] == -1 := -G[b, a]
It requires that you give literal definitions for the signature 1
ordering of arguments.
Carl Woll
Wolfram Research
On 2/12/2010 4:46 AM, Leonid Shifrin wrote:
> Hi Torsten,
>
> here is a little more high-level variation of Szabolcs's solution, which
> isn't robust either, since it assumes only Downvalue - based definitions and
> that you will not add more general (pattern-based) definitions to G later
> on.
>
> ClearAll[G];
> G[a, b] := f[a, b]
> G[a, c] := g[a, c]
> G[b, c] := h[b, c]
> G[x_, y_] := -G[y, x] /;
> Hold[G[y, x]] =!= (Hold[G[y, x]] /. Most@DownValues[G])
>
Leonid Shifrin
Szabolcs, thanks for this clarification - I should have been more clear.
I believe that what Leonid referred to when he said that it might not
> work if you add pattern based definitions later on was that this
> approach assumed that the "antisymmetry definition" is the very last
> one in the DownValue list.
Yes, that's exactly what I meant. As soon as we attach some condition of
almost any complexity to the rule, it becomes specific (less specific than only
explicit definitions which do not involve patterns at all and are kept internally
in a hash table), even if it's "host" pattern is very general. Therefore, even
patterns that appear less general than the bare "host" pattern, have a pretty
good chance to be interpreted as more general by Mathematica, and therefore
become the last.
Precisely this happens if for example you add the following definition:
In[75]:=G[x_, a] := (x + a)^2;
In[76]:= DownValues[G]
Out[76]= {HoldPattern[G[a, b]] :> f[a, b],
HoldPattern[G[a, c]] :> g[a, c], HoldPattern[G[b, c]] :> h[b, c],
HoldPattern[G[x_, y_]] :> -G[y, x] /;
Hold[G[y, x]] =!= (Hold[G[y, x]] /. Most[DownValues[G]]),
HoldPattern[G[x_, a]] :> (x + a)^2}
In[77]:= G[d, a]
During evaluation of In[77]:= $RecursionLimit::reclim: Recursion depth of
256 exceeded. >>
During evaluation of In[77]:= $RecursionLimit::reclim: Recursion depth of
256 exceeded. >>
The following version will be somewhat more robust:
ClearAll[G];
G[a, b] := f[a, b]
G[a, c] := g[a, c]
G[b, c] := h[b, c]
Module[{this},
G[x_, y_] :=
-G[y, x] /; (this; True) &&
Hold[G[y, x]] =!= (Hold[G[y, x]] /.
DeleteCases[DownValues[G], _?(! FreeQ[#, this] &)])];
But it resorts to DeleteCases and this will result in some performance hit.
This version can take this extra definition added later:
In[86]:= G[x_, a] := (x + a)^2;
In[87]:= G[b, a]
Out[87]= -f[a, b]
In[88]:= G[d, a]
Out[88]= (a + d)^2
In[89]:= G[a, d]
Out[89]= -(a + d)^2
> Mathematica tries to automatically order
> definitions from most specific to most general, but this is not always
> possible. When it can't do this, it just adds rules to the DownValue
> list in the order they were defined. So a general pattern based
> definition *may* displace the antisymmetry rule from the very last
> position, especially if it is added later. Just be careful with the
> order in which definitions are made.
>
Yes, this is exactly the point. (which I think is well -illustrated by the
examples above).
Best,
Leonid