Do they re-typecheck, in the example above K(M) and K(N)?
Yes, they do. It’s not that bad, though. The typechecker knows that K(M) is an application of K to M. It knows what the type of K is, and that should be a function type. It knows what the type of M is, and it can check that that’s the same as the input type of the function. So it knows that K(M) has the output type of K.
The typechecker also knows that K(N) is an application of K to N. It knows that K(N) has the same type as K(M). And it knows that x(y) is an application of x to y. It knows that x has a function type and that y has the same type as x‘s input type. So it knows that x(y) has the same type as x‘s output type. So it knows that the entire expression has the same type as K‘s output type.
Isn’t that time-consuming?
Not really. The typechecker doesn’t have to check the entire expression before it can start typechecking. It can check subexpressions as it goes, and it can do some caching to avoid rechecking subexpressions that it’s already checked.
And does it require passing an environment around? Do they use maps from AST nodes to type information to avoid re-running type checking?
Yes, they do. And they do use maps from AST nodes to type information, but they don’t use them to avoid re-running type checking. They use them to avoid running the same type checking on the same expression twice. (That might be the same thing, I’m not entirely sure.)