wolfram-mathematica - PatternTest没有优化吗？

在准备对An unexpected behavior of PatternTest in Mathematica的回复时，我遇到了我自己的意外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

Since, as Simon's quote of the documentation concisely states:

I am wondering why Mathematica is testing the first element of the list four separate times. Of course there are four ways to make up the underlying pattern {x__, y__} and if this were a Condition test then all elements that make up the sequence x would need to be tested, but I don't think that is the case here.

Does the logic not hold that if the first element of the list fails PatternTest then given pattern cannot match?

If it does hold, why is Mathematica not making this simple optimization?

Borrowing an example from yoda's answer, here is another example of what appears to be excess evaluation:

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似乎表明对此表示反对。

是否有更有效的基于模式的方式来编写此代码？

为实现正确的模式匹配行为，是否需要这种级别的冗余？为什么？

我匆忙作出了一个错误的断言，但我留下了它，因为下面有很好的答案解决了这个问题。请在以后的答案中忽略它。

最佳答案

我认为每个人都忘记了测试功能中可能出现的副作用。我认为这是正在发生的事情:正如Wizard先生和其他人所提到的，模式可以有几种匹配方式，只是组合起来即可。对于{x}和{y}的每种组合，首先测试x模式。顺便说一句，定义多个参数的函数(##)没有意义，因为正如@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

图案匹配器找到匹配项后，打印就会停止。

现在，从这里必须显而易见的是，问题和某些其他答案中提到的优化通常是不可能的，因为模式匹配器无法控制测试功能中可能存在的可变状态。

考虑模式匹配时，我们通常将其视为与评估分开的过程，这在很大程度上是正确的，因为模式匹配器是系统的内置组件，一旦模式和表达式求值，它将接手并在很大程度上绕过主评估循环。但是，还有一些值得注意的异常(exception)，它们使模式匹配更加强大，但代价是使它与评估器纠缠在一起。这些包括Condition和PatternTest的使用，因为这两个是主要评估过程进入与模式匹配过程隔离的“入口点”。模式匹配器一旦击中其中之一，就会在要测试的条件下调用主评估器，然后一切皆有可能。这再次让我发现，当不使用PatternTest和Condition进行测试并且模式完全语法化时，模式匹配器是最有效的-在这种情况下，它可以优化。

关于wolfram-mathematica - PatternTest没有优化吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8484299/