Functional Programming, Haskell, Computer Science, Lambda Calculus, Algorithms.
not a constant-time operation. First, because the substitution procedure must traverse over body, which can have any arbitrary size. Second, because it must fully copy arg for each occurrence of x. If implemented naively, that’s a quadratic amount of work. Beta-reduction does way too many things at