Эта версия функции хоть и наглядная, но не эффективная. Функция f вычисляется заново при каждом ре-
курсивном вызове. Было бы хорошо вычислять её только для новых значений. Для этого мы будем передавать
значения с предыдущего шага:
integrate :: Fractional a => (a -> a) -> a -> a -> [a]
integrate f a b = integ f a b (f a) (f b)
where integ f a b fa fb = (fa+fb)*(b-a)/2 :
zipWith (+) (integ f a m fa fm)
(integ f m b fm fb)
where m
= (a + b)/2
fm = f m
182 | Глава 11: Ленивые чудеса
В этой версии мы вычисляем значения в функции f лишь один раз для каждой точки. Запишем итоговое
решение:
int :: (Ord a, Fractional a) => a -> (a -> a) -> a -> a -> a
int eps f a b = converge eps $ integrate f a b
Мы опять воспользовались функцией converge, нам не нужно было её переписывать. Проверим решение.
Для проверки также воспользуемся экспонентой. В прошлой главе мы узнали, что
∫ x
ex = 1 +
etdt
0
Посмотрим, так ли это для нашего алгоритма:
*Numeric> let exp’ = int 1e-5 exp 0
*Numeric> let test x = abs $ exp x - 1 -
exp’ x
*Numeric> test 2
8.124102876649886e-6
*Numeric> test 5
4.576306736225888e-6
*Numeric> test 10
1.0683757864171639e-5
Алгоритм работает. В статье ещё рассмотрены методы повышения точности этих алгоритмов. Что инте-
ресно для улучшения точности не надо менять существующий код. Функция принимает последовательность
промежуточных решений и преобразует её.
11.2 Степенные ряды
Напишем модуль для вычисления степенных рядов. Этот пример взят из статьи Дугласа МакИлроя
(Douglas McIlroy) “Power Series, Power Serious”. Степенной ряд представляет собой функцию, которая опре-
деляется списком коэффициентов:
F ( x) = f 0 + f 1 x + f 2 x 2 + f 3 x 3 + f 4 x 4 + ...
Степенной ряд содержит бесконечное число слагаемых. Для вычисления нам потребуются функции сло-
жения и умножения. Ряд F ( x) можно записать и по-другому:
F ( x) = F 0( x)
= f 0 + xF 1( x)
= f 0 + x( f 1 + xF 2( x))
Это определение очень похоже на определение списка. Ряд есть коэффициент f 0 и другой ряд F 1( x)
умноженный на x. Поэтому для представления рядов мы выберем конструкцию похожую на список:
data Ps a = a :+: Ps a
deriving (Show, Eq)