Explain Condition (/;) strange behaviour?

Questions
1

Can someone explain the behaviour of Condition (/:wink: in the following sample code:

Clear[fu];
fu[c_ /; FreeQ[c, fu] fu[w]] = ok;
fu[w fu[w] ]

This produces a recursion error.

However, if we bracket the Condition everything is fine:

Clear[fu];
fu[(c_ /; FreeQ[c, fu]) fu[w]] = ok;
fu[w fu[w] ]

I think it is a problem of precedence, because

Precedence[Condition] < Precedence[Times]

However, how this leads to a recursion is beyond me. Maybe somebody can explain.

2

You might want to explore the FullForms of the alternative expressions to see clearly the difference.

Clear[fu];
c_ /; FreeQ[c, fu] fu[w] // FullForm
fu[c_ /; FreeQ[c, fu] fu[w]] = ok // FullForm
fu[w fu[w]] // FullForm

gives:

Condition[Pattern[c,Blank[]],Times[FreeQ[c,fu],fu[w]]],

ok

$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of FreeQ[w,fu] fu[w].

fu[Times[w,fu[w]]]

Whereas:

Clear[fu];
(c_ /; FreeQ[c, fu]) fu[w] // FullForm
fu[(c_ /; FreeQ[c, fu]) fu[w]] = ok; // FullForm
fu[w fu[w]] // FullForm

gives:

    Times[Condition[Pattern[c,Blank[]],FreeQ[c,fu]],fu[w]]

Null

ok

3

Thanks a lot for your answer.

Due to higher precedence of Times over Condition, “fu[w]” is pulled into the pattern test.

But the question is, why does this lead to a recursion. I would have guessed that the pattern would simply not fit.

4

The recursion in the first code takes place in the pattern, with the code fu[w] in FreeQ[c, fu] fu[w]. In evaluating FreeQ[c, fu] fu[w] to test the pattern, the fu[w] will be evaluated, which will cause another pattern-matching test, which leads to another evaluation of fu[w], and so on.

You didn’t ask for workaround, but if it’s any help, you can prevent fu[w] from evaluating with

fu[c_ /; FreeQ[c, fu] HoldPattern[fu[w]]] = ok;
5

Tanks’s very much. If something does not work out as expected, I always try to understand why. I think that the only way to really understand.

6

You can see the evaluation sequence with the following:

Clear[fu];
fu[c_ /; FreeQ[c, fu] fu[w]] = ok;
Block[{$RecursionLimit = 20},
 fu[w fu[w]] // Trace
 ]

It won’t explain everything by itself, but you can study it to reconcile it with your understanding of the evaluation process. Setting $RecursionLimit to its minimum yields a readable amount of output.