Есть ли способ «сохранить» результаты в Haskell?

Question

Я новичок в Haskell и понимаю, что это (в основном) чистый функциональный язык, который имеет то преимущество, что результаты для функций не будут меняться при нескольких оценках. Учитывая это, я озадачен тем, почему я не могу легко отметить функцию таким образом, чтобы она запоминала результаты ее первой оценки и не должна оцениваться снова каждый раз, когда требуется ее значение.

В Mathematica, например, есть simple idiom для достижения этого:

f[x_]:=f[x]= ... 

но в Haskell, самые близкие вещи, которые я нашел это something like

f' = (map f [0 ..] !!) 
    where f 0 = ... 
     f n = f' ... 

, которые в дополнение к тому, гораздо менее понятным (и, по-видимому, ограниченным аргументами Int?) не сохраняет (кажется) сохранение результатов в рамках интерактивного сеанса.

По общему признанию (и ясно), я не совсем понимаю, что здесь происходит; но наивно, похоже, Хаскель должен иметь какой-то способ, на уровне определения функции, из

• воспользовавшись тем, что его функции являются функции и пропускающие повторное вычисление их результатов, когда они были вычислены , и
• , указывающий на желание сделать это на уровне определения функции с простой и чистой идиомой.

Есть ли способ сделать это в Haskell, которого я не хватает? Я понимаю (вроде), что Haskell не может хранить оценки как «состояние», но почему он не может просто (по сути) переопределить оцениваемые функции как их вычисленное значение?

---

Это вырастает из this question, в которых отсутствие этой функции приводит к ужасной производительности.

Answer 1

Используйте подходящую библиотеку, такую ​​как MemoTrie.

import Data.MemoTrie 

f' = memo f 
where f 0 = ... 
     f n = f' ... 

Это вряд ли менее приятно, чем версия Mathematica, не так ли?

---

Относительно

“, почему она не может просто (в сущности) переопределять оцениваемых функций, чтобы быть их вычисленное значение? ”

Ну, это не так просто. Эти значения должны быть где-то сохранены. Даже для функции Int -значения вы не можете просто выделить массив со всеми возможными значениями –, который не поместился бы в память. Решение списка работает только потому, что Haskell ленив и поэтому допускает бесконечные списки, но это не особенно удовлетворяет, поскольку поиск равен O (n). Для других типов просто безнадежно – вам нужно как-то диагоналиризовать бесконечно бесконечный домен.

Вам нужна более умная организация. Я не знаю, как это делает Mathematica, но, вероятно, использует много “ запатентованной магии ”. Я бы не был так уверен, что он действительно работает так, как вам хотелось бы, для любых входов.

У Haskell, к счастью, есть классы типов, и это позволяет вам точно указать, какой тип нужен, чтобы быть быстро понятным. HasTrie - такой класс.