函数式编程公理

Question

我正在学习使用Clojure进行函数式编程，并希望加深对函数式范式的理论理解（不仅仅是Clojure语法）。

我正在寻找有关每种函数式技术（例如递归、map、reduce、cons、first和rest）之间的关系的公理或公式，可以从哪些技术中派生/组合，以及哪些是背后的终极公理。

例如，我意识到map只能使用recur、first、rest和cons函数以及传递给map的映射函数来实现。

之后，我又意识到map也可以使用reduce实现，而reduce可以再次使用recur、first和rest实现。同时filter也可以使用reduce实现。

我觉得我开始理解函数式编程了，但是仍然很难看到哪些是最终建筑块，即用于组成任意函数的最小集合的抽象或关键字是什么。在map示例中，第二种方法使用一个较少的抽象来达到相同的目标。那么，函数式范式的一些终极公理可以帮助我看清大局吗？

- Tuomas Toivonen

---

在这种情况下，我建议您查看这本书：https://mitpress.mit.edu/books/little-schemer。它是一个惊人的FP入门指南，向您展示如何仅使用基本元素制作事物。此外，经典的[SICP](https://mitpress.mit.edu/sicp/full-text/book/book.html)也可以帮助很多。它们都使用lisp（确切地说是scheme），因此很容易将您的理解转移到clojure上。 - leetwinski

函数式编程在很大程度上根植于Lambda演算，其核心公理正如amalloy所述。 - Frank C.

不要忘记map也可以用for替代。 - Alan Thompson

Answer 1

从lambda（在Clojure中称为 fn ）中，您可以推导出任何其他内容。例如，让我们使用 fn 来完成经典的派生 cons ， first 和 rest 的练习：

(defn cons [x y]
  (fn [f]
    (f x y)))

(defn first [coll]
  (coll (fn [x y] x)))

(defn rest [coll]
  (coll (fn [x y] y)))

如果您想要一个函数式编程的公理集，那么只有一个：lambda是终极公理。关于如何推导其他特性的详细信息，请参阅以下文章：

- 经典的Lambda the Ultimate论文。 - Programming with Nothing，一种较新的方法。它使用Ruby语法，但这并不重要，因为它只使用了lambda这一语言特性。 - SICP也有一个关于如何从lambda中推导car/cdr/cons的部分，作为解释抽象屏障价值的一部分：实现并不重要，只要它满足您建立的合同即可。当然，如果您对编程基础感兴趣，SICP是一个很好的阅读材料。

---

似乎从评论中可以看出对这个答案有很多困惑；这是我的错，没有为那些之前没有看过它的人解释清楚。

这个想法并不是重新实现所有clojure内置的first/rest功能，这些都是高级多态的东西，适用于各种序列。相反，我们实现了三个cons/first/rest函数，它们一起工作，通过满足合同来允许您构建集合。

(= x (first (cons x y)))
(= y (rest (cons x y)))

你可以使用 lambda 构建像 Clojure 的 first/rest 这样更复杂的东西，但是你必须首先发明一个完整的类型系统，因此这需要更多的工作量。

下面是一个示例 repl 会话，描述了这个练习的目的。

(defn cons [x y]
  (fn [f]
    (f x y)))

(defn first [coll]
  (coll (fn [x y] x)))

(defn rest [coll]
  (coll (fn [x y] y)))
user> (def integers (cons 0 (cons 1 (cons 2 (cons 3 nil)))))
#'user/integers
user> integers
#object[user$cons$fn__2108 0x3fb178bd "user$cons$fn__2108@3fb178bd"]
user> (first integers)
0
user> (first (rest (rest integers)))
2

- amalloy

---

这看起来很有前途，但即使我已经阅读了Clojure文档，我仍然不理解它。这些书中是否解释了这个“经典例子”？集合如何被用作函数？我在Clojure REPL中尝试了一下，但是出现了错误IllegalArgumentException Key must be integer。 - Tuomas Toivonen

我也对这里发生的事情感到困惑。您正在使用函数对集合进行索引。 - Carcigenicate

我的编辑有改善吗？first和rest并没有错误，而是明显使用方式不清楚。 - amalloy

新的示例有助于澄清coll必须使用您的cons函数构建；coll并不意味着通用的Clojure集合。 - Alan Thompson

@amalloy，太优雅了！ - leetwinski

Answer 2

首先理解在大多数函数式语言中列表是如何构建的，也就是说，为什么把列表看作first和rest是非常有意义的。这种递归定义是理解更改它们的递归机制的关键。

我最初理解map/filter/fold等函数是通过Haskell，它能够表达事物的类型。对于初学者来说，这非常有意义，至少对我来说是这样。

例如，map的签名为(a -> b) -> [a] -> [b]，表示：如果你有一个接受类型a并将其转换为类型b的函数，并给出一个类型为a的列表，则map将简单地返回一个类型为b的列表。

你真正需要花时间理解的是fold（包括left和right），在类型世界中reduce是其特例。当你感觉准备好了，我建议看看那本经典的《fold的普适性和表现力》教程。

我强烈鼓励你尝试实现你提到的一切东西，这些基本构件及其依赖的理解将会大大提高。用recur来实现reduce（以及两种fold），用recur和reduce等方法来实现map、filter、take等。

- Shlomi

---

这是一些不错的练习，但在Clojure中，foldr比在Haskell中要不那么有用，因为我们缺乏持久性的惰性求值。尝试自己实现它，然后在大型集合上实际使用它。or :: [Bool] -> Bool; or = foldr (||) False 由于短路计算，对于大型集合非常有效，但在Clojure中的版本则不好。 - amalloy

完全同意你的看法，@amalloy。我认为对于刚开始学习的人来说，了解fold是什么以及它们之间的区别是一个很好的练习。 - Shlomi

Answer 3

我认为你不可能找到一个简单的公理集，类似于概率论。例如，对于概率，只有三个基本公理：

• 对于每个事件A，P[A]≥0
• P["任何事件"]=1
• 如果A&B互斥，则P[ A 或 B ]= P[A] + P[B]

令人惊讶的是，概率和统计学中的所有内容都可以从这三个基本假设中推导出来。

“函数式编程”并没有被很好地定义。事实上，几乎每本关于该主题的书籍都以这样的观察开始：如果你问100位“专家”定义“函数式编程”，你会得到100个相互矛盾的答案。这种说法只是部分开玩笑。

你真正能说的关于函数式编程的唯一事情是它更强调函数，而不是传统或“非函数式”的语言。这实际上更像是函数式语言或函数式编程风格的“目标”，而不是肯定或否定的观察。

函数式编程的目标与以往一样：通过更大的简单性和可靠性实现成本节约。当然，自计算机诞生以来，每种语言和技术都有这个相同的计划。FP主要通过以下方式实现：

• 减少使用可变变量
• 增加使用函数而非手动循环

请注意，它说的是“减少”和“增加”，而不是“只有”和“永远不”。决定这意味着什么是一个判断性的问题，答案会因为不同的问题和询问者而改变。

请记住，问题和人都会随着时间而变化。今天在成本、复杂性、效率、可维护性等方面最好的权衡答案，可能在一个月或一年后就不是最好的答案了，因为问题、人、工具、硬件、价格等都会随着时间的推移而变化。

记住科学原则。它强制你尝试事情（实验），而不仅仅是思考它们（理论）。所以你必须实际做些事情并观察结果。

在软件中，这意味着用两种（或更多）方法解决一个问题，并比较每种方法的优缺点。

- Alan Thompson