converge :: (Ord a, Num a) => a -> [a] -> a
converge eps (a:b:xs)
| abs (a — b) <= eps
= a
| otherwise
= converge eps (b:xs)
Поскольку список бесконечный мы можем не проверять случаи для пустого списка. Итоговое решение:
roots :: (Ord a, Num a) => a -> a -> (a -> a) -> a
roots eps x0 f = converge eps $ iterate f x0
За счёт ленивых вычислений функции converge и iterate работают синхронно. Функция converge запра-
шивает новое значение и iterate передаёт его, но только одно! Найдём решение какого-нибудь уравнения.
Запустим интерпретатор. Мы ленимся и не создаём новый модуль для такой “большой” функции. Опреде-
ляем её сразу в интерпретаторе.
Prelude> let converge eps (a:b:xs) = if abs (a—b)<=eps then a else converge eps (b:xs) Prelude> let roots eps x0 f = converge eps $ iterate f x0
Найдём корень уравнения:
x( x ? 2) = 0
x 2 ? 2 x = 0
1 x 2 = x
2
Prelude> roots 0.001 5 (x -> x*x/2)
Метод завис, остаётся только нажать ctrl+c для остановки. На самом деле есть одно условие для сходи-
мости метода. Метод сойдётся, если модуль производной функции f меньше единицы. Иначе есть возмож-
ность, что мы будем бесконечно генерировать новые подстановки. Вычислим производную нашей функции:
d 1 x 2 = x
dx 2
Нам следует ожидать решения в интервале от минус единицы до единицы:
Prelude> roots 0.001 0.5 (x -> x*x/2)
3.0517578125e-5
Мы нашли решение, корень равен нулю. В этой записи Ne-5 означает N · 10 ? 5
9.5 Краткое содержание
В этой главе мы узнали о том как происходят вычисления в Haskell. Мы узнали, что они ленивые. Всё
вычисляется как можно позже и как можно меньше. Такие вычисления называются вычислениями по необ-
ходимости.
Также мы узнали о вычислениях по значению и вычислениях по имени.
• В вычислениях по значению редукция проводится от листьев дерева выражения к корню
• В вычислениях по имени редукция проводится от корня дерева выражения к листьям.
152 | Глава 9: Редукция выражений
Вычисление по необходимости является улучшением вычисления по имени. Мы не дублируем выражения
во время применения. Мы сохраняем значения в памяти и подставляем в функцию ссылки на значения. После
вычисления значения происходит его обновление в памяти. Так если в одном месте выражение уже было
вычислено и мы обратимся к нему по ссылке из другого места, то мы не будем перевычислять его, а просто
считаем готовое значение.
Мы познакомились с терминологией процесса вычислений. Выражение может находится в нормальной
форме. Это значит что оно вычислено. Может находится в слабой заголовочной нормальной форме. Это значит,
что мы знаем хотя бы один конструктор в корне выражения. Также возможно выражение ещё не вычислялось,
тогда оно является отложенным (thunk).
Суть ленивых вычислений заключается в том, что они происходят синхронно. Если у нас есть композиция
двух функций:
g ( f x)
Внутренняя функция f не начнёт вычисления до тех пор пока значения не понадобятся внешней функции
g. О последствиях этого мы остановимся подробнее в отдельной главе. Значения могут потребоваться только
при сопоставлении с образцом. Когда мы хотим узнать какое из уравнений нам выбрать.
Иногда ленивые вычисления не эффективны по расходу памяти. Это происходит когда выражение состоит
из большого числа подвыражений, которые будут вычислены в любом случае. В Haskell у нас есть способы
борьбы с ленью. Это функция seq, энергичные образцы и энергичные типы данных.
Функция seq:
seq :: a -> b -> b
Сначала приводит к слабой заголовочной форме свой первый аргумент, а затем возвращает второй.
Взрывные образцы выполняют те же функции, но они используются в декомпозиции аргументов или в объ-
явлении типа.
9.6 Упражнения
• Потренируйтесь в понимании того как происходят ленивые вычисления. Вычислите на бумаге следу-
ющие выражения (если это возможно):
– sum $ take 3 $ filter (odd . fst) $ zip [1 .. ] [1, undefined, 2, undefined, 3, undefined,
undefined]
– take 2 $ foldr (+) 0 $ map Succ $ repeat Zero
– take 2 $ foldl (+) 0 $ map Succ $ repeat Zero
• Функция seq приводит первый аргумент к СЗНФ, убедитесь в этом на таком эксперименте. Определите
тип:
data TheDouble = TheDouble { runTheDouble :: Double }
Он запаковывает действительные числа в конструктор. Определите для этого типа экземпляр класса
Num и посмотрите как быстро будет работать функция sum’ на таких числах. Как изменится скорость
если мы заменим в определении типа data на newtype? как изменится скорость, если мы вернём data,
но сделаем тип TheDouble энергичным? Поэкспериментируйте.
• Посмотрите на приведение к СЗНФ в энергичных типах данных. Определите два типа:
data Strict a = Strict ! a
data Lazy
a = Lazy
a
И повычисляйте в интерпретаторе различные значения с undefined, const, ($! ) и seq:
> seq (Lazy undefined) ”Hi”
> seq (Strict undefined) ”Hi”
> seq (Lazy (Strict undefined)) ”Hi”
> seq (Strict (Strict (Strict undefined))) ”Hi”
• Посмотрите на такую функцию вычисления суммы всех чётных и нечётных чисел в списке.
Упражнения | 153
sum2 :: [Int] -> (Int, Int)
sum2 = iter (0, 0)
where iter c
[]
= c
iter c
(x:xs) = iter (tick x c) xs
tick :: Int -> (Int, Int) -> (Int, Int)