I have been trying to understand how mathematica does pattern matching:

{Sin[x] + 1} /. Sin -> Cos


Cos[x] + 1

I am guessing that the program searches for the expression in the expression tree and then replaces the pattern once it finds it.


  • $\begingroup$ From the documentation of ReplaceAll: ReplaceAll looks at each part of expr, tries all the rules on it, and then goes on to the next part of expr. The first rule that applies to a particular part is used; no further rules are tried on that part or on any of its subparts. $\endgroup$ – vapor Mar 21 '17 at 17:17
  • $\begingroup$ Thanks for your reply, I have read the documentation. I wanted to know how does it look at each part of the expresison does it traverse down the expression tree or it has some other mechanism? $\endgroup$ – Arihant Parsoya Mar 21 '17 at 17:32
  • $\begingroup$ It performs a DFS of the expression tree. (I am not 100% sure since I cannot find an official source) $\endgroup$ – vapor Mar 21 '17 at 17:46
  • $\begingroup$ @happyfish It is not always DFS. It is DFS for functions like Replace, Cases, etc. For ReplaceAll it is actually BFS. $\endgroup$ – Leonid Shifrin Mar 21 '17 at 17:52
  • 1
    $\begingroup$ @LeonidShifrin I think ReplaceAll is not a BFS but rather a depth-first preorder traversal? $\endgroup$ – Mr.Wizard Mar 21 '17 at 18:28

Your Answer

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

Browse other questions tagged or ask your own question.