math - 函数式编程中的对偶方法

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只要有人能计算出 modulus of continuity对于 f .

这样做的好处是可以编写看起来自然的代码，并最终自动获得所需精度级别的结果。但是，不再可能比较实数是否相等。 x 之间唯一可能的比较和 y是 x < y + eps .

对偶的另一个例子是 this question on probability measures ，这引发了我脑海中的当前问题。让我们写

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

并将度量定义为针对功能的集成程序。在链接的问题中，我展示了在这个框架中表达卷积或前推等概念是多么自然，这些概念在概率密度级别上定义起来要困难得多(在计算上，但在理论上)。

它允许人们从概率论中组成构建 block ，原则上允许人们构建复杂的蒙特卡罗程序，甚至允许人们使用明确的概率密度(以数值积分为代价)。我会对在真实世界图书馆中关于这个主题的任何尝试特别感兴趣。

另一个我想到但还没有完全正式化的例子是 的概念。向量场 (来自微分几何)，可以表示为微分算子。为此，需要一种合适类型的“平滑实值函数”，然后向量场是这样的:

type VectorField = SmoothFunction -> SmoothFunction

这样 v (f * g) = f * (v g) + g * (v f) .

当然，用say 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] 类型的函数开始，将其转换为可以轻松恢复系数的表示会很痛苦。在编程语言中，函数真的是黑盒子。

出于这个原因，程序员经常尝试使用显式数据表示而不是函数黑盒。您可以轻松地从数据表示中获得函数(它是一种评估或解释)，而反过来可能会更困难、效率更低等。请参阅 Conal Elliott 的 “Everything is a function” in Haskell? .

然而，在我们真正想要扩展对象的情况下仍然使用函数，这些对象只能被观察而不是被检查。对于您要定义的对象上的每个可能的观察，您给出一个实现该观察的函数。在您的示例中，您只有一个函数，因为您只有一个观察值。这是 William Cook 在他的 On Understanding Data Abstraction, Revisited 中定义的面向对象编程的核心思想。纸。

我认为您将其与术语“二元性”(即在 Haskell 知识分子中，与范畴论概念相关的术语)联系起来的原因是，从对象到对它的某种特定观察形式的转变有时是在数学中称为对偶，并且具有在任何地方添加函数的效果。例如，有一个向量空间对偶的经典例子，特别是对偶构造，它实际上是从向量到线性函数观察的转换:你从 V 切换至(V -> K) -> K , 对于 K向量空间下的字段。

(阅读我的最后一个例子会想到延续吗？当然这些是相关的，因为延续的这种表示实际上是对具体评估上下文的“观察”，由它们对值的作用来表示。)

您对概率度量的表示实际上用于在功能语言中定义概率度量单子(monad)。有不同的方法来定义概率单子(monad)。参见示例 http://www.cs.tufts.edu/~nr/pubs/pmonad-abstract.html诺曼拉姆齐和阿维菲弗。然而，大多数现实世界的概率 DSL 实现使用更具体的表示，例如 [(prob,event)]对列表(Haskell probability 库和 OCaml HANSEI)。

最后，有关将实数表示为函数的示例，请参阅 Russel O'Connor 的 A Monadic, Functional Implementation of Real Numbers。 . “可计算”数的许多表示存在并且具有不同的优点，其中大多数是基于序列的，因此可以表示为Integer -> ...。功能。