Двойственные подходы в функциональном программировании

Question

Я хотел бы знать, какие проблемы реальной жизни могут быть решены с помощью "методов двойственности" в функциональном программировании.Точнее, я хотел бы знать, действительно ли кто-то использовал метод двойственности, подобный представленному ниже, или есть другие интересные примеры.Я был бы особенно заинтересован в существующих реализациях , возможно, в Haskell.

[Поскольку большинство людей, которые будут интересоваться этим вопросом, вероятно, знают Haskell, позвольте мне добавитьтег Haskell, даже если вопрос не зависит от языка]

Позвольте мне объяснить, что я имею в виду под двойственностью (отсутствием лучшего названия), на нескольких примерах.Первый - это действительные числа .Предположим, что существуют типы Integer и Rational, и определим действительное число как функцию (простите мой Haskell, я не хардкорный haskeller)

type Real = Integer -> Rational

, такой, что всякий раз, когда x :: Realобозначает действительное число x, x n дает рациональное число, которое находится в пределах 2^(-n) от x.

Теперь можно сделать

(+) :: Real -> Real -> Real
(+) x y n = (x $ n + 1) + (y $ n + 1)

или аналогично для других арифметических операций.Учитывая непрерывную вещественную функцию f, можно также вычислить f x, как только можно вычислить модуль непрерывности для f.

Это имеет то преимущество, что можно написать натуральноеищите код и в конце получите результат с желаемым уровнем точности автоматически.Однако больше нельзя сравнивать реальные числа на равенство.Единственное возможное сравнение между x и y - это x < y + eps.

Еще один пример дуальности - этот вопрос по вероятностным мерам , который вызвалНастоящий вопрос в моей голове.Давайте напишем

type Measure a = (a -> Double) -> Double

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

Это позволяет составлять строительные блоки из теории вероятностей и в принципе позволяет строить сложные процедуры Монте-Карло, и даже позволяет работать с явными плотностями вероятности (за счет численного интегрирования).Я был бы особенно заинтересован в любой попытке создать реальную библиотеку по этой теме.

Еще один пример, который я имею в виду, но еще не полностью формализовал, - это понятие векторных полей (из дифференциальной геометрии), который можно выразить как операторы дифференцирования .Для этого нужен подходящий тип «гладких вещественных функций», а затем векторное поле выглядит так:

type VectorField = SmoothFunction -> SmoothFunction

такой, что v (f * g) = f * (v g) + g * (v f).

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

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

type AnalyticFunction = Double -> Integer -> [Double]

и где f x n возвращаетn первые частичные суммы расширения Тейлора f вокруг x.Это позволяет нам легко писать все виды арифметики для аналитических функций, включая такие вещи, как f / g, где f и g оба могут исчезать в некоторой точке (вместе с некоторыми их производными), или даже f^(-1) (при условииf' не пропадает).В конце вычисляются только необходимые члены промежуточного ряда, чтобы получить значение данного выражения.

Answer 1

Общей особенностью вашего примера является представление некоторого (математического) объекта функциями .Это распространено в функциональных языках, но не так практично, как в математике, потому что функции в программах используются экстенсивно (вы не можете проверить их определения, только наблюдать их действия на аргументах), и только с вычислимыми операциями (вы можете наблюдать только конечное числоаргументы).

В математике вы не беспокоитесь о таких вещах, например, вы очень часто говорите «если f аналитична, то давайте (a_n) будем его последовательностью коэффициентов, и ...».На компьютерном языке, если вы начинаете с функции типа Double -> Integer -> [Double], будет трудно преобразовать ее в представление, в котором вы можете легко восстановить коэффициенты.В языках программирования функции на самом деле являются черными ящиками.

По этой причине программисты часто пытаются использовать явные представления данных вместо черных ящиков функции.Вы можете легко получить функцию из представления данных (это своего рода оценка или интерпретация), в то время как обратный путь может быть более сложным, менее эффективным и т. Д. См. «1011 *» Конала Эллиотта «Все есть функция» в Haskell?.

Однако функции все еще используются в тех случаях, когда нам действительно нужны объекты экстенсиональной структуры, которые можно наблюдать только вместо проверки.Для каждого возможного наблюдения объекта, который вы хотите определить, вы даете функцию, которая реализует это наблюдение.В вашем примере у вас есть только одна функция, потому что у вас есть только одно наблюдение.Это основная идея объектно-ориентированного программирования, определенная Уильямом Куком в его статье «Понимание абстракции данных», пересмотренной .

Я думаю, почему вы связываете это с термином «двойственность»(термин, который в интеллигенции Хаскелла скорее связан с теоретико-категориальными понятиями), заключается в том, что переход от объекта к какой-то конкретной форме его наблюдения иногда называют дуальностью в математике и приводит к добавлению функций повсюду.Например, есть классический пример двойственного векторного пространства и, в частности, двойная конструкция, которая в действительности представляет собой преобразование вектора в его наблюдения с помощью линейных функций: вы переключаетесь с V на (V -> K) -> K для K поле, лежащее в основе вашего векторного пространства.

(Можно ли подумать о продолжениях, читающих мой последний пример? Конечно, они связаны, поскольку это представление продолжений действительно является «наблюдением» конкретных контекстов оценки, представленныхих действие на значения.)

Ваше представление вероятностных мер фактически используется для определения монад вероятностных мер в функциональных языках.Существуют разные способы определения вероятности монады.См., Например, http://www.cs.tufts.edu/~nr/pubs/pmonad-abstract.html Нормана Рэмси и Ави Пфеффера.Однако в большинстве реальных реализаций вероятностного DSL используется более конкретное представление, такое как список пар [(prob,event)] (библиотека Haskell вероятность и библиотека OCaml HANSEI ).

Наконец, для примера представления действительного числа в виде функций см. Рассела О'Коннора "Монадическая функциональная реализация действительных чисел ".Существуют многочисленные представления «вычислимых» чисел, которые имеют разные достоинства, и большинство из них основаны на последовательностях и поэтому могут быть представлены как Integer -> ... функций.