PatternTest没有优化？

Question

在准备对Mathematica中PatternTest的意外行为的响应时,我遇到了一个意想不到的Mathematica行为.

请考虑:

test = (Print[##]; False) &;
MatchQ[{1, 2, 3, 4, 5}, {x__?test, y__}]

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

False

因为正如西蒙对文献的引用所简明地指出:

在一个形式中,例如__?test匹配的序列中的每个元素__ 必须True在应用测试时产生.

我想知道为什么Mathematica四次分别测试列表的第一个元素.当然,有四种方法可以构成底层模式{x__, y__},如果这是一个Condition测试,那么组成序列的所有元素x都需要进行测试,但我不认为这是这种情况.

逻辑是否认为如果列表的第一个元素失败,PatternTest那么给定的模式不能匹配？

如果它确实成立,为什么Mathematica不进行这种简单的优化？

---

借用尤达的回答中的一个例子,这是另一个看似过度评价的例子:

In[1]:= test2 = (Print@##; Positive@##) &;
MatchQ[{1, 2, 3, 4, -5}, {x__?test2, y__?Negative}]

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

During evaluation of In[1]:= 2

During evaluation of In[1]:= 1

During evaluation of In[1]:= 2

During evaluation of In[1]:= 3

During evaluation of In[1]:= 1

During evaluation of In[1]:= 2

During evaluation of In[1]:= 3

During evaluation of In[1]:= 4

Out[2]= True

我承认以前从未探索过模式匹配的这个方面,而我对此看似无效率感到不安.这真的和它看起来一样糟糕,还是发生了某种自动缓存？ Print似乎表明反对.

• 是否有更有效的基于模式的方式来写这个？

• 正确的模式匹配行为需要这种冗余级别,为什么？

---

我匆忙做了一个错误的断言,但是我离开了,因为下面的好答案解决了它.请在将来的答案中忽略它.

很容易证明在其他情况下进行了类似的优化:

MatchQ[{-1, 2, 3, 4, 5}, {__?Positive, y__?test}]

(没有打印.)

False

在这里,Mathematica正确地从未测试任何元素y.

Answer 1

我想每个人都忘记了测试功能可能产生的副作用.以下是我认为正在发生的事情:正如Mr.Wizard和其他人所提到的,模式可以通过组合方式进行匹配.对于的每个组合{x}和{y},所述x图案被首先测试.顺便说一句,定义多个arguments(##)的函数是没有意义的,因为正如@Simon解释的那样,测试函数被单独应用于序列中的每个元素.这也解释了为什么只打印第一个元素(-1):一旦找到第一个非匹配元素,模式匹配器就会停止并继续测试下一个可用组合.

这是一个更具说明性的例子:

In[20]:= 
MatchQ[{-1,2,3,4,5},{_,x__?(Function[Print[#];Positive[#]])}]
During evaluation of In[20]:= 2
During evaluation of In[20]:= 3
During evaluation of In[20]:= 4
During evaluation of In[20]:= 5

Out[20]= True

现在它打印所有这些,因为该函数逐个应用于它们,就像在这种情况下一样.

现在到了问题的关键.在这里,我设置了一个带副作用的测试函数,它决定在测试第一个元素后改变主意:

Module[{flag = False}, 
  ClearAll[test3]; 
  test3[x_] := 
     With[{fl = flag}, 
        If[! flag, flag = True]; 
        Print[x]; 
        fl
     ]
];

第一个组合({-1},{2,3,4,5}由于函数False首先给出,它将被拒绝.但是第二个组合({-1,2},{3,4,5})将被接受.这正是我们观察到的:

In[22]:= 
MatchQ[{-1,2,3,4,5},{x__?test3,y__}]
During evaluation of In[22]:= -1
During evaluation of In[22]:= -1
During evaluation of In[22]:= 2

Out[22]= True

一旦模式匹配器找到匹配,打印就会停止.

现在,从这里可以明显看出问题中提到的优化和其他一些答案通常是不可能的,因为模式匹配器无法控制测试函数中可能存在的可变状态.

在考虑模式匹配时,我们通常将其视为一个独立于评估的过程,这在很大程度上是正确的,因为模式匹配器是系统的内置组件,一旦模式和表达式评估,就会大量接管绕过主评估循环.然而,有一些值得注意的例外,它使得模式匹配更加强大,其代价是与评估者纠缠在一起.这些包括的用途Condition和PatternTest,因为这两个是主要的评估过程中的"进入点"到从它的模式匹配过程中的否则隔离.一旦模式匹配器击中其中一个,它就会在要测试的条件下调用主评估器,然后一切皆有可能.这让我再次看到模式匹配器在使用PatternTest和Condition不存在的测试时最有效,并且模式完全是语法 - 在这种情况下,它可以优化.