The lack of side-effects and equational reasoning in functional languages let you get a lot of details out of your way.
Actually ... You (kind-of/sort-of) need side effects when implementing a language with higher-order functions. You at least need it for generating fresh variables to avoid free name capture. Yes, I know you can do this with a monad, but this is not going to help a beginner. It's much easier to maintain a global counter that you increment every time you want a fresh variable name.
The way I did it was just recursively pass down an accumulator argument to generate De Bruijn index-like variable names, rather than keeping a global counter
Point taken though that it's a bit simpler with global state
