Re: Flat, OneIdentity
- To: mathgroup at smc.vnet.net
- Subject: [mg21707] Re: [mg21637] Flat, OneIdentity
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Sun, 23 Jan 2000 01:52:28 -0500 (EST)
- References: <200001180735.CAA20333@smc.vnet.net> <86a9ou$85$5@dragonfly.wolfram.com>
- Sender: owner-wri-mathgroup at wolfram.com
Below I offer an excerpt from my column in Mathematica in Education and
Research, improved in the light of the discussion so far on this topic. It
deals with pattern matching, which has been the main focus of attention, and
the effects on stored rules, raised by Andrzej Kozlowski.
After the excerpt I try the ideas out on recent examples from Andrzej and
Hartmut Wolf (see below the line *************************************).
Besides wanting to understand what is going on myself, I am concened about
whether I can teach other people to make use of these attributes with any
confidence.
Apologies for the length of this communication!
Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565
The behavior of the attributes Orderless and Flat (which is often used with
the attribute OneIdentity) frequently puzzles users. I'll try to sort things
out.
Firstly, Flat and Orderless have two independent effects - to rearrange
expressions and to modify pattern matching.
Let's look at Flat:
ClearAll[f]
Attributes[f] = {Flat};
Rearranging (flattening) expressions is simple
f[f[1], 2]
f[1, 2]
Modifying pattern matching is more complicated:
f[1, 2, 3] /. f[x_, y_] -> F[x, y]
F[f[1], f[2, 3]]
The reasoning here is that although f[1,2,3] does not match f[x_,y_], it
might have come from flattening f[f[1],f[2,3]], which does match f[x_,y_].
Mathematica uses this "f-grouping" for matches with patterns like _, x_, x_h
... which will normally only match a single expression, but it does not use
it for matches with other patterns. For example it is is used below for the
match with x_ but not for the match with y__ .
f[1, 2, 3] /. f[x_, y__] -> F[x, y]
F[f[1], 2, 3]
We might argue that it is unnecessary to change 1 into f[1] for the match
with x_ above, since f[1,2,3] might have come from f[1, f[2,3]].
Mathematica recognizes this: and if we add the attribute OneIdentity then
single elements are not "f-grouped"
Attributes[f] = {Flat, OneIdentity};
f[1, 2, 3] /. f[x_, y_] -> F[x, y]
f[1, 2, 3] /. f[x_, y__] -> F[x, y]
F[1, f[2, 3]]
F[1, 2, 3]
Note also
Attributes[f] = {Flat};
f[1] /. f[x_] -> F[x]
Attributes[f] = {Flat, OneIdentity};
f[1] /. f[x_] -> F[x]
F[f[1]]
F[1]
With assignments, another feature of Flat emerges:
Attributes[f] = {Flat} ; (*attribute set before assignment*)
f[1, x_] = F[x];
{ f[f[1]], f[1, 2, 3] }
{f[1], F[f[2, 3]]}
But
ClearAll[f];
f[1, x_] = F[x];
Attributes[f] = {Flat} ;(* attribute set after assignment*)
{ f[f[1]], f[1, 2, 3]}
{f[1], f[1, 2, 3]}
In both examples f[f[1]] is flattened to f[1]? because when the rule is
applied the evaluator finds Flat in Attributes[f]. But only in the first
example is the stored rule used on f[1,2,3]. The reason for this is that
when the rules were stored, f was evaluated and the then value of
Attributes[f], {Flat}in the first example and { } in the second one, was
invisibly attached to f; and it is this attachment, not the current value
of Attributes[f], that the pattern matcher consults when it has to decide
whether or not the rule is applicable.
We can take this further
ClearAll[f];
Attributes[f] = {Flat} ; (*attribute set before assignment*)
f[1, x_] = F[x];
Attributes[f] = {};
{f[f[1]], f[1, 2, 3] }
{f[f[1]], F[f[2, 3]]}
f[f[1]] was not flattened, because when it was evaluated, Attributes[f] gave
{}. But the stored rule was used on f[1,2,3], because when the rule was
stored Attributes[f] gave {Flat}.
The difference between f's with and different attachments is recognized
when new rules are made
ClearAll[f]
f[1, x_] = G[x];
Attributes[f] = {Flat};
f[1, x_] = F[x];
The second rule, with {Flat} attached to f, has not replaced the first one,
with { } attached.
?f
"Global`f"
Attributes[f] = {Flat}
f[1, x_] = G[x]
f[1, x_] = F[x]
We can replace the second rule
f[1, x_] = F2[x];
?f
"Global`f"
Attributes[f] = {Flat}
f[1, x_] = G[x]
f[1, x_] = F2[x]
and the first one
Attributes[f] = {};
f[1, x_] = G2[x];
?f
"Global`f"
f[1, x_] = G2[x]
f[1, x_] = F2[x]
But Unset ( =.) does not maintain the recognition of the difference; for
although the following deletes the first rule, with { } attached to f:
f[1, x_] =.;
?f
"Global`f"
f[1, x_] = F2[x]
nevertheless, a repeat of f[1,x_]=. removes the remaining rule, which has
{Flat} attached to f:
f[1, x_] =.;
?f
"Global`f"
**************************************************************
*** Hartmut Wolf's examples ***
ClearAll[f]; Attributes[f] = {Flat};
MatchQ[f[f[1, 2]], f[x : _f]]
True
MatchQ[f[f[1, 2]], f[x : f[_]]]
False
Since f[f[1]] is flattened to f[1] before any matchig is attempted let's
look at
MatchQ[f[1, 2], f[x : _f]]
True
MatchQ[f[1, 2], f[x : f[_]]]
False
The first of these uses f-grouping to match x: _f (which is the same as
x_f), so it regards f[1,2] as f[f[1,2]], which matches f[x_f].
The second one finds f[1,2] cannot match f[f[anyting]], so f-grouping is
not used in looking for a match for _ .
For Hartmut's next two examples I shall again change f[f[..]] to f[..].
MatchQ[f[1, 2], f[_]]
True
MatchQ[f[1, 2], HoldPattern[f[f[_]]]]
False
The first one finds f[1,2] might match f[_] and then uses f-grouping to get
the match for _. So we end up trying to match f[f[1,2]] with f[_]], which
succeeds. This is perhaps made clearer with
f[1, 2] /. f[x_] -> h[x]
h[f[1, 2]]
The second one finds that f[1,2] cannot match HoldPattern[f[f[anything]],
so never gets to the question of a match for _ and the use of f-grouping.
*** Andrzej Koslowki's examples ***
ClearAll[f]; Attributes[f] = {Flat};
MatchQ[f[g[3]], f[g[x_Integer]]]
True
This is because x_ is not an element in a pattern f[...] (the rationale for
f-grouping no longer holds).
MatchQ[f[a], f[f[x_]]]
True
MatchQ[f[a], HoldPattern[f[f[x_]]]]
False
Adrzej writes:
"In the first case f[f[x__]] was first replaced by f[x_], then f[a] by
f[f[a]] and a match was found. In the second case f[a] was not replaced by
f[f[a]] at all, so no match was found."
My explanation of behaviour of the second expression is that, leaving aside
Flatness, f[a] does not match HoldPatten[f[f[x_]], so the opportunity to use
f-grouping to get a match for x_ does not arise
- References:
- Flat, OneIdentity Again
- From: "Ersek, Ted R" <ErsekTR@navair.navy.mil>
- Flat, OneIdentity Again