Haskell語言實例分析

這篇“Haskell語言實例分析”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Haskell語言實例分析”文章吧。

例子：

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]，下面是它幾個基本的排序規(guī)則：

• 如果數組只有一個元素，返回這個數組

• 多于一個元素時，隨機選擇一個基點元素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]

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

JAVA:

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

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

HASKELL:

好，這里不需要狀態(tài)，不需要屬性。我需要定義一個函數，用它來把一個list轉變成另一個list。這兩個list有相同之處，它們都包含一樣的元素，并有各自的順序。我如何用統(tǒng)一的形式描述這兩個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方法參數狀態(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:

這已經是遞歸了。不需要在再做任何事情。

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

JAVA:

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

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循環(huán)條件，會怎樣？好吧，這是一個相對簡單的算法。但我們可以想象一下，如果我們整天寫這樣的代碼，整天面對這樣的程序，或者這個排序只是一個非常復雜的算法的***步，將會出現什么情況。當然，它是可以用的，但難免會產生潛在的、內部的bug。

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

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

事實上，你完全沒必要放棄使用你喜愛的命令式編程語言而改用Haskell編程。Haskell語言有其自身的缺陷[6]。只要你能夠接受函數式編程思維，你就能寫出更好的Java代碼。你通過學習函數式編程能變成一個更優(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代碼很相似？沒錯，也許你現在使用的Java版本無法正確的運行它，這里使用了lambda函數，Java8中引入的一種非?？岬恼Z法[7]?？吹經]有，函數式語法不僅能讓一個程序員變得更優(yōu)秀，也會讓一種編程語言更優(yōu)秀。

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

以上就是關于“Haskell語言實例分析”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業(yè)資訊頻道。