###Main Problem

Mr.Wizard posed this question when discussing another problem.

I reproduce the main part of Mr.Wizard's problem here:

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

On evaluation we get the result:

1

1
1
1
False

The result is correct of course, and there should be four possible patterns, but it seems that, though MatchQ already knows the element 1 cannot pass the pattern test, it continues matching 1 three more times.

The extra matching is okay here as evaluation is fast enough, but this will consume a lot of time while matching long lists or dealing with patterns with long evaluation times, such as x__?((Echo[##]; Pause @ 1; False)&)

So the main problem is:

how to speed this process up and aviod repetitive calculation.

###Some more explanation

I think some work-around is needed to get better results:

1. Unlike Condition(/;), PatternTest will check every element in a __?test-like pattern, not putting everything together. Thus this two pattern matching is different, and they give different results:

    MatchQ[{1, 2, 3}, {__?((Echo@{##}; True) &)}];
   
    MatchQ[{1, 2, 3}, {x__ /; (Echo@{x}; True)}];
   

{1}  

    {2}
    {3}
    {1,2,3}

Thus, in most cases, there'll be no problem of interference while using PatternTest; for example, testing 1 in Sequence[1, 2] will usually be the same as testing 1 in Sequence[1, 2, 3]. While in Condition, interference will be significant.

2. There are a few examples of interference. Take, for example, the answer of @Leonid Shifrin under the question I've mentioned at the beginning:

    Module[{flag = False},
      ClearAll[test3]; 
      test3[x_] := 
        With[{fl = flag}, If[! flag, flag = True]; 
        Echo @ x; 
        fl]];
      MatchQ[{-1, 2, 3, 4, 5}, {x__?test3, y__}];
   

-1

    -1
    2

But I think these cases usually won't occur, so I still want to know: are there any methods available to tell Mathematica, "I know testing result of elements will be the same in each trial, SKIP the repeated testing!"?

###Some Notes

• I do NOT need a way to store the result of the pattern test, I'm trying to reduce the testing repetitions.

• The latter one will speed up the simple pattern matching process in long lists considerably; the first one won't, as the pattern test completes in a flash, but there're are simply too many flashes, thus the overall speed is low.

• Actually, the sample match I used as an example, the four tests complete in a flash, so memoizing will not speed things up. But if we can avoid the testing of the latter three 1, the whole process will be 4 times faster!

Additional and related examples

Here is an additional example that may help illustrate the inefficiency of reapplying the same test to the same element.

Replace[
  {1.1, 2.2, 3, 4, 5},
  {a___, x__?((Print[##]; IntegerQ[#]) &), y__} :>
    {{a}, {x}, {y}}
]

1.1

1.1

1.1

1.1

2.2

2.2

2.2

3

{{1.1, 2.2}, {3}, {4, 5}}

This causes an algorithmic explosion in the time taken to process this pattern. In most applications it would be better if each element were only tested once. Observe that a test of a list of 200 elements performs almost twenty thousand tests:

i = 0;
MatchQ[N@Range[200], {a___, x__?((i++; IntegerQ[#]) &), y__}]
i

False

19900

This is not simply a matter handing the somewhat unusual case of a stateful test function (like the one with flag) as it is baked into expressly stateless patterns as well:

Needs["GeneralUtilities`"]

BenchmarkPlot[
  MatchQ[#, {a___, x__Integer, y__}] &,
  RandomReal[99, #] &
  , "IncludeFits" -> True
]