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, 2017 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$ Mar 21, 2017 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, 2017 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$ Mar 21, 2017 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, 2017 at 18:28


Your Answer

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

Browse other questions tagged or ask your own question.