JAVA: 好的，现在让我用递归来处理正常的情况。正常的情况下，需要记录sort方法参数状态。需要它的长度，所以，我还需要在Quicksort类里添加一个新属性。
1 2 3 4 5 6 7 8 | public void sort(int[] values) {
if (values.length == 0 || values == null) {
return;
}
this.numbers = values;
this.length = values.length;
quicksort(0, length - 1);
}
|
HASKELL: 这已经是递归了。不需要在再做任何事情。
1 | No code. Nothing. Nada. That's good.
|
JAVA: 现在，我需要根据上面说明的规则实现快速排序的过程。我选择第一个元素作为基点元素，这不需要使用其它奇异方法。比较，递归。每次比较从两头同时遍历，一个从头至尾(i, 生成<p的list)，一个从尾至头(j, 生成>p的list)。每次在i方向遍历中发现有比j方向遍历的当前值大时，交互它们的位置。当i的位置超过j时，停止比较，对形成的两个新队列继续递归调用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | private void quicksort(int low, int high) {
int i = low, j = high;
int pivot = numbers[low];
while (i <= j) {
while (numbers[i] < pivot) {
i++;
}
while (numbers[j] > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
i++;
j--;
}
}
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
|
交换位置的方法： 1 2 3 4 5 | private void swap(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
|
使用Haskell我先定义一个lesser和一个greater作为每次迭代的两个队列。等一下！我们可以使用标准的head和tail函数来获取第一个值作为基点数据。这样我们可以它的两个部分进行递归调用！
1 | quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
|
非常好，这里我声明了lesser和greater两个list，现在我将要用where——Haskell语言里一个十分强大的用来描述函数内部值(not 变量)的关键字——描述它们。我需要使用filter函数，因为我们已经得到除首元素之外的其它元素，我们可以调用(xs)，就是这样：
1 2 3 | where
lesser = filter (< p) xs
greater = filter (>= p) xs
|
我试图用最详细的语言解释Java里用迭代+递归实现快速排序。但是，如果在java代码里，我们少写了一个i++，我们弄错了一个while循环条件，会怎样？好吧，这是一个相对简单的算法。但我们可以想象一下，如果我们整天写这样的代码，整天面对这样的程序，或者这个排序只是一个非常复杂的算法的第一步，将会出现什么情况。当然，它是可以用的，但难免会产生潜在的、内部的bug。
现在我们看一下关于状态的这些语句。如果出于某些原因，这个数组是空的，变成了null，当我们调用这个Java版的快速排序方法时会出现什么情况？还有性能上的同步执行问题，如果16个线程想同时访问Quicksort方法会怎样？我们就要需要监控它们，或者让每个线程拥有一个实例。越来越乱。
最终归结到编译器的问题。编译器应该足够聪明，能够“猜”出应该怎样做，怎样去优化[5]。程序员不应该去思考如何索引，如何处理数组。程序员应该 思考数据本身，如何按要求变换数据。也许你会认为函数式编程给思考算法和处理数据增添的复杂，但事实上不是这样。是编程界普遍流行的命令式编程的思维阻碍 了我们。
事实上，你完全没必要放弃使用你喜爱的命令式编程语言而改用Haskell编程。Haskell语言有其自身的缺陷[6]。只要你能够接受函数式编程思维，你就能写出更好的Java代码。你通过学习函数式编程能变成一个更优秀的程序员。
看看下面的这种Java代码？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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中引入的一种非常酷的语法[7]。看到没有，函数式语法不仅能让一个程序员变得更优秀，也会让一种编程语言更优秀。 
函数式编程是一种编程语言向更高抽象阶段发展的自然进化结果。就跟我们认为用C语言开发Web应用十分低效一样，这些年来，我们也认为命令式编程语言也是如此。使用这些语言是程序员在开发时间上的折中选择。为什么很多初创公司会选择Ruby开发他们的应用，而不是使用C++？因为它们能使开发周期更短。不要误会。我们可以把一个程序员跟一个云计算单元对比。一个程序员一小时的时间比一个高性能AWS集群服务器一小时的时间昂贵的多。通过让犯错误更难，让出现bug的几率更少，使用更高的抽象设计，我们能使程序员变得更高效、更具创造性和更有价值。
标注： [1] Haskell from scratch courtesy of “Learn you a Haskell for Great Good!” [2] This quicksort in Haskell that I am showing here is not in-place quicksort so it loses one of its properties, which is memory efficiency. The in-place version in Haskell would be more like: 1 2 3 4 5 6 7 8 9 10 11 12 | import qualified Data.Vector.Generic as V
import qualified Data.Vector.Generic.Mutable as M
qsort :: (V.Vector v a, Ord a) => v a -> v a
qsort = V.modify go where
go xs | M.length xs < 2 = return ()
| otherwise = do
p <- M.read xs (M.length xs `div` 2)
j <- M.unstablePartition (< p) xs
let (l, pr) = M.splitAt j xs
k <- M.unstablePartition (== p) pr
go l; go $ M.drop k pr
|
Discussion here. [3] This version of quicksort is simplified for illustration purposes. It’s always good looking at the source. Boldly go and read this piece of History (with a capital H) by C.A.R. Hoare, “Quicksort”. [4] Taken from http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html [4] Will we consider uncontrolled state harmful the same way GOTO statement being considered harmful consolidated structured programming? [5] This wiki has LOTS of architectural information about the amazing Glasgow Haskell Compiler,ghc. https://ghc.haskell.org/trac/ghc/wiki/Commentary [6] A big question mark over time on functional programming languages has been the ability (or lack thereof) to effectively code User Interfaces. Don’t despair though! There’s this cool new thing called Functional Reactive Programming (FRP). Still performing babysteps, but there are already implementations out there. One that’s gaining lots of momentum is ReactJS/Om/ClojureScript web app stack. Guess that might be a good follow-up post [7] See http://zeroturnaround.com/rebellabs/java-8-explained-applying-lambdas-to-java-collections/ [英文原文：Programming (and thinking) the functional way ] | 
