Unknown - haskell-notes

=>

((1 +2) +3) +4

=>

(3 +3) +4

=>

6 +4

=>

10

А теперь представьте, что мы решили посчитать сумму чисел от 1 до миллиона. Сколько вычислений

нам придётся накопить! В этом недостаток второй стратегии. Но есть и ещё один недостаток, рассмотрим

выражение:

(\x ->add (add x x) x) (add Zerotwo)

Первая стратегия сначала редуцирует выражение add Zerotwo в то время как вторая подставит это

выражение в функцию и утроит свою работу!

Но у второй стратегии есть одно очень веское преимущество, она может вычислять больше выражений

чем вторая. Определим значение бесконечность:

infinity

:: Nat

infinity

= Succinfinity

Это рекурсивное определение, если мы попытаемся его распечатать мы получим бесконечную последо-

вательность Succ. Чем не бесконечность? Теперь посмотрим на выражение:

isZero infinity

Первая стратегия захлебнётся, вычисляя аргумент функции isZero, в то время как вторая найдёт решение

за два шага.

Подведём итоги. Плюсы вычисления по значению:

• Эффективный расход памяти в том случае если все

составляющие выражения участвуют в вычислении.

• Она не может дублировать вычисления, как стратегия вычисления по имени.

Плюсы вычисления по имени:

• Меньше вычислений в том случае, если при вычислении выражения

участвует лишь часть составляющих.

• Большая выразительность. Мы можем вычислить больше значений.

Какую из них выбрать? В Haskell пошли по второму пути. Всё-таки преимущество выразительности языка

оказалось самым существенным. Но для того чтобы избежать недостатков стратегии вычисления по имени

оно было модифицировано. Давайте посмотрим как.

9.2 Вычисление по необходимости

Вернёмся к выражению:

(\x ->add (add x x) x) (add Zerotwo)

Нам нужно как-то рассказать функции о том, что имя x в её теле указывает на одно и то же значение. И

если в одном из x значение будет вычислено переиспользовать эти результаты в других x. Вместо значения мы

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

Напомню, что мы по-прежнему вычисляем значение сверху вниз, сейчас мы просто хотим избавиться от

проблемы дублирования. Вернитесь к примеру с вычислением по имени и просмотрите его ещё раз. Обратите

внимание на то, что значения вычислялись лишь при сопоставлении с образцом. Мы вычисляем верхний

конструктор аргумента лишь для того, чтобы понять какое уравнение для foldNat выбрать. Теперь мы будем

хранить ссылку на (add Zerotwo) в памяти и как только, внешняя функция запросит верхний конструктор

мы обновим значение в памяти новым вычисленным до корневого конструктора значением. Если в любом

другом месте функции мы вновь обратимся к значению, мы не будем его перевычислять, а сразу вернём

конструктор. Посмотрим как это происходит на примере:

Вычисление по необходимости | 145

--

выражение

| память:

--------------------------------------------|-------------------------

(\x ->add (add x x) x) M

| M =(add Zerotwo)

-- подставим ссылку в тело функции

|

=>

add (add M M) M

|

-- раскроем самый верхний синоним

|

=>

foldNat (add M M) Succ M

|

-- для foldNat узнаем верхний конструктор

|

-- последнего аргумента (пропуская

|

-- промежуточные шаги, такие же как выше)

|

=>

| M

= Succ M1

| M1 =foldNat Succ Zeroone

-- по M выбираем второе уравнение

|

=> Succ(foldNat (add M M) Succ M1)

|

-- запросим следующий верхний конструктор:

|

=>

| M

= Succ M1

| M1 = Succ M2

| M2 =foldNat Succ Zerozero

-- по M1 выбираем второе уравнение

|

=> Succ( Succ(foldNat (add M M) Succ M2))

|

-- теперь для определения уравнения foldNat |

-- раскроем M2

|

=>

| M

= Succ M1

| M1 = Succ M2

| M2 = Zero

-- выбираем первое уравнение для foldNat:

|

=> Succ( Succ(add M M))

|

-- раскрываем самый верхний синоним:

|

=> Succ( Succ(foldNat M Succ M))

|

-- теперь, поскольку M уже вычислялось, в

|

-- памяти уже записан верхний конструктор,