5
$\begingroup$

Given

expr = f[x, g[y], z]

In the following query, the pattern h_[__, c_] appears as last slot in Alternatives:

Cases[expr, (h_[c_] | h_[c_, __] | h_[__, c_, __] | h_[__, c_]) :> 
  h -> c, {0, Infinity}]

Gives

{g -> y, f -> x}

Ie, "f[__,z]" is not matched but is matched when the pattern is rotated to the first slot:

Cases[expr, (h_[__, c_] | h_[c_] | h_[c_, __] | h_[__, c_, __]) :> 
  h -> c, {0, Infinity}]

Which gives:

{g -> y, f -> z}

Souldn't Alternatives be commutative? Apparentely only the first match per level is returned. Is there a method to return x, y and z containing patterns?

$\endgroup$
2
  • $\begingroup$ What result are you seeking to obtain, precisely? $\endgroup$
    – mfvonh
    Jun 24, 2014 at 22:35
  • $\begingroup$ {f->x,f->g,f->z,g->y} $\endgroup$ Jun 24, 2014 at 22:36

2 Answers 2

8
$\begingroup$
  • Patterns in Alternatives are tried in order
  • Only the first pattern that matches is "applied" to the expression.
  • Cases does not support multiple patterns outside of Alternatives.

I suppose it could be interesting to debate that design decision but nevertheless that's the way it works at this time.

You could of course search with multiple passes:

expr = f[x, g[y], z]
pat = h_[c_] | h_[c_, __] | h_[__, c_, __] | h_[__, c_];

Join @@ (Cases[expr, # :> h -> c, {0, -1}] & /@ List @@ pat)
{g -> y, f -> x, f -> g[y], f -> z}

Or using ReplaceList and Level:

rules = # :> h -> c & /@ List @@ pat
Join @@ (ReplaceList[#, rules] & /@ Level[expr, {0, -1}])

Since neither of these is efficient you could subvert the normal evaluation by using side-effects, e.g. with Condition:

Module[{f},
  f[pat] := 1 /; Sow[h -> c];
  Reap[Scan[f, expr, {0, -1}]][[2, 1]]
]
{g -> y, f -> x, f -> g[y], f -> z}

Or more cleanly, though perhaps rather enigmatically, using Cases itself:

Reap[Cases[expr, pat :> 1 /; Sow[h -> c], {0, -1}];][[2, 1]]
{g -> y, f -> x, f -> g[y], f -> z}

Finally, if traversal order is irrelevant:

Reap[expr /. pat :> 1 /; Sow[h -> c]][[2, 1]]
{f -> x, f -> g[y], f -> z, g -> y}

A note regarding another ramification of Alternatives is here:


NOTE: It looks like my assumptions about efficiency were wrong, and the multi-pass method may be more efficient than the rest. I need to explore this further but I have neither the time nor the interest right now.

$\endgroup$
8
  • 1
    $\begingroup$ In the last two instances I think you could simplify pat = h_[___, c_, ___], too. $\endgroup$
    – mfvonh
    Jun 24, 2014 at 23:08
  • $\begingroup$ @mfvonh Great point, but I was assuming the given patterns were merely toy examples and I did not wish to tamper with them. $\endgroup$
    – Mr.Wizard
    Jun 24, 2014 at 23:09
  • $\begingroup$ @Mr.Wizard, thanks, this is great. But how to modify so that the output only matches heads like 'f->g' rather than f->g[y]' $\endgroup$ Jun 24, 2014 at 23:33
  • $\begingroup$ @mfvonh, I tried h_[__, c, ___] but it didn't work. $\endgroup$ Jun 24, 2014 at 23:33
  • $\begingroup$ @alancalvitti Why shouldn't f -> g[y] be included? Because g[y] is not atomic? Because g[y] has already matched a pattern? Something else? $\endgroup$
    – Mr.Wizard
    Jun 24, 2014 at 23:36
2
$\begingroup$
Flatten@{Head[expr] -> # & /@ Level[expr, {1}], 
  Thread[Cases[expr, x_[_] -> x] -> Cases[expr, _[x_] -> x]]}
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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