Why does this pattern for combining two lists require triple underscores (___) to work?

Question

I understand that __ is a list of one or more elements, and that ___ is 0 or more elements, but when I try this rule with 2 underscores I don't get the results I expect.

cartesianProduct[lis1_, lis2_] := 
 ReplaceList[{lis1, lis2}, {{___, x_, ___}, {___, y_, ___}} :> {x, y}]

cartesianProduct[{a, b, c}, {x, y, z}]

(* {{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}, {c, x}, {c, y}, {c, z}} *)

I guess I do not understand the difference between _, __, and ___. Which is the pattern for instructing Mathematica to do what I want?

Answer 1

Let's first look at what a pattern with two underscores, i.e. {__, x_, __} does. You're asking Mathematica to match an expression that has the structure (pseudocode)

{<one or more elements I don't care about>, <call this x>, <one or more elements I don't care about>}

So when you try to match a 3 element list with the above pattern, the only element that will match x is the middle element. x is constrained, because the part that you don't care about, i.e. __ is at least 1 element long on each end. Hence, when you use only __ in your code, you get only {b, y} (i.e., the middle elements in each list) as your output.

What you instead want, is for x to match every possible element in the list. For that, you need to account (somehow) for the fact that if x is the first element in the list, there are no elements (or zero) before it. In order to do this, you need ___ before and after x.