函数式编程公理

Question

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

我正在寻找公理或公式,每个函数技术如递归,映射,减少,缺点,第一和休息是如何相互关联的,它们是可衍生的/可组合的,并且它是一切背后的终极公理.

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

在那之后,我也意识到map可以利用也实现reduce,并再次减少可利用来实现recur,first和rest.也filter可以实现reduce.

我觉得我开始围绕函数式编程,但仍然很难看出哪些是最终的构建块,即构成任意函数的最小抽象或关键字集合.使用map示例,第二种方法使用少一个抽象来定位同一目标.那么,功能范式的一些终极公理能够帮我看清大局吗？

Answer 1

从lambda(fn在clojure中调用),你可以得到任何其他东西.例如,让我们做的经典运动获得的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终极论文.
• 使用Nothing编程,这是一种更新的方法.这使用Ruby语法,但它并不重要,因为它使用的唯一语言功能是lambda.
• SICP还有一个关于从lambda中获取car/cdr/cons的部分,作为解释抽象障碍价值的一部分:只要满足你已经建立的合同,实现并不重要.当然,如果您对编程的基础感兴趣,那么SICP通常是一个很好的阅读.

从评论中可以看出,对这个答案存在很多困惑; 我没有为以前没见过的人解释过它.

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

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

你可以用lambda构建更复杂的东西,比如clojure的实际第一个/休息,但是你必须首先发明一个完整的类型系统,所以它涉及更多.

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