函数式编程公理

Question

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

我要找 公理或 公式 递归、映射、归约、缺点、第一和休息等每种功能技术如何相互关联，哪些是可推导/可组合的，哪些是一切背后的最终公理。

比如我实现了map只能使用 recur 实现, first , rest和 cons函数，当然还有传递给 map 的映射函数本身.

之后我也意识到map也可以使用 reduce 来实现，再次减少可以使用 recur 实现, first和 rest .还有 filter可以用 reduce 实现.

我觉得我开始关注函数式编程，但仍然很难看出哪些是最最终的构建块，即哪些是组成任意函数的最少抽象或关键字集。对于 map 示例，第二种方法使用较少的抽象来实现相同的目标。那么，有哪些功能范式的终极公理可以帮助我了解全局？

Answer 1

从 lambda(在 clojure 中称为 fn)，您可以派生出其他任何东西。例如，让我们做派生 cons 的经典练习。 , first , 和 rest与 fn :

(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 的，作为解释抽象障碍值(value)的一部分:实现无关紧要，只要它满足您建立的契约即可。当然，如果您对一般的编程基础感兴趣，那么 SICP 是一本很好的读物。

从评论中似乎对这个答案有很多困惑；我的错没有向以前没有看过的人解释。

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

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

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

这是一个示例 repl session ，描述了此练习旨在演示的内容:

(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