函数式编程公理

Question

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

我正在寻找公理或公式 递归、映射、缩减、缺点等每个函数技术如何, first ans rest 是相互关联的，是derivable/composable从中而来，也是万物背后的终极公理。

例如，我意识到 map 只能使用 recur、first、rest 和 cons 函数来实现，当然还有映射函数本身传递给 map.

之后，我也意识到map也可以用reduce来实现，reduce也可以用recur、first和[=13=来实现]. filter 也可以用 reduce.

来实现

我觉得我开始全神贯注于函数式编程，但仍然很难看出哪些是最终极的构建块，即哪些是抽象的最小集合 或 keywords 组成任意函数。以地图为例，第二种方法使用较少的抽象来达到相同的目标。那么，有哪些函数范式的终极公理可以帮助我看清全局？

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)))

你可以构建更复杂的东西，比如 clojure 的实际 first/rest 只用 lambda，但你必须首先发明一个完整的类型系统，所以它涉及更多。

这是一个示例 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

Answer 2

首先要了解列表在大多数函数式语言中的表现 constructed，也就是说，为什么将列表视为 first 和 rest 如此有意义。这个递归定义是理解你改变它们的递归机制的关键。

我第一次摸索 map/filter/fold 等的方式实际上是通过 haskell，这有表达事物类型的好处。这对初学者来说很有意义，至少对我来说是这样。

例如，map 的签名 (a -> b) -> [a] -> [b] 读作：如果您有一个接受类型 a 并将其转换为类型 b 的函数，并且你给出一个 a 类型的列表，然后 map 会简单地 return 你一个 b.

类型的列表

你真正应该花时间理解的是 fold（left 和 right），其中 reduce 是 in 的特例一个打字的世界。准备好后，我建议您复习一下 A tutorial on the universality and 折叠的表现力

我强烈建议您尝试并实现您提到的所有内容，您对这些基本构建块及其依赖关系的理解将会大大提高。根据 recur 实施 reduce（和两种折叠），根据 recur 和 reduce 实施 map filter take 等等等

Answer 3

例如，我认为您找不到一组类似于概率论的简单公理。对于概率，只有3个基本公理：

P[A] >= 0 对于每个事件 A
P["any event"] = 1
P[ A 或 B ] = P[A] + P[B] 如果 A & B 互斥

令人惊讶的是，概率统计中的一切都可以从这三个基本假设中推导出来。

"函数式编程" 的定义不是很明确。事实上，几乎每本关于该主题的书都以这样的观察开始：如果您要求 100 "experts" 来定义 函数式编程 ，您将收到 100 个相互不兼容的答案。这句话只是部分开玩笑。

关于函数式编程，你唯一能说的就是它比传统语言或 "non-functional" 语言更强调函数。这实际上更像是对函数式语言或函数式编程风格的 "goal" 而不是 yes/no 观察。

函数式编程的目标一如既往：通过提高简单性和可靠性来节省成本。当然，自计算诞生以来，每一种语言和技术都有同样的游戏计划。 FP 旨在通过以下方式实现它：

减少使用可变变量
增加使用函数代替手动循环

请注意，它说的是 "reduce" & "increase"，而不是 "only" & "never"。决定这意味着什么是判断电话，答案会根据手头的问题和你问的人而改变。

请记住，问题和人都会随着时间而改变。 "best" 今天在成本、复杂性、效率、可维护性等之间进行权衡的答案可能不会是 "best" 一个月或一年后的答案，因为问题、人员、工具、硬件、价格等随时间变化。

记住科学校长。它迫使你尝试事物（实验），而不仅仅是思考它们（理论）。所以你必须实际做一些事情并观察结果。

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

函数式编程公理

Functional programming axioms

reduce

functional-programming

function

clojure

higher-order-functions