Начальный вопрос. Я немного запутался в следующем: я читал, что метод ленивой оценки GHC (Haskell's?) Включает использование совместного использования, поэтому, например, оценивая выражение
(1+1)*(1+1)
будет вычислять только 1+1 один раз. В книге "Программирование в Хаскелле" Грэма Хаттона объясняется, что это реализуется путем замены обоих вхождений 1+1 на указатель на одну его копию и оценку только одной копии.
Но вычисление n-го числа Фибоначчи на fib n = if (n<2) then n else fib (n-1) + fib(n-2) занимает экспоненциальное время в n. Моя неопределенность выше говорит мне, что, например, fib 5 будет оцениваться следующим образом:
fib 5 => fib 4 + fib 3 => fib 3 + fib 2 + fib 3 => x + fib 2 + x
с x = fib 3 = fib 2 + fib 1 = y + fib 1
so fib 5 = y + fib 1 + y + y + fib 1
с y = fib 2 = fib 1 + fib 0 = 1
so fib 5 = 1 + 1 + 1 + 1 + 1
где x и y были введены как общие значения.
Но этот способ продолжения, хотя и несколько менее эффективный, чем стандартный способ итеративного генерации fib k для 2<=k<=n, явно не привел бы к такому длительному периоду времени, как это делает оценка функции. Так что же с моим пониманием?
