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