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