[[119533]]  

作為一個對Haskell語言[1]徹頭徹尾的新手，當***次看到一個用這種語言編寫的快速排序算法的優(yōu)雅例子時，我立即對這種語言發(fā)生了濃厚的興趣。下面就是這個例子：

quicksort :: Ord a => [a] -> [a]    
quicksort [] = []    
quicksort (p:xs) =    
    (quicksort lesser) ++ [p] ++ (quicksort greater)  
    where  
        lesser = filter (< p) xs  
        greater = filter (>= p) xs  

我很困惑。如此的簡單和漂亮，能是正確的嗎？的確，這種寫法并不是“完全正確”的***快速排序?qū)崿F(xiàn)。但是，我在這里并不想深入探討性能上的問題[2]。我想重點強調(diào)的是，純函數(shù)式編程是一種思維上的改變，是一種完全不同的編程思維模式和方法，就相當于你要重新開始學(xué)習(xí)另外一種編程方式。

首先，讓我先定義一個問題，然后用函數(shù)式的方式解決它。我們要做的基本上就是按升序排序一個數(shù)組。為了完成這個任務(wù)，我使用曾經(jīng)改變了我們這個世界的快速排序算法[3]，下面是它幾個基本的排序規(guī)則：

• 如果數(shù)組只有一個元素，返回這個數(shù)組
• 多于一個元素時，隨機選擇一個基點元素P，把數(shù)組分成兩組。使得***組中的元素全部 <p，第二組中的全部元素 >p。然后對這兩組數(shù)據(jù)遞歸的使用這種算法。

那么，如何用函數(shù)式的方式思考、函數(shù)式的方式編程實現(xiàn)？在這里，我將模擬同一個程序員的兩個內(nèi)心的對話，這兩個內(nèi)心的想法很不一樣，一個使用命令式的編程思維模式，這是這個程序員從最初學(xué)習(xí)編碼就形成的思維模式。而第二個內(nèi)心做了一些思想上的改造，清洗掉了所有以前形成的偏見：用函數(shù)式的方式思考。事實上，這程序員就是我，現(xiàn)在正在寫這篇文章的我。你將會看到兩個完全不同的我。沒有半點假話。

讓我們在這個簡單例子上跟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]

讓我們倆繼續(xù)兩個”我”之間的對話。

JAVA:

好 ，我先開始定義Java程序需要的數(shù)據(jù)結(jié)構(gòu)。一個類，里面含有一些屬性來保存狀態(tài)。我覺得應(yīng)該使用一個整數(shù)數(shù)組作為主要數(shù)據(jù)對象，針對這個數(shù)組進行排序。還有一個方法叫做sort，它有一個參數(shù)，是用來傳入兩個整數(shù)做成的數(shù)組，sort方法就是用來對這兩個數(shù)進行排序。

public class Quicksort {    
    private int[] numbers;  
 
    public void sort(int[] values) {  
 
    }  
}  

HASKELL:

好，這里不需要狀態(tài)，不需要屬性。我需要定義一個函數(shù)，用它來把一個list轉(zhuǎn)變成另一個list。這兩個list有相同之處，它們都包含一樣的元素，并有各自的順序。我如何用統(tǒng)一的形式描述這兩個list？啊哈！typeclass….我需要一個typeclass來實現(xiàn)這個…對，Ord.

quicksort :: Ord a => [a] -> [a]    

JAVA:

我要從簡單的開始，如果是空數(shù)組，如果數(shù)組是空的，我應(yīng)該返回這個數(shù)組。但是…該死的，當這個數(shù)組是null時，程序會崩潰。讓我來在sort方法開始的地方加一個if語句，預(yù)防這種事情。

if (values.length == 0 || values == null) {    
    return;  
}  

HASKELL:

先簡單的，一個空list。對于這種情況，需要使用模式匹配。我看看如何使用，好的，非常棒！

quicksort [] = []    

JAVA:

好的，現(xiàn)在讓我用遞歸來處理正常的情況。正常的情況下，需要記錄sort方法參數(shù)狀態(tài)。需要它的長度，所以，我還需要在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:

這已經(jīng)是遞歸了。不需要在再做任何事情。

No code. Nothing. Nada. That's good.    

JAVA:

現(xiàn)在，我需要根據(jù)上面說明的規(guī)則實現(xiàn)快速排序的過程。我選擇***個元素作為基點元素，這不需要使用其它奇異方法。比較，遞歸。每次比較從兩頭同時遍歷，一個從頭至尾(i, 生成<p的list)，一個從尾至頭(j, 生成>p的list)。每次在i方向遍歷中發(fā)現(xiàn)有比j方向遍歷的當前值大時，交互它們的位置。當i的位置超過j時，停止比較，對形成的兩個新隊列繼續(xù)遞歸調(diào)用。

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函數(shù)來獲取***個值作為基點數(shù)據(jù)。這樣我們可以它的兩個部分進行遞歸調(diào)用！

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)    

非常好，這里我聲明了lesser和greater兩個list，現(xiàn)在我將要用where——Haskell語言里一個十分強大的用來描述函數(shù)內(nèi)部值(not 變量)的關(guān)鍵字——描述它們。我需要使用filter函數(shù)，因為我們已經(jīng)得到除首元素之外的其它元素，我們可以調(diào)用(xs)，就是這樣：

where  
    lesser = filter (< p) xs  
    greater = filter (>= p) xs  

我試圖用最詳細的語言解釋Java里用迭代+遞歸實現(xiàn)快速排序。但是，如果在java代碼里，我們少寫了一個i++，我們弄錯了一個while循環(huán)條件，會怎樣？好吧，這是一個相對簡單的算法。但我們可以想象一下，如果我們整天寫這樣的代碼，整天面對這樣的程序，或者這個排序只是一個非常復(fù)雜的算法的***步，將會出現(xiàn)什么情況。當然，它是可以用的，但難免會產(chǎn)生潛在的、內(nèi)部的bug。

現(xiàn)在我們看一下關(guān)于狀態(tài)的這些語句。如果出于某些原因，這個數(shù)組是空的，變成了null，當我們調(diào)用這個Java版的快速排序方法時會出現(xiàn)什么情況？還有性能上的同步執(zhí)行問題，如果16個線程想同時訪問Quicksort方法會怎樣？我們就要需要監(jiān)控它們，或者讓每個線程擁有一個實例。越來越亂。

最終歸結(jié)到編譯器的問題。編譯器應(yīng)該足夠聰明，能夠“猜”出應(yīng)該怎樣做，怎樣去優(yōu)化[5]。程序員不應(yīng)該去思考如何索引，如何處理數(shù)組。程序員應(yīng)該思考數(shù)據(jù)本身，如何按要求變換數(shù)據(jù)。也許你會認為函數(shù)式編程給思考算法和處理數(shù)據(jù)增添的復(fù)雜，但事實上不是這樣。是編程界普遍流行的命令式編程的思維阻礙了我們。

事實上，你完全沒必要放棄使用你喜愛的命令式編程語言而改用Haskell編程。Haskell語言有其自身的缺陷[6]。只要你能夠接受函數(shù)式編程思維，你就能寫出更好的Java代碼。你通過學(xué)習(xí)函數(shù)式編程能變成一個更優(yōu)秀的程序員。

看看下面的這種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代碼很相似？沒錯，也許你現(xiàn)在使用的Java版本無法正確的運行它，這里使用了lambda函數(shù)，Java8中引入的一種非常酷的語法[7]?？吹?jīng)]有，函數(shù)式語法不僅能讓一個程序員變得更優(yōu)秀，也會讓一種編程語言更優(yōu)秀。 [[119534]]

函數(shù)式編程是一種編程語言向更高抽象階段發(fā)展的自然進化結(jié)果。就跟我們認為用C語言開發(fā)Web應(yīng)用十分低效一樣，這些年來，我們也認為命令式編程語言也是如此。使用這些語言是程序員在開發(fā)時間上的折中選擇。為什么很多初創(chuàng)公司會選擇Ruby開發(fā)他們的應(yīng)用，而不是使用C++？因為它們能使開發(fā)周期更短。不要誤會。我們可以把一個程序員跟一個云計算單元對比。一個程序員一小時的時間比一個高性能AWS集群服務(wù)器一小時的時間昂貴的多。通過讓犯錯誤更難，讓出現(xiàn)bug的幾率更少，使用更高的抽象設(shè)計，我們能使程序員變得更高效、更具創(chuàng)造性和更有價值。

標注：

[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/tuto…..icksort/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 [[119534]]

[7] See http://zeroturnaround.com/rebellabs/java-8-explained-applying-lambdas-to-java-collections/

英文原文：Programming (and thinking) the functional w

譯文出自：http://www.vaikan.com/programming-thinking-functional-way/