In typical functional languages state is managed so that it doesn't hurt, not completely absent.

For example, a REPL keeps state in the messages it prints to the terminal and this state isn't visible in the pure function definitions and expression the program is concerned with.

You don't have to throw away the result. That's what the State Monads are for. Immutable State is Ok. Memoization is Ok.