# How to terminate early a functional computation

Problem description: Given a list $A=\{1,2,0,7,0,-1,2,6,\ldots\}$ and a list $B=\{0,7,0\}$ write a program that determines whether $B$ appears in $A$ or not. Note: the order of $B$'s items does matter.

Functional way:

MemberQ[Partition[A, 3, 1], B]


The disadvantage of this way is that the whole list $A$ is processed even if $B$ is in the very start of $A$. Compare with the following code which terminates early if $B$ is found in $A$:

Procedural way:

found = False;
L = Length@A;
For[i = 1, i <= (L - 2) && !found, i++,
found = Take[A, {i, i + 2}] == B]


Question: Is there a functional way of solving the problem that does not need to scan/process all of $A$'s elements ?

P.S. Feel free to edit the title.

• Not very efficient a = {1, 2, 3, 4}; b = {2, 3, 4}; MatchQ[a, {___, PatternSequence @@ b, ___}] A Boyer-Moore type alg should be better Nov 26 '15 at 21:36
• @belisariushassettled. On cursory reading about Boyer-Moore, it says that there is pre-processing done on the list in order to reduce the number of comparisons done. OP doesn't seem to want pre-processing (though your observation might mean that the OP should want pre-processing instead!). Nov 26 '15 at 21:50
• @march Boyer-Moore preprocesses the needle (i.e., $B$), not the haystack ($A$). Nov 26 '15 at 21:52
• @Pillsy. That's why one shouldn't post comments after a "cursory reading". Nov 26 '15 at 21:53
• @march I was looking for a good example stackoverflow.com/a/6209778/353410 Nov 26 '15 at 21:55

More recent (10.1+) versions of Mathematica feature the SequencePosition function, which can be told to stop after the first match, like so:

SeedRandom;
a = RandomInteger[{1, 10}, 10000];
b = {1, 7, 1};

SequencePosition[a, b, 1] // AbsoluteTiming
(* {0.000175, {{88, 90}}} *)


This is quite a bit faster than the MemberQ/Partition-based approach:

MemberQ[Partition[a, 3, 1], b, {1}] // AbsoluteTiming
(* {0.00199, True} *)


As a word of warning, you can use more general patterns with SequencePosition and similar functions, but as of version 10.3 the performance is only really good with fixed patterns like {1, 7, 1}.

EDIT to add: It seems to provide a similar speedup over other solutions, like in @belisarius' comment:

MatchQ[a, {___, PatternSequence @@ b, ___}] // AbsoluteTiming
(* {0.019747, True} *)

• I'm on V9- Could you please compare this with my cheap solution on the comments? I guess this one is faster, but I'm curious about the improvement Nov 26 '15 at 22:02
• @belisariushassettled on my OS X box with 10.3 this method was Timing 0.000548 whereas the MatchQ timing was 0.027489 Nov 26 '15 at 22:04
• @MikeHoneychurch Thanks a lot! Nov 26 '15 at 22:04
• and the NestWhile methods were 0.019667 with the same a and b lists Nov 26 '15 at 22:06
• you seem to be only seeing a bit over an order of magnitude enhancement whereas on my computer after clearing cache etc. I am seeing two orders of magnitude (??) Nov 26 '15 at 22:08