Re: Flat, OneIdentity Again
- To: mathgroup at smc.vnet.net
- Subject: [mg21680] Re: [mg21637] Flat, OneIdentity Again
- From: Hartmut Wolf <hwolf at debis.com>
- Date: Fri, 21 Jan 2000 04:00:40 -0500 (EST)
- Organization: debis Systemhaus
- References: <200001180735.CAA20333@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Dear Ted, yesterday I answered to your posting (my reply hasn't yet appeared in the group), yet my feeling is, I possible was a little bit to harsh (and was wrong in a certain point). I now wan't to correct this, and hopefully, give some new insight to the problem. What I did, is to implement a *model* of the semantics as described in the _Mathematica_ documentation, and I show that this model -- which also corresponds to our (naive?) expectations -- gives results different from the _Mathematica_ implementation (see below). Hartmut Wolf schrieb: > > Ersek, Ted R schrieb: > > > > Thanks to all who answered my question on Flat and OneIdentity. > > I have more strange behavior on this subject. > > > > At http://support.wolfram.com/Kernel/Symbols/System/Flat.html > > it says in so many words .... > > If (f) has the Flat attribute you better not have a definition like > > f[p_]:=p > > because if you do, then an attempt to evaluate f[1,2] will not work and the > > kernel will have to quit when the infinite iteration limit is exceeded. > > > > In addition I found that you can't even evaluate f[2] in the above case, and > > it doesn't help if (f) also has the OneIdentity attribute! > > > > I wanted to understand just what the kernel is doing to exceed the iteration > > limit when we try to evaluate f[1,2] or f[2] above. The lines below offer > > some clues, but also add to the mystery. I wonder if any of you have an > > explanation. > > > > In[1]:= > > ClearAll[f]; > > Attributes[f]={Flat}; > > > > After the input above (f) has the Flat attribute and no definitions. > > f[1,2] as f[f[1,2]]. > > > > In[3]:= > > f[1,2]/.f[p_]:>{p} > > Out[3]= > > {f[1,2]} > > > > The idea that the pattern matcher treats > > f[1,2] as f[f[1,2]] is sort of verified > > at Out[4] below. > > > > In[4]:= > > MatchQ[f[1,2],f[_f]] > > Out[4]= > > True > > > > But if the pattern matcher treats f[1,2] as f[f[1,2]] > > why doesn't MatchQ return True in Out[4] below ? > > > > In[5]:= > > MatchQ[f[1,2],HoldPattern[f[f[_Integer,_Integer]]]] > > Out[5]= > > False > > > > Even stranger is the next line where the pattern is much more general! > > Notice that is a triple blank inside (f). > > > > In[6]:= > > MatchQ[f[1,2],HoldPattern[f[f[___]]]] > > Out[6]= > > False > > > > All the results above come out the same if (f) has the attributes Flat, > > OneIdentity. > > > > I have a hunch what may be going on here. Perhaps this is a bug. Could it be > > that the part of the pattern matcher that handles Flat is oblivious to > > HoldPattern and checks for a match with the patterns f[_Integer,_Integer] > > and f[___] > > when it should check for a match with f[f[_Integer,_Integer]] and f[f[___]] > > > > respectively in the lines above? > > > > I did all this using Version 4. > > > > -------------------- > > Regards, > > Ted Ersek > > > > On 12-18-99 Mathematica tips, tricks at > > http://www.dot.net.au/~elisha/ersek/Tricks.html > > had a major update > > Hello Ted, > > first, again a citation from The Book. In section 2.3.8 it says: > > Notice that with flat functions such as Plus and Times, Mathematica > automatically handles variable numbers of arguments, so you do not > explicitly need to use double or triple blanks, as discussed in Section > 2.3.7. > > ...to me "you do not explicitly need to use" reads plain "don't" > I refer to my answer <200001180735.CAA20354 at smc.vnet.net> to your first posting "[mg21600] Flat, OneIdentity attributes" <200001170343.WAA13401 at smc.vnet.net> where I had shown that double blanks definitly are not equivalent to a single blank in case of attribute Flat (without OneIdentity). > Now to your obvservations I'd like to add: > > In[1]:= ClearAll[f]; Attributes[f] = {Flat}; > > In[2]:= MatchQ[f[f[1, 2]], f[x : _f]] > Out[2]= True > > In[3]:= MatchQ[f[f[1, 2]], f[x : f[_]]] > Out[3]= False > > Something hard to digest! (It doesn't matter whether you use Blank[] or > BlankSequence[], see quotation above.) > > However > > In[4]:= MatchQ[f[f[1, 2]], f[f[_]]] > Out[4]= True > > In[5]:= MatchQ[f[f[1, 2]], HoldPattern[f[f[_]]]] > Out[5]= False > > Now it is informative to trace these examples. > > In[8]:= MatchQ[f[f[1, 2]], f[f[_]]] // Trace > Out[8]= > {{f[f[1, 2]], f[1, 2]}, {f[f[_]], f[_]}, MatchQ[f[1, 2], f[_]], True} > > Things are brought to a 'normal form' first, and such f[f[_]] is > converted to f[_] first, before matching begins. Now the idea, that the > pattern matcher converts the lhs (of MatchQ, ReplaceAll, etc.) to > f[f[1,2]] and then uses the 'normal' matching algorithm is nowhere > stated in The Book (being our *only* source of documentation). It's an > idea we gain and might use as a catch rule, yet understood literally and > procedurally this might be an illusion! > What is wrong with this statement is, first, S. Wolfram states in his book (4th ed. p.274): Mathematica writes the expression in the form r[r[a, b], r[a, b]] to match the pattern. In[17]:= r[a, b, a, b] /. r[x_, x_] -> rp[x] Out[17]= rp[r[a, b]] --end of quotation-- And second, we are used to respect the publications of Wolfram Inc. e.g. at http://support.wolfram.com/Kernel/Symbols/System/Flat.html as autoritative. There they write: ... For example, in matching the expression f[1,2,3], the pattern matcher will look for matches among the expressions f[1,2,3], or f[f[1,2],3], and so forth. Yet my new results give more support to my speculation > So the pattern matcher might very well use it's own procedures when he > receives its input for a Flat function (in 'normal form'). And now the > presence of the name x in f[x : f[_]]] as well as HoldPattern hinders > the evaluator to generate the appropriate 'normal form' the pattern > matcher needs to go throught its special Flat or Flat & OneIdentity > algorithm. > > Yet, Ted, this might be another illusion, and I'm telling fairy tales. > This is something I regret and want to apologize. Now here the new stuff: ---------------------------------------------- In[1]:= << DiscreteMath`Combinatorica` I define a helper function which generates "the expressions f[1,2,3], or f[f[1,2],3], and so forth" (see above) In[2]:= Attributes[allGroupings] = {HoldAll}; In[3]:= allGroupings[expr_] := Module[{f, c}, c = Join @@ Map[Permutations, Partitions[Length[expr]]]; f[lst_, n_] := (res = {res, Hold[Take[lst, n]]}; Drop[lst, n]); Block[{res = {}}, Fold[f, expr, #]; Head[expr] @@ Flatten[res] // ReleaseHold] & /@ c] In[4]:= Attributes[myReplaceList] = {HoldAllComplete}; In[5]:= myReplaceList[expr_, rules_] := If[MemberQ[myAttributes[Head[expr]], myFlat], Join @@ ((ReplaceList[#, rules]) & /@ allGroupings[Flatten[expr]]), ReplaceList[expr, rules]] This function is my model and has to be compaired with the kernel function ReplaceList! We define f (for the model) and ff (for the build-in): In[6]:= ClearAll[f]; myAttributes[f] = {myFlat}; In[7]:= ClearAll[ff]; Attributes[ff] = {Flat}; Just a test to show that it works: In[8]:= ReplaceList[ff[1, 2, 3, 4, 5] , ff[x_, y_, z_] :> {x, y, z}] Out[8]= {{ff[1], ff[2], ff[3, 4, 5]}, {ff[1], ff[2, 3], ff[4, 5]}, {ff[1, 2], ff[3], ff[4, 5]}, {ff[1], ff[2, 3, 4], ff[5]}, {ff[1, 2], ff[3, 4], ff[5]}, {ff[1, 2, 3], ff[4], ff[5]}} In[9]:= myReplaceList[f[1, 2, 3, 4, 5] , f[x_, y_, z_] :> {x, y, z}] // Sort Out[9]= {{f[1], f[2], f[3, 4, 5]}, {f[1], f[2, 3], f[4, 5]}, {f[1], f[2, 3, 4], f[5]}, {f[1, 2], f[3], f[4, 5]}, {f[1, 2], f[3, 4], f[5]}, {f[1, 2, 3], f[4], f[5]}} (I beg your pardon, for not giving the output in the same order, but certainly -- if we only wanted -- we could do so, at some cost. Yet this is not the point here, as well as the fact, that I didn't treat "myFlat" inside of the rules!) We also redo the example as quoted from The Book: In[10]:= ff[a, b, a, b] /. ff[x_, x_] -> rp[x] Out[10]= rp[ff[a, b]] In[11]:= myReplaceList[f[a, b, a, b], f[x_, x_] -> rp[x]] Out[11]= {rp[f[a, b]]} So here we also get the same. Now we run through a sequence of tests: In[12]:= ReplaceList[ff[ff[1, 2]] , ff[x_] :> {x}] Out[12]= {{ff[1, 2]}} In[13]:= myReplaceList[f[f[1, 2]] , f[x_] :> {x}] Out[13]= {{f[1, 2]}} In[14]:= ReplaceList[ff[ff[1, 2]] , ff[x : _ff] :> {x}] Out[14]= {{ff[1, 2]}} In[15]:= myReplaceList[f[f[1, 2]] , f[x : _f] :> {x}] Out[15]= {{f[1, 2]}} In[16]:= ReplaceList[ff[ff[1, 2]] , ff[x : ff[__]] :> {x}] Out[16]= {} In[17]:= myReplaceList[f[f[1, 2]] , f[x : f[__]] :> {x}] Out[17]= {{f[1, 2]}} different behaviour here! In[18]:= ReplaceList[ff[ff[1, 2]] , HoldPattern[ff[ff[__]]] -> "match!"] Out[18]= {} In[19]:= myReplaceList[f[f[1, 2]] , HoldPattern[f[f[__]]] -> "match!"] Out[19]= {"match!"} again different! ---------------------------------------------- I think, that the model corresponds more to our expectations as suggested with the documentation. So let's say we have a "documentation" error. Yet my greatest critique of The Book is that it is sometimes sort of vague or evasive as e.g. on page 272: "Whenever Mathematica encounters an orderless or commutative function such as Plus or Times in a pattern, it effectively tests all the possible orders of arguments to try and find a match." What does "effectively" mean? The model shows there are cases where it is not "effective". It is this vagueness, I really deplore. Kind regards, Hartmut
- References:
- Flat, OneIdentity Again
- From: "Ersek, Ted R" <ErsekTR@navair.navy.mil>
- Flat, OneIdentity Again