Когда используется совместное использование GHC?
Начальный вопрос. Я немного запутался в следующем: я читал, что метод ленивой оценки 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, явно не привел бы к такому длительному периоду времени, как это делает оценка функции. Так что же с моим пониманием?
Ответы
Ответ 1
Вы не можете полагаться на устранение общего подвыражения в GHC (по техническим причинам, поскольку использование ленивых значений может привести к утечке пространства).
Хорошим правилом является то, что значения разделяются по имени. Итак, назовите свое подвыражение, например:
n * n
where n = 1 + 1
и вы гарантируете совместное использование.
Обратите внимание, что в вашем простом примере GHC просто вычислил все это во время компиляции. Вышеупомянутое обсуждение действительно относится только к "большим" данным.
Вы можете наблюдать за совместным использованием средств отладки как вакуум. Такие общие значения представляются как кучи выделенных объектов с несколькими ссылками:
![enter image description here]()
