Haskell/惰性

惰性 (解決方案)

Haskell 效能

介紹
逐步示例
圖約簡
惰性
時間和空間分析
嚴格性
演算法複雜度
資料結構
 並行

編輯本章

“

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

”

介紹

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

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

非嚴格性與惰性

惰性和非嚴格性之間存在細微差別。非嚴格語義是指 Haskell 程式的特定屬性，您可以依賴它：在需要之前不會進行任何求值。惰性求值是使用一種稱為thunk的機制來實現非嚴格性的方法，我們將在下一節中解釋。但是，這兩個概念密切相關，將它們一起解釋起來很有幫助。瞭解 thunk 有助於理解非嚴格性，而非嚴格性的語義解釋了我們為什麼要首先使用惰性求值。因此，我們將同時介紹這些概念，並且不會特別努力地將它們分開（除了要正確使用術語）。

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 以確保它是 '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 將 x 評估為比 g x 更深的級別，那麼我們說 f 比 g 更嚴格。通常，我們只關心 WHNF，因此將引數評估為至少 WHNF 的函式稱為嚴格函式，而沒有任何評估的函式稱為惰性函式。對於具有多個引數的函式呢？好吧，我們可以說函式在一個引數中是嚴格的，但在另一個引數中是惰性的。例如，給定如下函式

f x y = length $ show x

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

練習
為什麼我們必須將 x 在 f x y = show 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 傳遞給它將不會列印任何錯誤，我們可以照常進行。例如，以下內容都不會產生錯誤

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 單元。因為我們對第一個等式使用了一個 *不可反駁* 模式，它會匹配，函式將始終返回 undefined。

練習
為什麼將等式的順序更改為 `head'` 這裡沒有幫助？如果將第一個等式更改為使用普通的可反駁模式，`head'` 的行為是否仍然不同於 `head`？如果是，怎麼樣？

非嚴格語義的好處

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

沒有時間懲罰的關注點分離

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

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

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 中完成的遞迴，使其再次儘早停止。你可以更好地重用標準庫程式碼。惰性求值不僅僅是一個恆定因子的速度問題，它對程式碼的編寫方式產生了質的影響。事實上，定義無限結構並只使用所需的部分，而不是將構建資料結構的邏輯與確定是否需要任何部分的程式碼混合在一起，這很常見。程式碼模組化得到增強，因為惰性求值為你提供了更多方法將程式碼分解成小塊，每塊都完成一個簡單的資料生成、過濾或其他操作任務。

Why Functional Programming Matters 主要關注惰性求值至關重要的例子，併為惰性求值成為預設選擇提供了強有力的論據。

無限資料結構

例子

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”結構，相互引用。這就是我們想要的。

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