Haskell/效能介紹

執行模型

介紹惰性求值

程式設計不僅僅是編寫能工作的程式，還包括編寫需要很少記憶體和時間在計算機上執行的程式。雖然在指令式程式設計語言或嚴格的函式式語言（如 LISP 或 ML）中，時間和記憶體使用相對容易預測，但這裡的情況有所不同。在 Haskell 中，表示式按需求值。例如，表示式

head (map (2 *) [1 .. 10])

將按如下方式求值

 ⇒ head (map (2 *) (1 : [2 .. 10]))      ([1 .. 10])
 ⇒ head (2 * 1 : map (2 *) [2 .. 10])    (map)
 ⇒ 2 * 1                                 (head)
 ⇒ 2                                     (*)

head 函式僅要求列表的第一個元素，因此列表的其餘部分 map (2 *) [2 .. 10] 從未求值。由於這種策略只執行必要的求值，因此被稱為惰性求值。章節圖歸約 將詳細介紹它。

雖然惰性求值是 Haskell 的常用實現技術，但語言標準 僅指定 Haskell 具有非嚴格的語義，而沒有確定特定的執行模型。具有一個引數的函式 f 被認為是嚴格的，如果它的引數求值永遠迴圈或未定義時，它不會終止或產生錯誤。用 ⊥ 表示無限迴圈的“結果”，嚴格性的定義為

如果 f ⊥ = ⊥ ，則函式 f 被稱為嚴格的。

例如，嘗試將 1 加到一個永遠迴圈的數字上，仍然會永遠迴圈，所以 ⊥+1 = ⊥，加法函式 (+1) 是嚴格的。head 函式也是嚴格的，因為如果整個列表未定義，列表的第一個元素將不可用。但是，第一個元素可能已定義，而其餘列表則沒有。在這種情況下，我們有

 head (x : ⊥) = x

此等式意味著 head 不會求值其餘列表，否則它也會迴圈。因此，這種純粹的代數嚴格性屬性對於推理執行時間和記憶體非常有幫助。在像 LISP 或 ML 這樣的嚴格語言中，我們總是會得到 head (x:⊥) = ⊥，而 Haskell 作為“非嚴格的”意味著我們可以編寫非嚴格的函式，比如 head 的上述屬性或最簡單的示例 (const 1) ⊥ = 1。藉助於來自Prelude 的常量 undefined，我們甚至可以互動地探索嚴格性

> head (1 : undefined)
1
> head undefined
*** Exception: Prelude.undefined

在這些章節中將使用嚴格性和 ⊥。圖歸約 提供了更多入門示例，語義 中詳細闡述了語義觀點。

示例：fold

理解惰性求值的最佳方法是研究一個例子。因此，我們將考慮 foldr 及其變體的典型用例。章節演算法複雜度 回顧了研究程式時間和空間複雜度所需的基礎知識。

時間

考慮以下 isPrime 函式，該函式檢查一個數字是否為素數

 isPrime n     = not $ any (`divides` n) [2..n-1]
 d `divides` n = n `mod` d == 0
 any p         = or . map p
 or            = foldr (||) False

來自 Haskell Prelude 的輔助函式 any 檢查列表中是否存在至少一個滿足某個屬性 p 的元素。對於 isPrime，該屬性是“是 n 的除數”。

求值一個表示式所需的時間當然是由歸約步驟的數量來衡量的。如果 n 是一個素數，上述演算法將檢查從 2 到 n-1 的所有數字，因此最壞情況下的執行時間為$O(n)$ 歸約。但是，如果 n 不是素數，我們不需要遍歷所有這些數字，只要找到一個除數就可以停止，並報告 n 是合數。惰性求值的妙處在於這種行為已經內建在邏輯析取 || 中！

isPrime 42
 ⇒ not $ any (`divides` 42) [2..41]                               
 ⇒ not ( or (map (`divides` 42) [2..41]                         ) )
 ⇒ not ( or ((42 `mod` 2 == 0) :      map (`divides` 42) [3..41]) )
 ⇒ not (     (42 `mod` 2 == 0) || or (map (`divides` 42) [3..41]) )
 ⇒ not (                 True  || or (map (`divides` 42) [3..41]) )
 ⇒ not True
 ⇒ False

該函式在發現 42 是偶數後返回 False，|| 在第一個引數確定結果為 True 時不會檢視它的第二個引數。換句話說，我們有以下嚴格性屬性

 True || ⊥ = True

當然，以上演算法可以使用自定義迴圈來實現。但延遲求值的關鍵在於，我們可以透過重複使用標準的foldr以透明的方式來制定演算法，並且仍然可以獲得提前退出。換句話說，延遲求值是關於以模組化的方式制定快速演算法。一個極端的例子是使用無限資料結構來有效地模組化生成和修剪演算法。本章延遲求值將詳細介紹這種技術以及許多其他與延遲求值相關的巧妙技巧。

對執行時間進行詳細的圖約簡分析既不可行也不必要。可以使用一些捷徑，例如非嚴格性或延遲求值始終比急切求值需要更少的約簡步驟。這些將在圖約簡中介紹。

空間

雖然執行時間由約簡步驟的數量來建模，但記憶體使用量由表示式在求值過程中的大小來建模。不幸的是，很難預測，而且偏離正常的延遲求值過程（透過增加嚴格性）可以改善這種情況。更多細節請參見圖約簡。在這裡，我們將介紹一個非預期空間行為的典型示例。

天真地對大量整數求和

> foldr (+) 0 [1..1000000]
*** Exception: stack overflow

會產生堆疊溢位。發生了什麼？求值過程如下

foldr (+) 0 [1..1000000]
 ⇒ 1+(foldr (+) 0 [2..1000000])
 ⇒ 1+(2+(foldr (+) 0 [3..1000000]))
 ⇒ 1+(2+(3+(foldr (+) 0 [4..1000000]))

等等。我們可以看到表示式越來越大，需要越來越多的記憶體。在本例中，記憶體是在堆疊上分配的，用於在遞迴呼叫foldr返回後執行待處理的加法運算。在某個時刻，所需的記憶體超過了最大可能的堆疊大小，從而引發了“堆疊溢位”錯誤。不要擔心是堆疊還是堆，要記住的是，表示式的尺寸對應於使用的記憶體，我們可以看到，通常情況下，求值foldr (+) 0 [1..n]需要$O(n)$記憶體。

但是，應該可以在$O(1)$空間內完成，方法是保留到目前為止看到的數字的累積和，利用+是結合律。（一些讀者可能會注意到，這意味著使函式尾遞迴。）這就是foldl的作用

foldl (+) 0 [1..n]
 ⇒ foldl (+) (0+1) [2..n]
 ⇒ foldl (+) ((0+1)+2) [3..n]
 ⇒ foldl (+) (((0+1)+2)+3) [4..n]

但令我們驚恐的是，累積的和將不會被進一步約簡！它將在堆上增長，直到列表結束

 ⇒ ... ⇒ foldl (+) ((((0+1)+2)+3)+...) []
 ⇒ ((((0+1)+2)+3)+...)

隨後對這個巨大的未求值的和進行約簡也會導致堆疊溢位。（因此，僅僅引入一個累積引數並不能使其成為尾遞迴。）

問題在於，未求值的和對於單個整數來說是一個過大的表示，並且急切地對其進行求值更便宜。這就是foldl'的作用

foldl' f z []     = z
foldl' f z (x:xs) = z `seq` foldl' f (f z x) xs

這裡，求值a `seq` b將在繼續約簡b之前，將a約簡為弱頭正規化。這樣，求和過程就變成了

foldl' (+) 0 [1..n]
 ⇒ foldl' (+) (0+1) [2..n]
 ⇒ foldl' (+) (1+2) [3..n]
 ⇒ foldl' (+) (3+3) [4..n]
 ⇒ foldl' (+) (6+4) [5..n]
 ⇒ ...

在恆定空間內。

有關更多詳細資訊和示例，請閱讀本章圖約簡。

低階開銷

與急切求值相比，延遲求值會增加相當大的開銷，即使是整數或字元也必須儲存為指標，因為它們可能為⊥。一個包含 1 位元組字元的陣列比長度相同的String = [Char]緊湊得多。使用嚴格性註解、非盒裝型別和自動嚴格性分析，可以降低開銷。Haskell wiki 是一個很好的資源[1]，其中包含這些低階細節，但該維基百科目前不包含這些內容。

演算法和資料結構

演算法

雖然本維基百科不是一本關於演算法的通用書籍，但其中包含許多在函數語言程式設計中獨有的編寫高效程式的技術。本章演算法複雜性回顧了大 O 符號，並展示了一些來自實踐的示例。

在延遲求值中，重點是利用延遲求值以模組化的方式編寫高效演算法。

程式推導和等式推理的共同主題是從規範中推匯出一個高效的程式，方法是應用和證明方程，例如

map f . reverse  = reverse . map f
filter p . map f = map f . filter (p . f)

這種探索催生了一個寶石，即純粹的代數方法來進行動態規劃，這將在某個有良好名稱的章節中介紹。

另一種稱為融合或去森林化的等式技術旨在消除函式組合中的中間資料結構。例如，左側的組合

 map f . map g = map (f . g)

構造和解構一箇中間列表，而右側是對列表的單次遍歷。這裡的一般主題是融合構造器-解構器對，例如

 case (Just y) of { Just x -> f x; Nothing -> ...; } = f y

這將在某個有良好名稱的章節中詳細介紹。

資料結構

選擇正確的資料結構是成功的關鍵。雖然列表很常見，而且可以帶來意想不到的收穫，但它們更像是一種物化的迴圈，而不是一種具有快速訪問和更新功能的經典資料結構。許多語言都為這類資料結構提供了特殊支援，例如 C 語言中的陣列、Perl 語言中的雜湊表或 LISP 語言中的列表。在 Haskell 中，本質上傾向於任何型別的樹。但是，由於引數多型性和型別類，任何抽象型別（如平衡二叉樹）都易於使用和重用！本章資料結構詳細介紹了針對常見問題的資料結構的自然選擇。

因為 Haskell 是純粹的函式式語言，所以資料結構具有共同的特徵，即永續性。這意味著資料結構的舊版本仍然可用，例如在

 foo set = (newset, set)
   where newset = insert "bar" set

相比之下，命令式語言中的預設行為是瞬態的，即資料在原地更新，舊版本被覆蓋。例如，陣列是瞬態的。這就是為什麼它們在 Haskell 中要麼是不可變的，要麼需要單子來使用。幸運的是，許多瞬態結構（如佇列或堆）都有永續性對應物，本章資料結構還將溫和地介紹一些設計原則，例如關於攤銷。

並行性

並行的目標是在多個核心/計算機上並行執行演算法，以獲得更快的結果。由於 Haskell 由於其純度而不強制執行執行順序，因此非常適合制定並行演算法。

目前，Haskell 中的並行仍然是一個研究課題，並且正在進行實驗。有一些用於控制執行順序的組合子Control.Parallel.Strategies，但它們粒度相當細。對一個不太雄心勃勃但更實用的替代方案資料並行 Haskell的研究正在進行中。

本章並行尚未編寫，但旨在成為對並行演算法以及 Haskell 中當前可能性的簡要介紹。