函数式编程中的对偶方法
我想知道函数式编程中的“对偶方法”可以解决什么样的现实生活问题。更准确地说，我想知道是否有人确实使用了像我下面介绍的那样的对偶方法，或者是否还有其他有趣的例子。我对现有实现特别感兴趣，可能是在 Haskell 中。
[由于大多数对此问题感兴趣的人可能都知道 Haskell，所以请让我添加 Haskell 标签，即使问题与语言无关]
让我解释一下我所说的对偶性（由于缺乏更好的名称）通过几个例子。第一个是实数。假设存在 Integer 和 Rational 类型，并将实数定义为函数（请原谅我的 Haskell，我不是铁杆 Haskell），
type Real = Integer -> Rational
这样每当 x :: Real 表示实数 x，x n 生成一个在 x 的 2^(-n) 范围内的有理数。
现在可以
(+) :: Real -> Real -> Real
(+) x y n = (x $ n + 1) + (y $ n + 1)
对其他算术运算进行类似的操作。给定一个连续实函数 f，只要可以计算 f 的连续性模量。
这样做的优点是，人们可以编写看起来自然的代码，并最终自动获得所需精度级别的结果。然而，不再可能比较实数是否相等。 x 和 y 之间唯一可能的比较是 x x x x 。 y + 每股收益。
对偶性的另一个例子是这个关于概率度量的问题，它引发了我脑海中当前的问题。让我们将度量编写
type Measure a = (a -> Double) -> Double
并定义为针对功能的集成过程。在链接的问题中，我展示了在这个框架中表达诸如卷积或前推之类的概念是多么自然，这些概念在概率密度水平上定义起来要困难得多（在计算上，而且在理论上）。
它允许人们从概率论中构建构建块，原则上允许人们构建复杂的蒙特卡罗程序，甚至允许人们使用明确的概率密度（以数值积分为代价）。我对现实世界图书馆在这个主题上的任何尝试特别感兴趣。
我想到但尚未完全形式化的另一个例子是矢量场的概念（来自微分几何），可以将其表达为微分算子。为此，需要一种合适类型的“平滑实值函数”，然后向量场如下所示：
type VectorField = SmoothFunction -> SmoothFunction
使得 v (f * g) = f * (vg) + g * (vf)代码>.
当然，用 Haskell 描述一堆常规函数应该并不容易。但是通过这样做，我们可以以完全坐标独立的方式表达微分几何中的所有内容，并在最后插入坐标。
还有其他例子，例如。 泰勒级数已在 Sigfpe 的博客中讨论过（不过我找不到这篇特定的文章），其中分析函数为以下类型：
type AnalyticFunction = Double -> Integer -> [Double]
并且其中 fx n 返回 < code>n 围绕 x 的 f 泰勒展开式的第一个部分和。这使我们能够无缝地在分析函数上编写各种算术，包括像 f / g 这样的东西，其中 f 和 g 都可以在点（以及它们的一些导数），甚至是 f^(-1) （前提是 f' 不会消失）。最后，仅计算中间级数的必要项以产生给定表达式的值。
I'd like to know what kind of real life problems can be tackled by "duality methods" in functional programming. More precisely, I'd like to know whether someone did actually use a duality method like the ones I present below, or whether there are other interesting examples. I'd be particularly interested in existing implementations, probably in Haskell.
[Since the majority of people which will be interested in this question likely know Haskell, let me please add the Haskell tag, even if the question is quite language independent]
Let me explain what I mean by duality (by lack of a better name) through a few examples. The first one is the real numbers. Assume the existence of a Integer and a Rational type, and define a real number as a function (pardon my Haskell, I'm no hardcore haskeller)
type Real = Integer -> Rational
such that whenever x :: Real denotes the real number x, x n yields a rational number which is within 2^(-n) of x.
Now one can do
(+) :: Real -> Real -> Real
(+) x y n = (x $ n + 1) + (y $ n + 1)
or likewise for other arithmetic operations. Given a continuous real function f, one can also compute f x as soon as one can compute a modulus of continuity for f.
This has the advantage that one can write natural looking code, and at the end, get a result at the desired level of precision automatically. However, it is no longer possible to compare real numbers for equality. The only kind of comparison possible between x and y is x < y + eps.
Another example of duality is this question on probability measures, which triggered the present question in my head. Let us write
type Measure a = (a -> Double) -> Double
and define measures as integration procedures against functions. In the linked question, I show how natural it is in this framework to express concepts like convolution or pushforward which are much more difficult (computationally, but also theoretically) to define at the level of probability densities.
It allows one to compose building blocks from probability theory, and in principle allows one to build complex Monte Carlo procedures, and even allows one to work with explicit probability densities (at the expense of numerical integration). I'd be especially interested in any attempt at a real world library on this topic.
Another example that I have in mind, but did not quite formalize yet is the notion of vector fields (from differential geometry), that one can express as differentiation operators. For this, one needs a suitable type of "smooth real valued functions", and then a vector field is like this:
type VectorField = SmoothFunction -> SmoothFunction
such that v (f * g) = f * (v g) + g * (v f).
Of course, describing a sheaf of regular functions in say Haskell should not be easy. But by doing that, we could express all the stuff from differential geometry in a totally coordinate independant way, and plug coordinates at the very end.
There are other examples, eg. Taylor series have been discussed in Sigfpe's blog (I can't find this particular post though), where an analytic function is the following type:
type AnalyticFunction = Double -> Integer -> [Double]
and where f x n returns the n first partial sums of the Taylor expansion of f around x. This allows us to seamlessly write all kind of arithmetic on analytic functions, including stuff like f / g where f and g both can vanish at a point (along with some of their derivatives), or even f^(-1) (provided f' does not vanish). At the end, only the necessary terms of the intermediate series are computed to yield the value of a given expression.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您的示例的共同特征是通过函数表示某些（数学）对象。这在函数式语言中很常见，但不如在数学中那么实用，因为程序中的函数是可扩展使用的（您无法检查它们的定义，只能观察它们对参数的操作），并且只能用于可计算操作（您只能观察有限数量的论据）。
在数学中，你不会为这些东西烦恼，例如你经常说“如果 f 是解析的，那么让 (a_n) 成为它的系数序列，并且......”。在计算机语言中，如果您从
Double -> 类型的函数开始整数-> [Double]，将其转换为可以轻松恢复系数的表示形式会很痛苦。在编程语言中，函数实际上是黑盒子。因此，程序员经常尝试使用显式数据表示而不是函数黑盒。您可以轻松地从数据表示中获取函数（它是一种评估或解释），而相反的方式可能会更困难、效率更低等。请参阅 Conal Elliott 的 Haskell 中的“一切都是函数”？。
然而，在我们真正想要扩展对象的情况下仍然使用函数，这些对象只能被观察而不是检查。对于要定义的对象的每个可能的观察，您给出一个实现该观察的函数。在您的示例中，您只有一个函数，因为您只有一个观察结果。这是 William Cook 在他的《重新审视数据抽象》中定义的面向对象编程的核心思想< /a> 纸。
我认为你将其与“二元性”一词（哈斯克尔知识分子中的一个术语，与范畴论概念相当相关）联系起来的原因是，从一个对象到对其的某种特定形式的观察的转变有时是数学上称为对偶性，具有到处添加函数的效果。例如，有一个向量空间对偶的经典示例，特别是对偶构造，它实际上是通过线性函数从向量到其观测值的转换：您从
V切换到 <代码>(V -> K) -> K，K表示向量空间下的场。（有人会想到继续阅读我的上一个例子吗？当然，这些是相关的，因为这种连续的表示实际上是对具体评估上下文的“观察”，由它们对值的作用来表示。）
您对概率度量的表示实际上用于用函数语言定义概率测度单子。定义概率单子有不同的方法。例如，请参阅 http://www.cs.tufts.edu/~ nr/pubs/pmonad-abstract.html 作者：Norman Ramsey 和 Avi Pfeffer。然而，概率 DSL 的大多数现实世界实现都使用更具体的表示，例如
[(prob,event)]对列表（Haskell 概率 库和 OCaml HANSEI）。最后，有关将实数表示为函数的示例，请参阅 Russel O'Connor 的一元函数实现实数。 “可计算”数字的多种表示形式存在并且具有不同的优点，并且它们中的大多数基于序列并且因此可以表示为整数->整数。 ... 功能。
The common feature of your example is the representation of some (mathematical) object by functions. This is common in functional languages, but not as practical as in mathematics because functions in programs are used extensionally (you cannot inspect their definitions, only observe their actions on arguments), and only with computable operations (you can only observe a finite number of arguments).
In mathematics, you don't bother with such stuff, for example you very often say "if f is analytic, then let's (a_n) be its sequence of coefficients, and...". In a computer language, if you start with a function of type
Double -> Integer -> [Double], it will be painful to convert it to a representation where you can easily recover the coefficients. In programming languages, function really are black boxes.For this reason, programmers often try to use explicit data representations instead of function black boxes. You can easily obtain a function from a data representation (its a kind of evaluation or interpretation), while the other way around can be more difficult, less efficient, etc. See Conal Elliott's “Everything is a function” in Haskell?.
Functions are however still used in cases where we really want extensional objects, that can only be observed instead of inspected. For each possible observation on the object you want to define, you give a function that realize this observation. In your example, you only have one function because you only have one observation. This is the core idea of Object Oriented Programming as defined by William Cook in his On Understanding Data Abstraction, Revisited paper.
I think the reason why you relate this to the term "duality" (a term that is, in the Haskell intelligentsia, rather related to category-theoretic concepts) is that the shift from an object to some particular form of observation of it is sometimes called duality in maths, and has the effect of adding functions everywhere. For example, there is the classical example of the dual of a vector space, and in particular the bidual construction which is really a conversion from a vector to its observations by linear functions : you switch from
Vto(V -> K) -> K, forKthe field underlying your vector space.(Would one think of continuations reading my last example ? Of course those are related, as this representation of continuations is really an "observation" of concrete evaluation contexts, represented by their action on values.)
Your representation of probability measures is actually used to define probability measure monads in functional languages. There are different ways to define probability monads. See for example http://www.cs.tufts.edu/~nr/pubs/pmonad-abstract.html by Norman Ramsey and Avi Pfeffer. Most real-world implementation of probability DSL however use a more concrete representation such as a
[(prob,event)]list of pair (Haskell probability library and OCaml HANSEI).Finally, for an example of representation of real number as functions, see Russel O'Connor's A Monadic, Functional Implementation of Real Numbers. Numerous representation of "computable" numbers exist and have different merits, and most of them are based on sequences and may therefore be represented as
Integer -> ...functions.