10
=>
10
144 | Глава 9: Редукция выражений
Теперь посмотрим на вторую стратегию:
sum [1,2,3,4] 0
=>
sum [2,3,4]
0+1
=>
sum [3,4]
(0+1)+2
=>
sum [4]
((0+1)+2)+3
=>
sum []
(((0+1)+2)+3)+4
=>
(((0+1)+2)+3)+4
=>
((1+2)+3)+4
=>
(3+3)+4
=>
6+4
=>
10
А теперь представьте, что мы решили посчитать сумму чисел от 1 до миллиона. Сколько вычислений
нам придётся накопить! В этом недостаток второй стратегии. Но есть и ещё один недостаток, рассмотрим
выражение:
(\x -> add (add x x) x) (add Zero two)
Первая стратегия сначала редуцирует выражение add Zero two в то время как вторая подставит это
выражение в функцию и утроит свою работу!
Но у второй стратегии есть одно очень веское преимущество, она может вычислять больше выражений
чем вторая. Определим значение бесконечность:
infinity
:: Nat
infinity
= Succ infinity
Это рекурсивное определение, если мы попытаемся его распечатать мы получим бесконечную последо-
вательность Succ. Чем не бесконечность? Теперь посмотрим на выражение:
isZero infinity
Первая стратегия захлебнётся, вычисляя аргумент функции isZero, в то время как вторая найдёт решение
за два шага.
Подведём итоги. Плюсы вычисления по значению:
• Эффективный расход памяти в том случае если все
составляющие выражения участвуют в вычислении.
• Она не может дублировать вычисления, как стратегия вычисления по имени.
Плюсы вычисления по имени:
• Меньше вычислений в том случае, если при вычислении выражения
участвует лишь часть составляющих.
• Большая выразительность. Мы можем вычислить больше значений.
Какую из них выбрать? В Haskell пошли по второму пути. Всё-таки преимущество выразительности языка
оказалось самым существенным. Но для того чтобы избежать недостатков стратегии вычисления по имени
оно было модифицировано. Давайте посмотрим как.
9.2 Вычисление по необходимости
Вернёмся к выражению:
(\x -> add (add x x) x) (add Zero two)
Нам нужно как-то рассказать функции о том, что имя x в её теле указывает на одно и то же значение. И
если в одном из x значение будет вычислено переиспользовать эти результаты в других x. Вместо значения мы
будем передовать в функцию ссылку на область памяти, которая содержит рецепт получения этого значения.
Напомню, что мы по-прежнему вычисляем значение сверху вниз, сейчас мы просто хотим избавиться от
проблемы дублирования. Вернитесь к примеру с вычислением по имени и просмотрите его ещё раз. Обратите
внимание на то, что значения вычислялись лишь при сопоставлении с образцом. Мы вычисляем верхний
конструктор аргумента лишь для того, чтобы понять какое уравнение для foldNat выбрать. Теперь мы будем
хранить ссылку на (add Zero two) в памяти и как только, внешняя функция запросит верхний конструктор
мы обновим значение в памяти новым вычисленным до корневого конструктора значением. Если в любом
другом месте функции мы вновь обратимся к значению, мы не будем его перевычислять, а сразу вернём
конструктор. Посмотрим как это происходит на примере:
Вычисление по необходимости | 145
--
выражение
| память:
--------------------------------------------|-------------------------
(\x -> add (add x x) x) M
| M = (add Zero two)
-- подставим ссылку в тело функции
|
=>
add (add M M) M
|
-- раскроем самый верхний синоним
|
=>
foldNat (add M M) Succ M
|
-- для foldNat узнаем верхний конструктор
|
-- последнего аргумента (пропуская
|
-- промежуточные шаги, такие же как выше)
|
=>
| M
= Succ M1
| M1 = foldNat Succ Zero one
-- по M выбираем второе уравнение
|
=> Succ (foldNat (add M M) Succ M1)
|
-- запросим следующий верхний конструктор:
|
=>
| M
= Succ M1
| M1 = Succ M2
| M2 = foldNat Succ Zero zero
-- по M1 выбираем второе уравнение
|
=> Succ (Succ (foldNat (add M M) Succ M2))
|
-- теперь для определения уравнения foldNat |
-- раскроем M2
|