Оригинал доступен на сайте cs.dartmouth.edu

Эти функции Haskell имплементируют операции со степенными рядами.

Ряды представлены в виде списков числовых коэффициентов и трактуются формально; конвергентность не является проблемой.

Поскольку списки не ограничены по размеру, ленивые вычисления обязательны.

Специальные правила для пустых списков сделают так, что операции будут выполняться также с исходными данными конечной длины (многочленами) и позволят заданным скалярным величинам быть конечными рядами.

Источник: М. Д. Макилрой, Музыка потоков данных (.ps.gz),

Документ по обработке данных 77 (2001) 189-195.

Определение функции

У переменной ряда имеется индекс s, а когда она находится в конце – то t.

На странице с пояснениями разъясняются некоторые детали формул, которые помечены как ссылки.

Задать ряду скаляр

series f = f : repeat 0

 fromInteger c = series(fromInteger c)

Отрицание

negate (f:ft) = -f : -ft

Сложение

(f:ft) + (g:gt) = f+g : ft+gt

Умножение

(f:ft) * gs@(g:gt) = f*g : ft*gs + series(f)*gt

Деление

(f:ft) / (g:gt) = qs where qs = f/g : series(1/g)*(ft-qs*gt)

Вычитание, целая степень

Для данных операций мы используем стандартные определения Haskell:

вычитание посредством сложения и отрицания,

обратное вычисление (recip) с помощью деления,

получение неотрицательной целой степени (^) с помощью умножения, и

общей целой степени (^^) с помощью (^) и обратного вычисления.

Сложная функция (#)

(f:ft) # gs@(0:gt) = f : gt*(ft#gs)

Реверсия (обратная функция)

revert (0:ft) = rs where rs = 0 : 1/(ft#rs)

Вычисление интеграла

int fs = 0 : zipWith (/) fs [1..]     — integral from 0 to x

Дифференцирование

diff (_:ft) = zipWith (*) ft [1..]   — type (Num a,Enum a)=>[a]->[a]

Примеры

Задание значений позволяет рассматривать кратко записанные многочлены в виде степенных рядов.

Таким образом, 1+x2 можно записать как 1+(0:1)^2 или как 1:0:1 – это указано ниже в развернутом виде, для определения ряда для tan x при помощи ряда для получения его обратной функции: arctan x = ∫dx/(1+x2).

   tans = revert(int(1/(1:0:1)))

Из обычных дифференциальных соотношений между синусом и косинусом вытекает код для вычисления их степенного ряда. Ленивое вычисление разрешает взаимную рекурсию.

sins = int coss

 coss = 1 — int sins

Если операции обобщены для того, чтобы многочлены оставались конечными, то коэффициенты степенных рядов сами могут становиться (конечными) степенными рядами. Тогда тождественное равенство

1/(1−(1+x)z) = Σ (1+x)nzn приводит к порождающему классу согласно треугольнику Паскаля:

pascal = 1/[1, −[1,1]]

Эта формула распространяется на список списков:

[[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1], …]::[[Rational]]

Полный пакет

Приведенный выше код плюс несколько строк объявления составляют рабочий минимальный пакет.

Для быстрого теста, попробуйте определить 10 tans. Это задействует каждую операцию, кроме diff.

(Простите, расширение файла пакета – .txt для того, чтобы удовлетворять требования некоторых браузеров.

А еще некоторые браузеры на экране отображают знак “минус” в этих программах как дефис)

Расширения для обработки многочленов формируют практичный пакет, вдвое больший по размеру, не такой красивый, но гораздо более быстрый и способный на подвиги как и pascal.

Чтобы увидеть грандиозное ускорение, попробуйте провести более значимый тест: к примеру, попробуйте определить 20 tans.

Почему конечное множество сложнее бесконечного? Потому что как бы то ни было, конец необходимо отыскать.

Завершающий штрих

Автор Даг Макилрой

[email protected]

Июль 2007

Авг 2007. Текст, но не код, слегка изменен.

Сентябрь 2007 г. Исправлено ​​опечатку в термине “sins”; ОК в полных пакетах.

Добавлены ​​ страница с пояснениями и треугольник Паскаля. Незначительные правки текста.