函数式编程是什么

函数式编程更加强调程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。

例子一 累加运算

// sum

List<</span>Integer> nums = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 10);



public static Integer sum(List<</span>Integer> nums) {

int result = 0;

for (Integer num : nums) {

result += num;

}



return result;

}



sum(nums); // -> 46

同样的代码用 Java8 Stream 实现

Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 10).stream().reduce(0, Integer::sum);

同样的代码用 Clojure 实现

(apply + [0 1 2 3 4 5 6 7 8 10]) ; -> 46

#_(reduce + [0 1 2 3 4 5 6 7 8 10])

例子二 fabonacci数列

// java

public static int fibonacci(int number) {

if (number == 1) {

return 1;

}

if(number == 2) {

return 2;

}



int a = 1;

int b = 2;

for(int cnt = 3; cnt <= number; cnt++) {

int c = a + b;

a = b;

b = c;

}

return b;

}

// java8

Stream.iterate(new int[]{1, 1}, s -> new int[]{s[1], s[0] + s[1]})

.limit(10)

.map(n -> n[1])

.collect(toList())

// -> [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

// clojure

(->> (iterate (fn [[a b]] [b (+ a b)]) [1 1])

(map second)

(take 10))

; -> (1 2 3 5 8 13 21 34 55 89)

比起命令式的语言，函数式语言更加关注执行的结果，而非执行的过程。

函数式编程的历史

从Hilbert 23个数学难题谈起

1900年，Hilbert 提出了数学界悬而未决的10大问题，后续陆续添加成了23个问题，被称为著名的 Hilbert 23 Problem。针对其中第2个决定数学基础的问题——算术公理之相容性，年轻的哥德尔提出了哥德尔不完备定理，解决了这个问题形式化之后的前两点，即数学是完备的吗？数学是相容的吗？哥德尔用两条定理给出了否定的回答。

所谓不完备，即系统中存在一个为真，但是无法在系统中推导出来的命题。比如：U说：“U在PM中不可证”。虽然和说谎者很类似，但其实有明显的差异。我们可以假设U为可证，那么可以推出PM是矛盾（不相容）的；但是假设U不可证，却推导不出PM是矛盾的。U的含义是在PM中不可证，而事实上，它被证明不可证，所以U是PM中不可证的真命题。

基于第一条不完备定理，又可以推导出第二条定理。如果一个（强度足以证明基本算术公理的）公理系统可以用来证明它自身的相容性，那么它是不相容的。

而最后一个问题，数学是确定的吗？也就是说，存在一个算法判定一个给定的命题是否是不确定的吗（Entscheidungsproblem 判定性问题）？这个问题引起了阿隆佐·邱奇和年轻的阿兰·图灵的兴趣。

阿隆佐·邱奇的 lambda calculus 和图灵的图灵机构造出了可计算数，图灵的那篇论文 ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM 的意义不在于证明可计算数是否可数，而在于证明可判定性是否成立。在1936年他们对判定性问题分别独立给出了否定的答案。也就是现在被我们熟知的图灵停机问题：不存在这样一个程序（算法），它能够计算任何程序（算法）在给定输入上是否会结束（停机）。图灵借此发明了通用图灵机的概念，为后来的冯·诺依曼体系的计算机体系提供了理论基础。