Возможно ли кэширование в рамках чистого FP?

Кеширование, по идее, предусматривает создание некоторой муттабельной структуры, в отличии от мемоизации, насколько я понимаю. Получается, что в FP это невозможно. Таким образом, существует класс задач (или алгоритмов), принципиально нереализуемых в рамках fp. Любопытно было бы узнать, а что еще входит в этот класс? И почему FP, несмотря на эти ограничения, считается тьюринг-полным и эквивалентным, по своим возможностям, императивному программированю? Это миф?