FP code tends to be heavy on recursive algorithms, which means you need mutually tail recursive functions. And laziness. Somebody mentioned the State monad and the IO type. Well, these are lazy abstractions with a memory-safe bind/flatMap operation that makes them tick.
Well, the problem with these abstractions is that they'll require building a data structure that cannot be an array. And in the case of languages like Scala or Clojure that don't have real tail recursion because of the JVM, you need to manage your own trampoline as well. We now have the Free monad, which is awesome, except that it is very heap unfriendly.
Actually for FP you need persistent data structures everywhere, not just lists, like maps, hashes, vectors and all known implementations are some sort of trees. And this is an active area of research, but building cache friendly trees is a hard problem.