9
$\begingroup$

I have a list of stuff.

list = {a, b, b, a, b, a, a, a, b, a};

I want to split it up into subsequences where a single a is followed by zero or more bs. It's a perfect job for SequenceCases:

SequenceCases[list, {a, b ...}]
(* {{a, b, b}, {a, b}, {a}, {a}, {a, b}, {a}} *)

Now I can use a RuleDelayed argument to do something to each subsequence.

SequenceCases[list, seq : {a, b ...} :> f[seq]]
(* {f[{a, b, b}], f[{a, b}], f[{a}], f[{a}], f[{a, b}], f[{a}]} *)

Let's use this to consecutively number the subsequences.

count = 1;
SequenceCases[list, seq : {a, b ...} :> (count++ -> seq)]
(* {1 -> {a, b, b}, 4 -> {a, b}, 6 -> {a}, 7 -> {a}, 8 -> {a, b}, 10 -> {a}} *)

Wait, what? Maybe Sow/Reap can shed some light:

count = 1;
Last@Reap[
  SequenceCases[list, seq : {a, b ...} :> Sow[seq, count++]],
  _, Rule]

(* {1 -> {{a, b, b}}, 2 -> {{a, b}}, 3 -> {{a}}, 4 -> {{a, b}}, 
    5 -> {{a}}, 6 -> {{a}}, 7 -> {{a}}, 8 -> {{a, b}}, 9 -> {{a}}, 
    10 -> {{a}}}*)

For some reason it's evaluating the right-hand side of that rule for each subsequence that matches at all, but only keeping the ones that are the longest. There's nothing in the documentation that specifies what SequenceCases will do if a RuleDelayed argument has side effects, but this behavior is still quite surprising and seems undesirable.

(There is, at least, an easy work-around with Map[Replace[rule]], but it's likely to be verbose and repetitive.)

$\endgroup$
2
  • $\begingroup$ maybe count = 1;SequenceCases[list, seq : {a, b ...} :> (count++ -> seq), Overlaps -> All] can explain what is going on? $\endgroup$ – kglr Mar 19 '20 at 23:37
  • 1
    $\begingroup$ That seems like an explanation but it's also bizarre behavior, and might even qualify as a bug. $\endgroup$ – Pillsy Mar 19 '20 at 23:51
7
$\begingroup$
count = 1;
SequenceCases[list, seq : {a, b ...} :> (count++ -> seq), Overlaps -> All]

{1 -> {a, b, b}, 2 -> {a, b}, 3 -> {a},
4 -> {a, b}, 5 -> {a},
6 -> {a},
7 -> {a},
8 -> {a, b}, 9 -> {a},
10 -> {a}}

SequenceCases >> Details and Options

enter image description here

$\endgroup$
1
  • 5
    $\begingroup$ +1. In v12.x, the core of the algorithm can be seen in the definition of Language`SequencesDump`sequenceCasesPattern. First all possible sublists are found but then that result is possibly trimmed down depending upon the setting of Overlaps. The present implementation is straight-forward, but as the question shows the extra sublists are wasteful at best and harmful at worst. $\endgroup$ – WReach Mar 19 '20 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.