Умножение
Умножим два ряда:
F ? G = ( f + xF 1) ? ( g + xG 1) = f g + x( f G 1 + F 1 ? G)
Переведём:
(.*) :: Num a => a -> Ps a -> Ps a
k .* (f :+: fs) = (k * f) :+: (k .* fs)
(f :+: fs) * (g :+: gs) = (f * g) :+: (f .* gs + fs * (g :+: gs))
Дополнительная операция (.*) выполняет умножение всех коэффициентов ряда на число.
Класс Num
Соберём определения для методов класса Num вместе:
instance Num a => Num (Ps a) where
(f :+: fs) + (g :+: gs) = (f + g) :+: (fs + gs)
(f :+: fs) * (g :+: gs) = (f * g) :+: (f .* gs + fs * (g :+: gs))
negate (f :+: fs) = negate f :+: negate fs
fromInteger n = p0 (fromInteger n)
(.*) :: Num a => a -> Ps a -> Ps a
k .* (f :+: fs) = (k * f) :+: (k .* fs)
Методы abs и signum не определены для рядов. Обратите внимание на то, как рекурсивное определение
рядов приводит к рекурсивным определениям функций для рядов. Этот приём очень характерен для Haskell.
Поскольку наш ряд это число и ещё один ряд за счёт рекурсии мы можем воспользоваться операцией, которую
мы определяем, на “хвостовом” ряде.
Деление
Результат деления Q удовлетворяет соотношению:
F = Q ? G
Переписав F , G и Q в нашем представлении, получим
f + xF 1 = ( q + xQ 1) ? G = qG + xQ 1 ? G = q( g + xG 1) + xQ 1 ? G
= qg + x( qG 1 + Q 1 ? G)
Следовательно
q
= f / g
Q 1 = ( F 1 ? qG 1)/ G
Если g = 0 деление имеет смысл только в том случае, если и f = 0. Переведём на Haskell:
184 | Глава 11: Ленивые чудеса
class Fractional a => Fractional (Ps a) where
(0 :+: fs) / (0 :+: gs) = fs / gs
(f :+: fs) / (g :+: gs) = q :+: ((fs — q .* gs)/(g :+: gs))
where q = f/g
fromRational x = p0 (fromRational x)
Производная и интеграл
Производная одного члена ряда вычисляется так:
d xn = nxn? 1
dx
Из этого выражения по свойствам производной
d
d
d
( f ( x) + g( x)) =
f ( x) +
g( x)
dx
dx
dx
d ( k ? f( x)) = k ? d f( x)
dx
dx
мы можем получить формулу для всего ряда:
d F( x) = f 1 + 2 f 2 x + 3 f 3 x 2 + 4 f 4 x 3 + …
dx
Для реализации нам понадобится вспомогательная функция, которая будет обновлять значение допол-
нительного множителя n в выражении nxn? 1:
diff :: Num a => Ps a -> Ps a
diff (f :+: fs) = diff’ 1 fs
where diff’ n (g :+: gs) = (n * g) :+: (diff’ (n+1) gs)
Также мы можем вычислить и интеграл степенного ряда:
int :: Fractional a => Ps a -> Ps a
int (f :+: fs) = 0 :+: (int’ 1 fs)
where int’ n (g :+: gs) = (g / n) :+: (int’ (n+1) gs)
Элементарные функции
Мы можем выразить элементарные функции через операции взятия производной и интегрирования. К
примеру уравнение для ex выглядит так:
dy = y
dx
Проинтегрируем с начальным условием y(0) = 1:
? x
y( x) = 1 +
y( t) dt
0
Теперь переведём на Haskell:
expx = 1 + int expx
Кажется невероятным, но это и есть определение экспоненты. Так же мы можем определить и функции
для синуса и косинуса:
d sin x = cos x,
sin(0) = 0 ,
dx
d cos x = ? sin x, cos(0) = 1
dx
Что приводит нас к:
sinx = int cosx
cosx = 1 — int sinx
И это работает! Вычисление этих функций возможно за счёт того, что вне зависимости от аргумента
функция int вернёт ряд, у которого первый коэффициент равен нулю. Это значение подхватывается и ис-
пользуется на следующем шаге рекурсивных вычислений.
Через синус и косинус мы можем определить тангенс:
tanx = sinx / cosx
Степенные ряды | 185
11.3 Водосборы
В этом примере мы рассмотрим одну интересную технику рекурсивных вычислений, которая называется
мемоизацией (memoization). Она заключается в том, что мы запоминаем все значения, с которыми вызывалась
функция и, если с данным значением функция уже вычислялась, просто используем значение из памяти, а
если значение ещё не вычислялось, вычисляем его и сохраняем.
В ленивых языках программирования для мемоизации функций часто используется такой приём. Мы со-
храняем все значения функции в некотором контейнере, а затем обращаемся к элементам. При этом значения
сохраняются в контейнере и не перевычисляются. Это происходит за счёт ленивых вычислений. Что интерес-
но вычисляются не все значения, а лишь те, которые нам действительно нужны, те которые мы извлекаем из
контейнера хотя бы один раз.
Посмотрим на такой классический пример. Вычисление чисел Фибоначчи. Каждое последующее число
ряда Фибоначчи равно сумме двух предыдущих. Наивное определение выглядит так:
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n—1) + fib (n—2)
В этом определении число вычислений растёт экспоненциально. Для того чтобы вычислить fib n нам
нужно вычислить fib (n—1) и fib (n—2), для того чтобы вычислить каждое из них нам нужно вычислить
ещё два числа, и так вычисления удваиваются на каждом шаге. Если мы вызовем в интерпретаторе fib 40,
то вычислитель зависнет. Что интересно в этой функции вычисления пересекаются, они могут быть пере-
использованы. Например для вычисления fib (n—1) и fib (n—2) нужно вычислить fib (n—2) (снова), fib
(n—3), fib (n—3) (снова) и fib (n—4).
Если мы сохраним все значения функции в списке, каждый вызов функции будет вычислен лишь один
раз:
fib’ :: Int -> Int
fib’ n = fibs !! n
where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Попробуем вычислить для 40:
*Fib> fib’ 40
102334155
*Fib> fib’ 4040
700852629
Вычисления происходят мгновенно. Если задача состоит из множества подзадач, которые самоподобны