函数式思维和函数式编程
问题导读
1.本文是如何理解函数式编程的？
2.如何用函数式的方式思考、函数式的方式编程实现？
static/image/hrline/4.gif
作为一个对Haskell语言彻头彻尾的新手，当第一次看到一个用这种语言编写的快速排序算法的优雅例子时，我立即对这种语言发生了浓厚的兴趣。下面就是这个例子：
quicksort :: Ord a => ->
quicksort [] = []
quicksort (p:xs) =
(quicksort lesser) ++ ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
我很困惑。如此的简单和漂亮，能是正确的吗？的确，这种写法并不是“完全正确”的最优快速排序实现。但是，我在这里并不想深入探讨性能上的问题。我想重点强调的是，纯函数式编程是一种思维上的改变，是一种完全不同的编程思维模式和方法，就相当于你要重新开始学习另外一种编程方式。首先，让我先定义一个问题，然后用函数式的方式解决它。我们要做的基本上就是按升序排序一个数组。为了完成这个任务，我使用曾经改变了我们这个世界的快速排序算法，下面是它几个基本的排序规则：
[*]如果数组只有一个元素，返回这个数组
[*]多于一个元素时，随机选择一个基点元素P，把数组分成两组。使得第一组中的元素全部 <p，第二组中的全部元素 >p。然后对这两组数据递归的使用这种算法。
那么，如何用函数式的方式思考、函数式的方式编程实现？在这里，我将模拟同一个程序员的两个内心的对话，这两个内心的想法很不一样，一个使用命令式的编程思维模式，这是这个程序员从最初学习编码就形成的思维模式。而第二个内心做了一些思想上的改造，清洗掉了所有以前形成的偏见：用函数式的方式思考。事实上，这程序员就是我，现在正在写这篇文章的我。你将会看到两个完全不同的我。没有半点假话。让我们在这个简单例子上跟Java进行比较：
public class Quicksort{
private int[] numbers;
private int number;
public void sort(int[] values) {
if (values == null || values.length == 0){
return;
}
this.numbers = values;
number = values.length;
quicksort(0, number - 1);
}
private void quicksort(int low, int high) {
int i = low, j = high;
int pivot = numbers;
while (i <= j) {
while (numbers < pivot) {
i++;
}
while (numbers > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
i++;
j--;
}
}
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
private void swap(int i, int j) {
int temp = numbers;
numbers = numbers;
numbers = temp;
}
}
哇塞。到处都是i和j，这是干嘛呢？为什么Java代码跟Haskell代码比较起来如此的长？这就好像是30年前拿C语言和汇编语言进行比较！从某种角度看，这是同量级的差异。
让我们俩继续两个”我”之间的对话。
JAVA:
好 ，我先开始定义Java程序需要的数据结构。一个类，里面含有一些属性来保存状态。我觉得应该使用一个整数数组作为主要数据对象，针对这个数组进行排序。还有一个方法叫做sort，它有一个参数，是用来传入两个整数做成的数组，sort方法就是用来对这两个数进行排序。public class Quicksort {
private int[] numbers;
public void sort(int[] values) {
}
}
HASKELL:
好，这里不需要状态，不需要属性。我需要定义一个函数，用它来把一个list转变成另一个list。这两个list有相同之处，它们都包含一样的元素，并有各自的顺序。我如何用统一的形式描述这两个list？啊哈！typeclass….我需要一个typeclass来实现这个…对，Ord.quicksort :: Ord a => ->
我要从简单的开始，如果是空数组，如果数组是空的，我应该返回这个数组。但是…该死的，当这个数组是null时，程序会崩溃。让我来在sort方法开始的地方加一个if语句，预防这种事情。if (values.length == 0 || values == null) {
return;
}
HASKELL:
先简单的，一个空list。对于这种情况，需要使用模式匹配。我看看如何使用，好的，非常棒！
quicksort [] = []
JAVA:
好的，现在让我用递归来处理正常的情况。正常的情况下，需要记录sort方法参数状态。需要它的长度，所以，我还需要在Quicksort类里添加一个新属性
public void sort(int[] values) {
if (values.length == 0 || values == null) {
return;
}
this.numbers = values;
this.length = values.length;
quicksort(0, length - 1);
}
HASKELL:
这已经是递归了。不需要在再做任何事情。
No code. Nothing. Nada. That's good.
JAVA:
现在，我需要根据上面说明的规则实现快速排序的过程。我选择第一个元素作为基点元素，这不需要使用其它奇异方法。比较，递归。每次比较从两头同时遍历，一个从头至尾(i, 生成<p的list)，一个从尾至头(j, 生成>p的list)。每次在i方向遍历中发现有比j方向遍历的当前值大时，交互它们的位置。当i的位置超过j时，停止比较，对形成的两个新队列继续递归调用。private void quicksort(int low, int high) {
int i = low, j = high;
int pivot = numbers;
while (i <= j) {
while (numbers < pivot) {
i++;
}
while (numbers > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
i++;
j--;
}
}
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
交换位置的方法：
private void swap(int i, int j) {
int temp = numbers;
numbers = numbers;
numbers = temp;
}
使用Haskell
我先定义一个lesser和一个greater作为每次迭代的两个队列。等一下！我们可以使用标准的head和tail函数来获取第一个值作为基点数据。这样我们可以它的两个部分进行递归调用！
quicksort (p:xs) = (quicksort lesser) ++ ++ (quicksort greater)
非常好，这里我声明了lesser和greater两个list，现在我将要用where——Haskell语言里一个十分强大的用来描述函数内部值(not 变量)的关键字——描述它们。我需要使用filter函数，因为我们已经得到除首元素之外的其它元素，我们可以调用(xs)，就是这样：
where
lesser = filter (< p) xs
greater = filter (>= p) xs
我试图用最详细的语言解释Java里用迭代+递归实现快速排序。但是，如果在java代码里，我们少写了一个i++，我们弄错了一个while循环条件，会怎样？好吧，这是一个相对简单的算法。但我们可以想象一下，如果我们整天写这样的代码，整天面对这样的程序，或者这个排序只是一个非常复杂的算法的第一步，将会出现什么情况。当然，它是可以用的，但难免会产生潜在的、内部的bug。
现在我们看一下关于状态的这些语句。如果出于某些原因，这个数组是空的，变成了null，当我们调用这个Java版的快速排序方法时会出现什么情况？还有性能上的同步执行问题，如果16个线程想同时访问Quicksort方法会怎样？我们就要需要监控它们，或者让每个线程拥有一个实例。越来越乱。
最终归结到编译器的问题。编译器应该足够聪明，能够“猜”出应该怎样做，怎样去优化。程序员不应该去思考如何索引，如何处理数组。程序员应该思考数据本身，如何按要求变换数据。也许你会认为函数式编程给思考算法和处理数据增添的复杂，但事实上不是这样。是编程界普遍流行的命令式编程的思维阻碍了我们。
事实上，你完全没必要放弃使用你喜爱的命令式编程语言而改用Haskell编程。Haskell语言有其自身的缺陷。只要你能够接受函数式编程思维，你就能写出更好的Java代码。你通过学习函数式编程能变成一个更优秀的程序员。
看看下面的这种Java代码？
public List<Comparable> sort(List<Comparable> elements) {
if (elements.size() == 0) return elements;
Stream<Comparable> lesser = elements.stream()
.filter(x -> x.compareTo(pivot) < 0)
.collect(Collectors.toList());
Stream<Comparable> greater = elements.stream()
.filter(x -> x.compareTo(pivot) >= 0)
.collect(Collectors.toList());
List<Comparable> sorted = new ArrayList<Comparable>();
sorted.addAll(quicksort(lesser));
sorted.add(pivot);
sorted.addAll(quicksort(greater));
return sorted;
}
是不是跟Haskell代码很相似？没错，也许你现在使用的Java版本无法正确的运行它，这里使用了lambda函数，Java8中引入的一种非常酷的语法。看到没有，函数式语法不仅能让一个程序员变得更优秀，也会让一种编程语言更优秀。 :)
函数式编程是一种编程语言向更高抽象阶段发展的自然进化结果。就跟我们认为用C语言开发Web应用十分低效一样，这些年来，我们也认为命令式编程语言也是如此。使用这些语言是程序员在开发时间上的折中选择。为什么很多初创公司会选择Ruby开发他们的应用，而不是使用C++？因为它们能使开发周期更短。不要误会。我们可以把一个程序员跟一个云计算单元对比。一个程序员一小时的时间比一个高性能AWS集群服务器一小时的时间昂贵的多。通过让犯错误更难，让出现bug的几率更少，使用更高的抽象设计，我们能使程序员变得更高效、更具创造性和更有价值。
感谢楼主分享
页:
[1]