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, в то время как вторая найдёт решение
за два шага.
Подведём итоги. Плюсы вычисления по значению:
• Эффективный расход памяти в том случае если все
составляющие выражения участвуют в вычислении.
• Она не может дублировать вычисления, как стратегия вычисления по имени.
Плюсы вычисления по имени:
• Меньше вычислений в том случае, если при вычислении выражения