Какова роль стратегии оценки Haskell в Memoization через Representable

Question

Статья Memoization via Representables отлично объясняет, как запоминать рекурсивные функции с помощью Representables. Он начинается с реализации последовательности Фибоначчи как фиксированной точкиfibOp:

      fibOp :: Num a => (Natural -> a) -> (Natural -> a)
fibOp v 0 = 0
fibOp v 1 = 1
fibOp v n = v (n-1) + v (n-2)

fix f = let x = f x in x

fibNaive :: Num a => Natural -> a
fibNaive = fix fibOp  

Эта реализация неэффективна, так как она вычисляет одни и те же значения много раз.

Далее в статье вводятся взаимные обратные функции иstreamIndex(которые позже будут обобщены вRepresentableтип класса). Эти функции позволяют нам реализовать запоминаемые версииfibNaive:

      fibSmart :: Num a => Natural -> a
fibSmart = fix (streamIndex . streamTabulate . fibOp)

И именно в этот момент статья становится несколько «неуклюжей»:

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

Что это означает ? По-видимому, этот метод запоминания работает из-за стратегии ленивых вычислений Haskell и из-за того, что он пытается не вычислять выражения "без необходимости". Например , в этом ответе упоминается, что Haskell вычисляет любое данное выражение не более одного раза за каждый раз, когда вводится окружающее его лямбда-выражение. Однако окружающее лямбда-выражение вводится один раз за итерацию, вызванную окружением.fix, что означало быstreamTabulateпотенциально оценивается несколько раз.

Почему и как работает этот подход? Какой аспект стратегии оценки Haskell он использует?

Answer 1

Ваша функция:

      fibSmart :: Num a => Natural -> a
fibSmart = fix (streamIndex . streamTabulate . fibOp)

действительно может быть расширен путем встраивания(.)к:

      fibSmart = fix (\f -> streamIndex (streamTabulate (fibOp f)))

но лямбда\f -> ...здесь вводится только один раз функцией.

Вы также можете увидеть это, вставивfix:

      fibSmart = let f = streamIndex (streamTabulate (fibOp f)) in f