Re: Function with attributes Flat and OneIdentity
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg1092] Re: Function with attributes Flat and OneIdentity
- From: villegas (Robert Villegas)
- Date: Sun, 14 May 1995 21:21:32 -0400
- Organization: Wolfram Research, Inc.
Marc Mazzariol <mmazzari at didec14.epfl.ch> writes with a problem using Flat and OneIdentity: > Hello, I'm a student and i'm trying to use mathematica. > > I've a little problem : > > I want to define a function r that has the attributes Flat and OneIdentity so i > write : > Attributes[r] = {Flat,OneIdentity}; > > Now if i ask mathematica for : > r[r[a]] > the result is : > r[a] > But i want to have the result : a (and not r[a]) > > If i ask mathematica for : > r[a] > the result is : > r[a] > But i also want : a (and not r[a]) > > So i've tried to write : > r[x_] := x > > Now if i ask mathematica for : > r[a] > or for : > r[r[a]] > i've the right result : a > > But now there is another problem : > > > if i ask mathematica for : > r[a,a] > mathematica says : > > $IterationLimit::itlim: Iteration limit of 4096 exceeded. > And this because of the attributes of r. > > So my problem is that i want to create a function like Plus : > > Plus has the attributes Flat and OneIdentity > Plus[2] gives 2 (and not Plus[2] like my function r does) > Plus[Plus[2]] gives 2 ( "" "" "" ) > Plus[2,2] gives 4 (and not $Itera... like my function r does) > > How can I do it ???? > > Thanks for help Hello Marc, This came up in a tech support query just last month; a user wanted to create a function with the algebraic properties of Plus: commutative, associative, and identity. ===================== Cause of your problem ===================== OneIdentity isn't involved in your infinite loop; that is caused by Flat along with the rewrite rule r[x_] := x. Here's an illustration: In[1]:= Attributes[r] = Flat Out[1]= Flat In[2]:= r[x_] := x In[3]:= r[1, 2] $IterationLimit::itlim: Iteration limit of 4096 exceeded. Out[3]= Hold[r[1, 2]] The reason this happens is due to one of Flat's purposes: it tries hard to group arguments together in an effort to match your pattern. r[1, 2] doesn't match r[x_], because it has two arguments not one. But if the two arguments are grouped under a head of r, like so r[ r[1, 2] ] then we do have a match for r[x_], with x ==> r[1, 2]. So Flat does that, and your rule fires, returning x, which is r[1, 2]. Now we're back where we started, at r[1, 2]. The process is repeated, ad infinitum. That's the cause of the infinite iteration. A safe way to catch this circular evaluation red-handed is by changing your rule slightly, to one that freezes the evaluation after the first step: In[4]:= r[x_] := Hold[x] In[5]:= r[1, 2] Out[5]= Hold[r[1, 2]] =================== A proposed solution =================== As a solution to your problem, if you just want r to throw out nesting of itself, I think this rule will do it: r[a___, b_r, c___] := Flatten[Unevaluated[r[a, b, c]], 1, r] The reason for the Unevaluated is that the rule uses r[a, b, c] on the right-hand side, which is identical to the left-hand side (minus all the ___ pattern garbage). This is self-referential, so we have to make it sit still until Flatten has a chance to change it (making it no longer identical to the original r[a, b, c] that fired the rule). Now add in your r[x_] := x, and I think you're in business. In[34]:= ClearAll[r] (* ClearAll erases rules, like Clear, but also kills Attributes that might have been set in previous experiments. *) In[35]:= r[a___, b_r, c___] := Flatten[Unevaluated[r[a, b, c]], 1, r] In[36]:= r[x_] := x In[37]:= r[a] Out[37]= a In[38]:= r[a, a] Out[38]= r[a, a] In[39]:= r[r[a], r[b, c], r[d], e] Out[39]= r[a, b, c, d, e] I haven't tortured this attempt, but it worked in simple cases I tried. Let me know if it fails to do what you want. =================================================== More discussion of Orderless, Flat, and OneIdentity =================================================== Orderless, Flat, and OneIdentity are sometimes confusing, so it's worth explaining some of the distinctions. I'll try to give a useful, precise description of their basic design. I do remember seeing one or two strange things when I was in tech support, though (regarding Flat and OneIdentity I think), so there might be points that I'll miss. Orderless and Flat are effectively evaluation rules AND pattern-matching attributes. By "evaluation rules", I mean that they cause expressions to be rewritten even if you haven't given defined any rules for the function. In[48]:= ClearAll[f, g] In[49]:= Attributes[f] = Flat ; Attributes[g] = Orderless Out[49]= Orderless In[50]:= f[f[1, 2], f[3], f[4, 5]] Out[50]= f[1, 2, 3, 4, 5] In[51]:= g[3, 2, 1] Out[51]= g[1, 2, 3] By "pattern-matching attributes", I mean that if you _have_ defined rules for the function, they will reorganize the arguments of an expression in an effort to make it match your pattern, if possible. In[52]:= f[x_, y_] := Hold[x, y] In[53]:= f[1, 2, 3] Out[53]= Hold[f[1], f[2, 3]] In[54]:= g[x_, 1, y_] := Hold[x, y] In[55]:= g[1, 2, 3] Out[55]= Hold[2, 3] The pattern-matching action is the reverse of the evaluation action (grouping instead of flattening for Flat; taking liberties with ordering instead of enforcing a canonical order for Orderless). This important fact is noted by Maeder in the caption to In/Out 3 near the top of p. 150 of _Programming in Mathematica_ (2nd ed). Unlike them, OneIdentity is not by itself a rewrite rule for evaluation. It affects only matching of other rewrite rules, and it doesn't play alone, it is really there to specify which way Flat should go in one case. This is found on p. 232 of The Mathematica Book. I should mention that some people believe OneIdentity should be a rewrite rule as well. The effect of OneIdentity on a Flat function is shown by comparing what value the pattern matches in a simple rule, before and after OneIdentity: In[57]:= ClearAll[f] In[58]:= Attributes[f] = Flat Out[58]= Flat In[59]:= f[x_] := Hold[x] In[60]:= f[1] Out[60]= Hold[f[1]] In[61]:= SetAttributes[f, OneIdentity] In[62]:= f[1] Out[62]= Hold[1] If OneIdentity isn't there, Flat's default behavior is to wrap an extra f around the matched argument. If it is there, then Flat skips the extra f. Robby Villegas