list manipulation - Mysterious behaviour of Pick

As everyone knows, Pick can do amazing things, The most fascinating phenomenon is that it can pick though all sorts of lists:

The basic & pattern matching:

Pick[{4, 5, 6}, {1, 2, 1}, 1]
(*{4,6}*)

Pick[{4,5,6},{1,2,3},_?(#<3&)]
(*{4,5}*)

The most facinating thing is that it can match through ragged list and you can even make the thing you want to pick almost arbitraryly!

Pick[{2, {3, 4}}, {3, {4, 5}}, 5]
(*{{4}}*)


Pick[{2, {3, 4}}, {3, {4, 5}}, {4, 5}]
(*{{3,4}}*)

But the mysterious behaviour occurs here:

Sometimes we need to Pick from Complex ragged lists with list as its element, and sometime we need to Pick according to similar lists. It's quite hard to handle for Pick, but most times it do perfectly. In the following case, it successfully pick through multiple levels and all sorts of pattern:

Pick[{{1, 2}, {2, 3}, {5, 6}}, {{1}, {2, 3}, {{3, 4}, {4, 5}}}, {1} | 2 | {4, 5}]
(*{{1, 2}, {2}, {6}}*)

As you can see, it can match through {1} | 2 | {4, 5}. It's quite natural to think that if we only want to match one of them, for example, {4,5}, it would be quite easy and the result should be {{},{},{6}}, but actually it simply won't do the job and return error message telling me that the shape is not the same:

Pick[{{1, 2}, {2, 3}, {5, 6}}, {{1}, {2, 3}, {{3, 4}, {4, 5}}}, {4, 5}]

Is this a bug and how to solve this problem? Or maybe it's too hard for computer to find a proper match shape with the mere information I give it?

Answer

This is not a bug. It is a consequence of the manner in which Pick scans its arguments.

The Pick Process

The documentation for Pick calls its arguments list, sel and patt. Pick scans the list and sel expressions lock-step in a top-down, left-to-right fashion. It proceeds roughly as follows:

1. The entire sel expression is checked to see if it matches patt. If it does, then list is returned as the result.


2. If either list or sel are atomic, the result is Sequence[] and the scan stops.



3. If this point is reached, both list and sel have subparts that can be scanned. However, if the lengths of the expressions are not the same then the process is aborted with the Pick::incomp message. Note that the heads do not have to match -- just the number of subparts.


4. If this point is reached, both list and sel have the same number of subparts. The whole process is repeated recursively for corresponding pairs of elements in the two expressions. Successfully picked subparts of list are gathered into a resultant expression whose head is the same as the head of list. Note that recursive occurrences of Sequence[] from step 2 will cause mismatches to be dropped out of the final result.

The Cases At Hand

Let us first consider this expression, which "works":

Pick[
  {{1, 2}, {2, 3}, {5     , 6     }}
, {{1   }, {2, 3}, {{3, 4}, {4, 5}}}
, {1} | 2 | {4, 5}
]


(* {{1, 2}, {2}, {6}} *)

(Step 1) The entire sel expression ({{1}, {2, 3}, {{3, 4}, {4, 5}}}) is checked to see if it matches the pattern. It does not.

(Step 2) Neither list nor sel is atomic, so scanning descends to the next level.

(Step 3) Both list and sel have three elements, so the shapes are compatible. A resultant object will be created using the head of list, namely List.

(Step 4) The whole process is repeated for corresponding elements from list and sel:

(Element 1 - Step 1) The first element of sel ({1}) is checked to see if it matches the pattern. It does, so the first element of list ({1, 2}) is added to the resultant List from step 4 above.

(Element 2 - Step 1) The second element of sel {2, 3} is checked to see if it matches the pattern. It does not.

(Element 2 - Step 2) Neither the second element of sel ({2, 3}) nor its list partner ({2, 3}) are atomic so the process continues.

(Element 2 - Step 3) The elements {2, 3} and {2, 3} have the same length so the process continues.

(Element 2 - Step 4) A resultant expression will be constructed with the head List and scanning recurses down to the next level.

(Element 2, 1 - Step 1) The sel element 2 matches the pattern and the corresponding list element 2 is added to the result.

(Element 2, 2 - Step 1) The element 3 does not match the pattern.

(Element 2, 2 - Step 2) The element 3 is atomic, so Sequence[] (i.e. nothing) is contributed to the result. This is the last element in this sublist, so this recursive subprocess is complete.

(Element 3 - Step 1) The third element of sel ({{3, 4}, {4, 5}}) does not match the pattern.

(Element 3 - Step 2) Neither the third element of sel nor its list partner {5, 6} are atomic so the process continues.

(Element 3 - Step 3) The two lists have compatible lengths so the process continues.

(Element 3 - Step 4) A resultant expression will be constructed with the head List and scanning recurses down to the next level.

(Element 3, 1 - Step 1) {3, 4} does not match the pattern so Sequence[] (i.e. nothing) is contributed to the result.

(Element 3, 2 - Step 1) {4, 5} matches the pattern so the corresponding expression 6 is contributed to the result.

At this point, list and sel have been scanned entirely. The final result is returned.

Now let us consider the expression that "does not work":

Pick[
  {{1, 2}, {2, 3}, {5     , 6     }}
, {{1   }, {2, 3}, {{3, 4}, {4, 5}}}
, {4, 5}
]

(* Pick::incomp: Expressions have incompatible shapes. *)

The first four steps proceed exactly as in the preceding example. Scanning descends recursively into the subparts of list and sel. However, trouble arises when processing the first pair of subparts. {1} does not match the pattern, so the process wants to descend recursively again. But the sel expression {1} does not have the same number of parts as the list expression {1, 2}. Thus, the process aborts with the "incompatible shapes".

Is this all detailed in the documentation?

Umm, maybe?? I can't find it.

Okay then, is any of this observable?

Yes! The following helper function is useful to get a peek into the internals of any pattern-matching process:

tracePattern[patt_] :=
    _?(((Print[#, " ", #2]; #2)&)[#, MatchQ[#, patt]]&)

It looks ugly, but its operation is simple: it returns a pattern that matches the same things as its argument, but prints out each candidate expression with its matching status. For example:

Cases[{1, 2, 3}, tracePattern[2]]

(* 1 False
   2 True
   3 False

   {2}
 *)

Note: this is a simplistic implementation that is good enough for the present discussion. A more robust implementation would have to account for the possibility of evaluation leaks and other sordid eventualities.

Here tracePattern is being used to snoop on the Pick expression that "works":

Pick[
  {{1, 2}, {2, 3}, {5     , 6     }}
, {{1   }, {2, 3}, {{3, 4}, {4, 5}}}
, tracePattern[{1} | 2 | {4, 5}]
]

(* {{1},{2,3},{{3,4},{4,5}}} False
   {1} True
   {2,3} False

   2 True
   3 False
   {{3,4},{4,5}} False
   {3,4} False
   {4,5} True

   {{1,2},{2},{6}}
 *)

And here is the expression that "does not work":

Pick[
  {{1, 2}, {2, 3}, {5     , 6     }}
, {{1   }, {2, 3}, {{3, 4}, {4, 5}}}
, tracePattern[{4, 5}]
]

(* {{1},{2,3},{{3,4},{4,5}}} False
   {1} False

   Pick::incomp: Expressions have incompatible shapes.

*)

A close inspection of these results, along with similar traces for the other Pick expressions in the question, will reveal that the processing follows the steps outlined above.