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

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

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

Позвольте мне объяснить, что я подразумеваю под двойственностью (из-за отсутствия лучшего имени) через несколько примеров. Первый - действительные числа. Предположим существование типа Integer и a Rational и определим действительное число как функцию (pardon my 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

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

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

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

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' не обращается в нуль). В конце вычисляются только необходимые члены промежуточной серии, чтобы получить значение данного выражения.

Ответ 1

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

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

По этой причине программисты часто пытаются использовать явные представления данных вместо функций черных ящиков. Вы можете легко получить функцию из представления данных (своего рода оценку или интерпретацию), в то время как наоборот может быть более трудным, менее эффективным и т.д. См. Conal Elliott "Все функции" в Haskell?.

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

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

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

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

Наконец, пример представления действительного числа как функции, см. Russel O'Connor Монадическая, функциональная реализация реальных чисел. Многочисленное представление "вычислимых" чисел существует и имеет разные достоинства, и большинство из них основаны на последовательностях и поэтому могут быть представлены как функции Integer -> ....