[[119533]]  

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

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

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

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

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

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

讓我們?cè)谶@個(gè)簡(jiǎn)單例子上跟Java進(jìn)行比較：

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代碼比較起來(lái)如此的長(zhǎng)？這就好像是30年前拿C語(yǔ)言和匯編語(yǔ)言進(jìn)行比較！從某種角度看，這是同量級(jí)的差異。[4]

讓我們倆繼續(xù)兩個(gè)”我”之間的對(duì)話(huà)。

JAVA:

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

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

HASKELL:

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

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

JAVA:

我要從簡(jiǎn)單的開(kāi)始，如果是空數(shù)組，如果數(shù)組是空的，我應(yīng)該返回這個(gè)數(shù)組。但是…該死的，當(dāng)這個(gè)數(shù)組是null時(shí)，程序會(huì)崩潰。讓我來(lái)在sort方法開(kāi)始的地方加一個(gè)if語(yǔ)句，預(yù)防這種事情。

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

HASKELL:

先簡(jiǎn)單的，一個(gè)空l(shuí)ist。對(duì)于這種情況，需要使用模式匹配。我看看如何使用，好的，非常棒！

quicksort [] = []    

JAVA:

好的，現(xiàn)在讓我用遞歸來(lái)處理正常的情況。正常的情況下，需要記錄sort方法參數(shù)狀態(tài)。需要它的長(zhǎng)度，所以，我還需要在Quicksort類(lèi)里添加一個(gè)新屬性。

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

我先定義一個(gè)lesser和一個(gè)greater作為每次迭代的兩個(gè)隊(duì)列。等一下！我們可以使用標(biāo)準(zhǔn)的head和tail函數(shù)來(lái)獲取***個(gè)值作為基點(diǎn)數(shù)據(jù)。這樣我們可以它的兩個(gè)部分進(jìn)行遞歸調(diào)用！

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

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

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

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

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

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

事實(shí)上，你完全沒(méi)必要放棄使用你喜愛(ài)的命令式編程語(yǔ)言而改用Haskell編程。Haskell語(yǔ)言有其自身的缺陷[6]。只要你能夠接受函數(shù)式編程思維，你就能寫(xiě)出更好的Java代碼。你通過(guò)學(xué)習(xí)函數(shù)式編程能變成一個(gè)更優(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代碼很相似？沒(méi)錯(cuò)，也許你現(xiàn)在使用的Java版本無(wú)法正確的運(yùn)行它，這里使用了lambda函數(shù)，Java8中引入的一種非常酷的語(yǔ)法[7]。看到?jīng)]有，函數(shù)式語(yǔ)法不僅能讓一個(gè)程序員變得更優(yōu)秀，也會(huì)讓一種編程語(yǔ)言更優(yōu)秀。 [[119534]]

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

標(biāo)注：

[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/