Haskell/惰性

Haskell 效能

介紹
循序漸進的例子
圖歸約
惰性
時間和空間分析
嚴格性
演算法複雜度
資料結構
 並行

“

努力工作以後會得到回報。懶惰現在就有回報！- 史蒂文·賴特

”

介紹

到目前為止，你已經知道 Haskell 使用惰性求值，這意味著在必要之前不會對任何東西進行求值。但是，“直到必要”到底是什麼意思呢？在本章中，我們將瞭解惰性求值是如何工作的（有多少魔法），它對函數語言程式設計到底意味著什麼，以及如何充分利用它。

首先，讓我們考慮惰性求值的原因和影響。乍一看，我們可能會認為惰性求值會使程式更高效。畢竟，還有什麼比什麼都不做更有效率的呢？然而，在實踐中，惰性往往會引入開銷，導致程式設計師尋找可以使他們的程式碼更加嚴格的地方。惰性的真正好處在於使正確的事物足夠有效。惰性求值使我們能夠編寫比在嚴格環境中更簡單、更優雅的程式碼。

非嚴格性與惰性

惰性和非嚴格性之間存在細微的差別。非嚴格語義指的是 Haskell 程式具有的一個你可以依賴的屬性：在需要之前不會對任何東西進行求值。惰性求值是使用一種叫做thunk的機制來實現非嚴格性的方式，我們將在下一節中解釋。然而，這兩個概念是如此密切相關，以至於將它們一起解釋會有所幫助。瞭解 thunk 有助於理解非嚴格性，而非嚴格性的語義解釋了我們為什麼首先在 Haskell 中使用惰性求值。因此，我們將同時介紹這些概念，並且不會特別努力地防止它們交織在一起（除了將術語弄清楚）。

Thunk 和弱頭正規化

你需要理解兩個原則，才能瞭解 Haskell 中的程式是如何執行的。首先，我們有非嚴格性的特性：我們儘可能少地進行求值，並儘可能地延遲求值。其次，Haskell 值是高度分層的；“求值”一個 Haskell 值可能意味著求值到這些層中的任何一層。讓我們使用一個對來逐步瞭解一些例子。

let (x, y) = (length [1..5], reverse "olleh") in ...

假設在“in”部分，我們使用了 x 和 y — 否則，我們根本不需要求值 let 繫結！右側可以是 undefined，如果“in”部分沒有提及 x 或 y，它仍然可以工作。這個假設將在本節中所有示例中保持有效。

我們對 x 知之多少？我們可以計算出 x 必須是 5 並且 y 是 "hello"，但請記住第一個原則：我們不會對 length 和 reverse 的呼叫進行求值，直到我們被迫這樣做。因此，我們說 x 和 y 都是thunk：也就是說，它們是帶有求值方法的未求值值。例如，對於 x，這個方法表示“求值 length [1..5]”。但是，我們實際上正在對左側進行一些模式匹配。如果我們刪除了模式匹配，會發生什麼？

let z = (length [1..5], reverse "olleh") in ...

儘管對我們來說，z 是一個對還是非常明顯的，但是編譯器看到我們根本沒有嘗試對“=”符號右側的值進行解構，所以它並不關心那裡是什麼。它讓 z 自身成為一個 thunk。稍後，當我們嘗試使用 z 時，我們可能需要一個或兩個元件，因此我們必須對 z 進行求值，但現在，它可以是一個 thunk。

上面，我們說 Haskell 值是分層的。如果我們對 z 進行模式匹配，我們可以看到這一點。

let z     = (length [1..5], reverse "olleh")
   (n, s) = z 
in ...

在第一行執行後，z 只是一個 thunk。我們不知道它是什麼型別的值，因為我們還沒有被要求找出它。然而，在第二行中，我們使用對模式對 z 進行模式匹配。編譯器認為“我最好確保這個模式確實與 z 匹配，為了做到這一點，我需要確保 z 是一個對。”注意，我們還沒有對元件部分（對 length 和 reverse 的呼叫）做任何事情，所以它們可以保持未求值狀態。換句話說，z，它只是一個 thunk，被求值為類似 (*thunk*, *thunk*) 的東西，而 n 和 s 成為 thunk，當它們被求值時，將成為原始 z 的元件部分。

讓我們嘗試一個稍微複雜一點的模式匹配。

let z     = (length [1..5], reverse "olleh")
   (n, s) = z 
   'h':ss = s
in ...

對 z 的第二個元件的模式匹配會導致一些求值。編譯器希望檢查 'h':ss 模式是否與對的第二個元件匹配。因此，它

對 s 的頂層進行求值，以確保它是一個 cons 單元：s = *thunk* : *thunk*。（如果 s 是一個空列表，我們將在此時遇到模式匹配失敗錯誤。）
對它剛剛揭示的第一個 thunk 進行求值，以確保它是一個 cons 單元：'h':ss = 'h' : *thunk*。

列表的其餘部分保持未求值狀態，而 ss 成為一個 thunk，當它被求值時，將是這個列表的其餘部分。

逐步求值 `(4, [1, 2])`。第一個階段是完全未求值的；所有後續形式都在 WHNF 中，最後一個形式也在正常形式中。

我們可以對（大多數）Haskell 值進行“部分求值”。此外，我們還可以從某種意義上來說明我們能夠進行的最小求值量。例如，如果我們有一個對 thunk，那麼最小求值量會將我們帶到帶有兩個未求值元件的對建構函式：(*thunk*, *thunk*)。如果我們有一個列表，最小求值量將我們帶到一個 cons 單元格 *thunk* : *thunk* 或一個空列表 []。請注意，在空列表情況下，無法對值進行更多求值；它被稱為處於規範形式。如果我們處於任何中間步驟，以便我們已經對值執行了至少一些求值，則它處於弱首規範形式 (WHNF)。（也存在“首規範形式”，但它在 Haskell 中未使用。）完全求值 WHNF 中的某個東西會將其簡化為規範形式；如果我們在某個時候需要，比如，將 z 列印給使用者，我們需要完全對其進行求值，包括對 length 和 reverse 的呼叫，到 (5, "hello")，它處於規範形式。對值執行任何程度的求值有時被稱為強制該值。

請注意，對於某些值，只有一個結果。例如，您無法對整數進行部分求值。它要麼是一個 thunk，要麼處於規範形式。此外，如果我們有一個具有嚴格元件的建構函式（用感嘆號註釋，例如 data MaybeS a = NothingS | JustS !a），則這些元件在評估上面的級別時會立即被評估。也就是說，我們永遠不會有 JustS *thunk*——一旦我們達到這個級別，JustS 元件上的嚴格性註釋就會迫使我們評估元件部分。

在本節中，我們探討了惰性求值的基礎知識。我們已經看到，直到需要時才會對任何東西進行求值（事實上，Haskell 值求值的唯一地方是在模式匹配中以及在某些基本 IO 函式內部）。這個原則甚至適用於評估值——我們對值進行的最小工作量是計算結果所需的。

惰性和嚴格函式

函式可以是“在引數中”惰性或嚴格的。大多數函式都需要對它們的引數做些什麼，這將涉及將這些引數評估到不同的級別。例如，length 只需要評估您提供的引數中的 cons 單元格，而不必評估這些 cons 單元格的內容。length *thunk* 可能會評估為類似 length (*thunk* : *thunk* : *thunk* : []) 的東西，這反過來又會評估為 3。其他人需要完全評估他們的引數，例如 (length . show)。如果你有 length $ show *thunk*，除了將該 thunk 評估為規範形式之外，你沒有其他辦法可以做任何事情。

因此，一些函式比其他函式更全面地評估它們的引數。給定兩個具有一個引數的函式 f 和 g，如果 f x 比 g x 更深入地評估 x，則我們說 f 比 g 更嚴格。通常，我們只關心 WHNF，因此將引數評估為至少 WHNF 的函式被稱為嚴格的，而執行任何評估的函式被稱為惰性的。具有多個引數的函式呢？好吧，我們可以談論函式在一個引數中是嚴格的，而在另一個引數中是惰性的。例如，給定一個類似於以下的函式

f x y = length $ show x

顯然，我們不需要對 y 執行任何評估，但我們需要完全將 x 評估為規範形式，因此 f 在其第一個引數中是嚴格的，但在第二個引數中是惰性的。

練習
為什麼我們必須在 `f x y = show x` 中完全將 `x` 評估為規範形式？哪個函式更嚴格？ f x = length [head x] g x = length (tail x)

在關於摺疊的原始討論中，我們討論了 foldl 的記憶體問題，這些問題透過嚴格評估的 foldl' 解決。本質上，foldr (:) [] 和 foldl (flip (:)) [] 都將它們的引數評估為相同的嚴格程度，但 foldr 可以立即開始生成值，而 foldl 需要一直評估 cons 單元格直到最後才能開始生成任何輸出。因此，有時嚴格性可能是寶貴的。

黑盒嚴格性分析

如果 `f` 在傳遞 undefined 時返回錯誤，則它必須是嚴格的。否則，它就是惰性的。

想象一下，我們得到了一些函式 f，它接受一個引數。我們不允許檢視它的原始碼，但我們想知道 f 是否嚴格。我們該怎麼做？可能最簡單的方法是使用標準 Prelude 值 undefined。強制 undefined 到任何級別的評估將使我們的程式停止並列印錯誤，因此所有這些都列印錯誤

let (x, y) = undefined in x
length undefined
head undefined
JustS undefined -- Using MaybeS as defined in the last section

因此，如果一個函式是嚴格的，將 undefined 傳遞給它會導致錯誤。如果函式是惰性的，將 undefined 傳遞給它不會列印錯誤，我們可以像往常一樣繼續。例如，以下 none 產生錯誤

let (x, y) = (4, undefined) in x
length [undefined, undefined, undefined]
head (4 : undefined)
Just undefined

因此，我們可以說 f 是一個嚴格函式，當且僅當 f undefined 導致列印錯誤並使我們的程式停止。

在非嚴格語義的背景下

我們目前所介紹的內容在你開始思考 id 之類的函式時是有意義的。id 是嚴格的嗎？我們本能的反應可能是“不！它沒有評估它的引數，因此它是惰性的”。但是，讓我們將上一節中的黑盒嚴格性分析應用於 id。顯然，id undefined 會列印錯誤並使我們的程式停止，所以我們不應該說 id 是嚴格的嗎？造成這種混淆的原因是 Haskell 的非嚴格語義使整個問題變得更加模糊。

根據非嚴格性，如果不需要對任何東西進行求值，則不會對其進行求值。在以下程式碼中，length undefined 會被評估嗎？

[4, 10, length undefined, 12]

如果您在 GHCi 中輸入此內容，它似乎是嚴格的——您會收到錯誤。但是，我們的問題有點像個陷阱。在沒有對該值做任何事情的情況下，談論值是否被評估沒有意義。想想看：如果我們在 GHCi 中輸入 head [1, 2, 3]，我們必須進行任何評估的唯一原因是 GHCi 必須將結果列印給我們。輸入 [4, 10, length undefined, 12] 再次需要 GHCi 將該列表列印給我們，因此它必須將其評估為規範形式。在您平均的 Haskell 程式中，直到我們開始在 main 中執行 IO 之前，什麼都不會被評估。因此，在不知道它被傳遞給了什麼、上層是什麼的情況下，說某個東西是否被評估是沒有意義的。這裡的一個教訓是：不要盲目地信任 GHCi，因為GHCi 中的所有內容都透過 IO 過濾！

因此，當我們說“f x 是否強制 x？”時，我們的真正意思是“鑑於我們正在強制 f x，x 是否因此而被強制？”。現在我們可以將注意力回到 id。如果我們將 id x 強制為規範形式，那麼 x 將被強制為規範形式，因此我們得出結論，id 是嚴格的。id 本身不評估它的引數，它只是將其傳遞給呼叫者，而呼叫者將對其進行評估。一種觀察這種方式是在以下程式碼中

-- We evaluate the right-hand of the let-binding to WHNF by pattern-matching
-- against it.
let (x, y) = undefined in x -- Error, because we force undefined.
let (x, y) = id undefined in x -- Error, because we force undefined.

id 不會“停止”強制，因此它是嚴格的。將此與一個明顯是惰性的函式 const (3, 4) 進行對比

let (x, y) = undefined in x -- Error, because we force undefined.
let (x, y) = const (3, 4) undefined -- No error, because const (3, 4) is lazy.

關於事物的語義觀點

如果您熟悉語義學（也許您已經閱讀了華夏公益教科書章節？），那麼函式的嚴格性可以用非常簡潔的方式概括起來

f ⊥ = ⊥ ⇔ f 是嚴格的

假設這一點，我們可以說所有型別為 forall a. a 的東西，包括 undefined、error "any string"、throw 等等，都具有 ⊥ 的意義。

惰性模式匹配

您可能在 Haskell 原始碼中看到了以下模式匹配。

-- From Control.Arrow
(***) f g ~(x, y) = (f x, g y)

問題是：上面的模式匹配中的波浪號 (~) 代表什麼？~ 建立一個惰性模式或不可否認模式。通常，如果您使用建構函式作為模式的一部分進行模式匹配，您必須評估傳遞給該函式的任何引數以確保它與模式匹配。例如，如果您有像上面的函式，那麼當您呼叫該函式時，第三個引數將被評估以確保該值與模式匹配。（請注意，第一個和第二個引數不會被評估，因為模式 f 和 g 匹配任何東西。同樣值得注意的是，元組的元件不會被評估：只有“頂層”。嘗試 let f (Just x) = 1 in f (Just undefined) 來檢視這一點。）

但是，在模式前加上波浪號會延遲值的評估，直到實際使用元件部分。但您冒著值可能與模式不匹配的風險——您告訴編譯器“相信我，我知道它會成功”。（如果事實證明它與模式不匹配，您將得到執行時錯誤。）為了說明差異

Prelude> let f (x,y) = 1
Prelude> f undefined
*** Exception: Prelude.undefined

Prelude> let f ~(x,y) = 1
Prelude> f undefined
1

在第一個示例中，該值被評估，因為它必須與元組模式匹配。您評估 undefined 並得到 undefined，這會停止執行過程。在後一個示例中，您不會在需要之前評估引數，結果是永遠不會，因此您傳遞給它 undefined 並不重要。為了將討論回到 (***)

Prelude> (const 1 *** const 2) undefined
(1,2)

如果模式不是不可否認的，示例將失敗。

何時使用惰性模式有意義？

本質上，當您只對該型別有一個建構函式時，使用惰性模式，例如元組。多個方程與不可否認模式不匹配。為了檢視這一點，讓我們檢查一下如果我們使 head 具有不可否認的模式會發生什麼

head' :: [a] -> a
head' ~[]     = undefined
head' ~(x:xs) = x

我們肯定使用其中一種模式，並且我們不需要在絕對必要之前評估引數的頂層，所以我們不知道它是一個空列表還是一個 cons 單元。由於我們使用的是第一個方程式的不可反駁模式，它將匹配，並且函式將始終返回未定義。

練習
為什麼將方程式的順序更改為`head'`在這裡不起作用？如果將第一個方程式更改為使用普通的可反駁模式，`head'`的行為是否仍與`head`不同？如果是，怎樣？

非嚴格語義的優點

為什麼首先要使 Haskell 成為非嚴格語言？有哪些優點？

無需時間損失的關注點分離

惰性求值鼓勵在編碼方面的一種“所見即所得”的心態。例如，假設您想在一個長列表中找到最小的三個數字。在 Haskell 中，這非常自然地實現：take 3 (sort xs)。但是，在嚴格語言中對該程式碼進行天真的轉換將是一個非常糟糕的想法！它將涉及計算整個排序列表，然後只保留前三個元素。但是，使用惰性求值，我們一旦將列表排序到第三個元素就停止，因此這個自然的定義最終變得高效（取決於排序的實現）。

再舉一個例子，來自 Data.List 的函式isInfixOf允許您檢視一個字串是否是另一個字串的子字串。它很容易定義為

isInfixOf :: Eq a => [a] -> [a] -> Bool
isInfixOf x y = any (isPrefixOf x) (tails y)

同樣，這在嚴格語言中將是自殺，因為計算列表的所有尾部將非常耗時。但是，在這裡，我們只評估每個尾部的足夠元素來確定它是否具有字首x，一旦找到具有字首x的元素就停止並返回True。

還有很多類似的例子。^{^[1] 所以我們可以編寫程式碼，看起來和感覺都很自然，並且不會產生任何時間損失。}

然而，正如計算機科學（以及生活中）中總是存在的那樣，存在權衡（特別是時間-空間權衡）。對於一個微不足道的計算（例如2+2），使用 thunk 代替普通的Int可能是浪費。有關更多示例，請參閱有關Haskell/Strictness的頁面。

改進的程式碼重用

程式碼重用通常是可取的。

例如，我們將再次（但更詳細地）討論來自 Data.List 的isInfixOf。讓我們看看完整定義

-- From the Prelude
or = foldr (||) False
any p = or . map p 
 
-- From Data.List
isPrefixOf []     _      = True
isPrefixOf _      []     = False
isPrefixOf (x:xs) (y:ys) = x == y && isPrefixOf xs ys 

tails []         = [[]]
tails xss@(_:xs) = xss : tails xs

-- Our function
isInfixOf :: Eq a => [a] -> [a] -> Bool
isInfixOf x y = any (isPrefixOf x) (tails y)

其中any、isPrefixOf和tails是從Data.List庫中獲取的函式。此函式確定它的第一個引數x是否作為第二個引數y的子序列出現；當應用於String（即[Char]）時，它檢查x是否是y的子字串。以嚴格的方式閱讀，它形成y的所有尾部的列表，然後檢查它們是否具有x作為字首。在嚴格的語言中，以這種方式編寫此函式（依賴於已經編寫的程式any、isPrefixOf和tails）將是愚蠢的，因為它將比它需要的慢得多。您最終將再次進行直接遞迴，或者在命令式語言中，進行幾個巢狀迴圈。您可能會從isPrefixOf中獲得一些用途，但您肯定不會使用tails。您可能會能夠編寫一個可用的短路any，但這將更多工作，因為您不希望使用foldr來完成它。

現在，在惰性語言中，所有短路操作都為您完成。您不會最終重新編寫foldr以在找到解決方案時進行短路，也不會重新編寫在tails中完成的遞迴，以便它再次提前停止。您可以更好地重用標準庫程式碼。惰性不僅僅是恆定因子速度問題，它對程式碼的編寫方式產生了質的影響。事實上，定義無限結構並只使用需要的部分很常見，而不必將構造資料結構的邏輯與確定是否需要任何部分的程式碼混合起來。程式碼模組化性得到提高，因為惰性為您提供了更多方法將程式碼分解成小塊，每個小塊都執行一項生成、過濾或以其他方式操作資料的簡單任務。

為什麼函數語言程式設計很重要主要集中在惰性至關重要的示例上，併為惰性求值為預設值提供了強有力的論據。

無限資料結構

示例

fibs = 1:1:zipWith (+) fibs (tail fibs)
"rock-scissors-paper" example from Bird&Wadler
prune . generate

無限資料結構通常也會打結，但科幻解釋最好留到下一節。可以將下一節移到本節之前，但我認為無限資料結構比打一般結更簡單

常見的非嚴格習慣用法

打結

更實用的例子？

repMin

科幻解釋：“只要你不試圖改變它們，你就可以從未來借用東西”。高階：“藍圖”技術。示例：來自 haskellwiki 的示例，來自郵件列表的示例。

起初，純函式式語言似乎在迴圈資料結構方面存在問題。假設我有一個這樣的資料型別

data Foo a = Foo {value :: a, next :: Foo a}

如果我想建立兩個物件“x”和“y”，其中“x”包含對“y”的引用，“y”包含對“x”的引用，那麼在傳統的語言中，這很簡單：建立物件，然後設定相關欄位指向彼此

 -- Not Haskell code
 x := new Foo;
 y := new Foo;
 x.value := 1;
 x.next := y;
 y.value := 2
 y.next := x;

在 Haskell 中，這種修改是不允許的。因此，我們依賴於惰性求值

circularFoo :: Foo Int 
circularFoo = x
   where
      x = Foo 1 y
      y = Foo 2 x

這取決於“Foo”建構函式是一個函式這一事實，就像大多數函式一樣，它被惰性求值。只有當某個欄位需要時，它才會被求值。

瞭解幕後發生的事情可能會有所幫助。當建立一個惰性值（例如，透過呼叫“Foo”）時，編譯器會生成一個稱為“thunk”的內部資料結構，其中包含函式呼叫和引數。當要求函式的值時，該函式被呼叫（正如您所期望的那樣）。但隨後 thunk 資料結構將被返回值替換。因此，任何其他引用該值的項都會立即獲得它，而無需呼叫函式。

（請注意，Haskell 語言標準沒有提到 thunk：它們是實現機制。從數學的角度來看，這是一個關於相互遞迴的簡單示例。）

所以，當我們呼叫“circularFoo”時，結果“x”實際上是一個 thunk。其中一個引數是對錶示“y”的第二個 thunk 的引用。這反過來又對錶示“x”的 thunk 進行了引用。如果我們隨後使用值“next x”，這將強制“x”thunk 被求值，並返回對“y”thunk 的引用。如果我使用值“next $ next x”，那麼我將強制對這兩個 thunk 求值。因此，現在這兩個 thunk 都已被實際的“Foo”結構替換，相互引用。這就是我們想要的。

這通常應用於建構函式，但並不侷限於建構函式。您可以同樣容易地編寫