I'm sorry but I still have problem to understand, here is the code I consider :

    expr = g[g[x]];
ReplaceAll[expr, g -> fonction]
ReplaceAll[expr, g[x_] -> fonction[x]]

fonction[fonction[x]]

fonction[g[x]]

I will write what I understand step by step of what is happening : the first ReplaceAll : ReplaceAll[expr, g -> fonction]

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.

Allright, I will look at each part of expr.

• I look at the 0'th part of expr which is the Head : g. I have a matching pattern, g becomes fonction. I don't have to look at subparts of g as I had a matching (but even in this case, g doesn't have subparts so it wouldn't change anything).
• I go at the next part (1st part) of expr : fonction[g[x]][[1]] = g[x] it doesn't match.
• I go at the first subpart of g[x] : g[x][[0]] = g, it matches. I replace. I don't have to look at the subparts of g as it matched. At this point I thus have fonction[fonction[x]]
• I look at the 2ndt part of expr : fonction[fonction[x]][[2]] : it doesn't exist.

Thus the code stops and the function returns : fonction[fonction[x]]

Now for the second ReplaceAll : ReplaceAll[expr, g[x_] -> fonction[x]]

• I look at the 0'th part of expr : g[g[x]][[0]] = g : no matching
• I look at the subparts of g : it doesn't have, so it stops for that.
• Thus, now I look at the 1st part of expr : g[g[x]][[1]] = g[x] It matches : g[x] -> fonction[x]. I thus now have g[fonction[x]]... which I know is wrong.

Here is how I understood the algorithm and I still have a problem. I don't understand what precisely does the algorithm then.

And is the 0'th part really the head or the full expression ? Because in the documentation of Replace for example :

The default value for levelspec in Replace is {0}, corresponding to the whole expression.

Here is my extremly basic understanding of Replace and ReplaceAll.

This post is also a way for me to check if I understood the mechanism behind, if you see mistakes in my explanation don't hesitate to correct me !

Replace is a function that will apply replacement rules on part of expression.

However, it will apply the replacement rules at specific level given in parameters (by default it will be {0} corresponding to the whole tree).

So here :

Replace[x^2 + 1, x^2 -> a]

It doesn't do anything as x^2 is a subpart of the tree but it is not the whole tree in itself.

I could do :

Replace[x^2 + 1, x^2 -> a, All]

To make it work. Then the code will look at all the levels of the trees (thus all the subtrees) and look for a matching replacement.

I could also do :

ReplaceAll[x^2 + 1, x^2 -> a]

And here is my question : is there actually any difference between using

Replace[expr, rule, All]

and

ReplaceAll[expr,rule]

or it is indeed the same thing ?

Here is my extremly basic understanding of Replace and ReplaceAll.

This post is also a way for me to check if I understood the mechanism behind, if you see mistakes in my explanation don't hesitate to correct me !

Replace is a function that will apply replacement rules on part of expression.

However, it will apply the replacement rules at specific level given in parameters (by default it will be {0} corresponding to the whole tree).

So here :

Replace[x^2 + 1, x^2 -> a]

It doesn't do anything as x^2 is a subpart of the tree but it is not the whole tree in itself.

I could do :

Replace[x^2 + 1, x^2 -> a, All]

To make it work. Then the code will look at all the levels of the trees (thus all the subtrees) and look for a matching replacement.

I could also do :

ReplaceAll[x^2 + 1, x^2 -> a]

And here is my question : is there actually any difference between using

Replace[expr, rule, All]

and

ReplaceAll[expr,rule]

or it is indeed the same thing ?

Another question linked to the answer

Then I don't understand this behavior :

diffReplaceReplaceAll = g[g[x]];

Replace[diffReplaceReplaceAll, g -> c, All]

g[g[x]]

g[g[x]][[1]]

g[x]

ReplaceAll[diffReplaceReplaceAll, g -> c]

c[c[x]]

If I take strictly what you say, ReplaceAll shoud return c[g[x]]

Indeed, it goes from the outside which is g[g[x]] (the whole tree), it looks at each part. So first it tries with the Head (the 0 part), which is $g$, it replaces it by $c$. And... it should stop here right ? Thus we would have c[g[x]] as a result. But it continues and replaces the second g. Why ?

My problem is very probably linked to a not fully understanding of what a part precisely is. But if I'm not wrong the 0'th part is the head and the 1st part is g[x] here right ?

I also have a problem with Replace : why if it goes from the inside to the outside I don't have at least g[c[x]] ?

Remark : I don't fully get your example as I'm not familiar with ":>", I am reading about it now.