函數式思維和函數式編程
作為一個對Hashell語言[1]徹頭徹尾的新手，當第一次看到一個用這種語言編寫的快速排序算法的優雅例子時，我立即對這種語言發生了濃厚的興趣。下面就是這個例子：
quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter (< p) xs greater = filter (>= p) xs
我很困惑。如此的簡單和漂亮，能是正確的嗎？的確，這種寫法并不是“完全正確”的最優快速排序實現。但是，我在這里并不想深入探討性能上的問題 [2]。我想重點強調的是，純函數式編程是一種思維上的改變，是一種完全不同的編程思維模式和方法，就相當于你要重新開始學習另外一種編程方式。
首先，讓我先定義一個問題，然后用函數式的方式解決它。我們要做的基本上就是按升序排序一個數組。為了完成這個任務，我使用曾經改變了我們這個世界的快速排序算法[3]，下面是它幾個基本的排序規則：
如果數組只有一個元素，返回這個數組
多于一個元素時，隨機選擇一個基點元素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[low + (high-low)/2];
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);
}
private void swap(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
} 哇塞。到處都是i和j，這是干嘛呢？為什么Java代碼跟Haskell代碼比較起來如此的長？這就好像是30年前拿C語言和匯編語言進行比較！從某種角度看，這是同量級的差異。[4]
讓我們倆繼續兩個”我”之間的對話。
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 => [a] -> [a]
JAVA:
我要從簡單的開始，如果是空數組，如果數組是空的，我應該返回這個數組。但是…該死的，當這個數組是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[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);
} 交換位置的方法：
private void swap(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
} 使用Haskell
我先定義一個
lesser和一個greater作為每次迭代的兩個隊列。等一下！我們可以使用標準的head和tail函數來獲取第一個值作為基點數據。這樣我們可以它的兩個部分進行遞歸調用！
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (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方法會怎樣？我們就要需要監控它們，或者讓每個線程擁有一個實例。越來越亂。
最終歸結到編譯器的問題。編譯器應該足夠聰明，能夠“猜”出應該怎樣做，怎樣去優化[5]。程序員不應該去思考如何索引，如何處理數組。程序員應該 思考數據本身，如何按要求變換數據。也許你會認為函數式編程給思考算法和處理數據增添的復雜，但事實上不是這樣。是編程界普遍流行的命令式編程的思維阻礙 了我們。
事實上，你完全沒必要放棄使用你喜愛的命令式編程語言而改用Haskell編程。Haskell語言有其自身的缺陷[6]。只要你能夠接受函數式編程思維，你就能寫出更好的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中引入的一種非常酷的語法[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:
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 ]