Haskell: Почему эта работа - пример memoization?

Привет. Я рассматриваю этот пример из Memoization:

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)

Мне просто интересно, почему это работает, потому что для меня, если вы вызываете memoized_fib(n-2), тогда вы "создаете" новый список и делаете что-то с ним, и после вашего возвращения из него список, содержащий частичный результат, исчезнет? Так что memorized_fib(n-1) вообще не выиграет от этого?

Ответ 1

memoized_fib является CAF, который так же хорош, как буквальная константа, избегая создания новых вещей. Нет переменных → нет вещей, чтобы связать новый материал с → нет создания нового материала (в упрощенном виде).

Ответ 2

Я могу объяснить отсутствующее наблюдение, и это может помочь вам понять поведение, которое вы видите. Важно понять, к чему относятся дескрипторы where.

Представленный вами код

memoized_fib = (map fib [0 ..] !!)
    where fib = ...

который desugars на

memoized_fib = let fib = ...
               in \n -> map fib [0 ..] !! n

missingno представил следующее, которое выглядит как простое расширение eta, но это не так!

memoized_fib n = map fib [0 ..] !! n
    where fib = ...

desugars to

memoized_fib = \n -> let fib = ...
                     in map fib [0 ..] !! n

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

Ответ 3

Код, который вы показываете, зависит от конкретного поведения компилятора. Здесь desugaring, как Том Эллис, предложил:

memoized_fib = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)
    in
       (map fib [0 ..] !!)

Ничто не гарантирует, что список map fib [0..] будет повторно использован, то есть "общий". Особенно, когда вы опускаете подпись типа, как и я, делая это полиморфным определением.

Лучше сделать этот список явным, указав ему имя:

memoized_fib n = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = g (n-2) + g (n-1)
          g = (fibs !!)
          fibs = map fib [0 ..]
    in
       g n

Это было обсуждено до.