Как haskell управляет памятью рекурсивных вызовов функций

Question

Я работал над проблемой, которая очень выигрывает от получения результатов моих функций, и в моем исследовании я наткнулся на эту статьюЯ ошеломлен тем, насколько просто ядро ​​в разделе «Заметки с рекурсией», а именно:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

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

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

Просто набирая это, у меня болит голова, потому что я не понимаю, почему значение, используемое при расчете fib 2, должно быть доступно при расчете fib 3 или лучше yest fib 100?

Мои интуитивные ощущения говорят мне, что у этого поведения есть две проблемы (я, вероятно, ошибаюсь, но опять же не уверен, почему):

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

Answer 1

Я думаю, что это легче понять, если вы сравните свое определение со следующим:

not_memoized_fib :: Int -> Integer
not_memoized_fib m = map fib [0 ..] !! m
   where fib 0 = 0
         fib 1 = 1
         fib n = not_memoized_fib (n-2) + not_memoized_fib (n-1)

Вышеприведенное определение по сути совпадает с вашим, за исключением того, что оно принимает явный аргумент m. Это так называемое eta-расширение предыдущей функции, и семантически эквивалентно ей. Тем не менее, в оперативном плане это имеет значительно худшую производительность, поскольку здесь не происходит запоминание.

Почему? Итак, ваша функция определяет список map fib [0..] до , принимающий (неявный) входной параметр m, поэтому существует только один список, для всех m, которые мы можем передать позже в качестве аргументов. Вместо этого в not_memoized_fib сначала мы принимаем m в качестве входных данных, а затем определяем список, заставляя функцию создавать список для каждого вызова not_memoized_fib, снижая производительность.

Это даже легче увидетьесли мы используем let и лямбды вместо where. Сравните

memoized :: Int -> Integer
memoized = let
   list = map fib [0..]
   fib 0 = 0
   fib 1 = 1
   fib n = memoized (n-1) + memoized (n-2)
   in \m -> list !! m
   -- ^^ here we take m, after everything is defined,

с его структурой кода lambda ^(*) , с

not_memoized :: Int -> Integer
not_memoized = \m -> let
            -- ^^ here we take m, before everything is defined, so
            -- we define local bindings {list,fib} at every call
   list = map fib [0..]
   fib 0 = 0
   fib 1 = 1
   fib n = not_memoized (n-1) + not_memoized (n-2)
   in list !! m

с символом let внутри лямбда.

В первом случае существует только один список, а во втором - один список для каждого вызова.

---

_{^(*) a searchable term.}

Answer 2

Список, определенный map fib [0..], определяется как часть определения функции, а не создается при каждом вызове функции. Из-за лени, однако, список только "реализован" как необходимый для любого данного вызова.

Скажем, ваш первый вызов memoized_fib 10. Это приведет к тому, что первые 10 чисел Фибоначчи будут фактически вычислены и сохранены в памяти, и они будут оставаться в памяти в течение всей программы. Последующие вызовы с меньшим аргументом не должны ничего вычислять;последующие вызовы с более крупными аргументами должны вычислять только те элементы, которые встречаются позже в списке, чем самый большой из существующих элементов.