本節書摘來自異步社群《haskell并行與并發程式設計》一書中的第2章，第2.1節惰性求值和弱首範式，作者【英】simon marlow，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視
2.1 惰性求值和弱首範式
haskell并行與并發程式設計
haskell是一門惰性語言，即表達式是在其值需要使用時才被求值2。一般來說，不必擔心該過程如何發生，隻要表達式在需要時求值，不需要時不被求值即可。但是，當在代碼中使用了并行程式設計後，就需要告訴編譯器一些程式運作的資訊，即某些代碼應該并行執行。由于對惰性求值的工作方式有一個直覺的認識将有助于有效地進行并行程式設計，是以本節将以ghci作為試驗工具，探讨惰性求值的一些基本概念。
下面從非常簡單内容的開始：
<code>prelude> let x = 1 + 2 :: int</code>
這會将變量x綁定（bind）到表達式1 + 2（為了避免任何由重載帶來的複雜性，特指定為int類型）。此時，僅考慮haskell語言本身，1 + 2是和3相等的，是以這裡也可以寫成let x = 3 :: int，而且通過普通的haskell代碼無法将兩種寫法區分開。但出于并行程式設計的目的，這裡确實在意1 + 2和3的差別，因為1 + 2是一個還未開始的計算，其值也許可以通過其他方法并行地計算出來。當然，在實際中不會對像1 + 2這樣簡單情況使用并行計算，然而，其作為未求值計算的本質是仍然是重要的。
此刻，稱x為未求值的（unevaluated）。一般來說，在haskell中是無法得知x是未求值的，但幸運的是，ghci的調試器提供了一些指令，這些指令可以檢視haskell表達式的結構，但又不影響表達式本身。是以，可以通過使用這些指令來說明發生的情況。:sprint這條指令可以列印出表達式的值，但又不會引發表達式求值。
`prelude> :sprint x
x = _`
特殊符号_表示“未求值的”，對于這種情況，讀者也許聽過另一個詞“thunk”，即記憶體中表示1 + 2這個未求值計算的對象。此例中的thunk如圖2-1所示。
圖2-1 表示1 + 2的thunk
在圖中，x是一個指向記憶體對象的指針，該記憶體對象表示函數+應用于整數1和2。
該thunk表示x将在其值需要時被求值。在ghci中，觸發求值最容易的方法是将其列印出來，也就是說，在提示符後輸入x即可：
`prelude> x
3`
現在若通過:sprint檢視x的值，可以發現其已被求值：
x = 3`
從記憶體中的對象方面考慮，即表示1 + 2的thunk實際上被（裝箱的）整數3覆寫了3。是以，以後任何對x值的查詢都會立即傳回結果，這就是惰性求值的工作原理。
前面的例子比較簡單，再試一個稍為複雜的的示例：
`prelude> let x = 1 + 2 :: int
prelude> let y = x + 1
prelude> :sprint x
x = _
prelude> :sprint y
y = _`
這裡再次将變量x綁定到1 + 2，此外，還将變量y綁定到x + 1，然後，正如所預期的，:sprint指令顯示兩者均未被求值。在記憶體中，會有圖2-2所示的結構。
圖2-2 一個引用了另外的thunk的thunk
不幸的是，該結構無法被直接檢視，讀者隻有相信這裡所畫的圖是正确的。
現在，為了計算y的值，需要x的值，即y依賴于x。是以，對y的求值同時會導緻對x的求值。這次使用不同方法來強制求值，即通過haskell内建的seq函數。
`prelude> seq y ()
()`
函數seq先對其第一個參數求值，這裡是y，然後傳回第二個參數，此例中，即()。再檢視此時x和y的值：
x = 3
y = 4`
正如所預期的，兩者均已被求值。是以，到目前為止一般性的原則如下。
• 定義一個表達值會建立一個thunk來表示該表達式。
• 在需要其值前，thunk保持未求值狀态。一旦被求值，則會被求出的值所替代。
再看一下增加一個資料結構會發生什麼情況：
prelude> let z = (x,x)
變量z綁定到了序對（x，x），指令:sprint顯示出一些有意思的内容：
prelude> :sprint z
z = (_,_)`
這裡隐含的結構如圖2-3所示。
變量z本身引用了序對（x，x），但序對的兩項均指向了未求值的，代表x的thunk。這說明資料結構可以使用未求值的表達式來建構。
圖2-3 兩項引用同一thunk的序對
下面再次将z變為thunk：
`prelude> import data.tuple
prelude data.tuple> let z = swap (x,x+1)`
函數swap的定義為：swap（a，b）=（b，a）。這次z和前面的一樣，是未求值的：
`prelude data.tuple> :sprint z
z = _`
這樣的話，當使用seq來對z求值時，就能看清楚具體發生的情況：
`prelude data.tuple> seq z ()
()
prelude data.tuple> :sprint z
函數seq執行後，導緻作為參數的z被求值，成為一個序對，但序對的兩項仍然處于未求值狀态。函數seq僅對其第一個參數的第一層構造求值，不再對剩下的結構繼續求值。對此有一個專門的稱呼：稱函數seq對第一個參數求值，使之成為弱首範式（weak head normal form）。該術語的使用是出于曆史原因，是以對其不必深究。該術語常被縮寫為whnf4。名詞範式在這裡是“完全求值”5的意思，在2.4節會看到如何将表達式求值使之成為範式。
弱首範式的概念在下面兩章會多次出現，是以值得去花些時間去了解這個概念，并對haskell中求值是如何發生的有所體會。對此在ghci中試驗不同的表達式和:sprint指令不失為一種很好的方法。
為了完成本例，下面對x進行求值：
`prelude data.tuple> seq x ()
此時z會是何值？
z = (_,3)`
記得變量z被定義為swap（x，x+1），即（x+1，x），前面剛對x求值了，是以z的第二個成員是已被求值的，值為3。
最後，來看一個關于清單和幾個常見清單函數的例子。對于函數map的定義，讀者或許已經知道，不過還是列在下面作為參考：
`map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs`
函數map建立了一個惰性的資料結構。若重寫map的定義而讓thunk明确，可能會更清楚一些：
map f (x:xs) = let
這和前面的map的定義是一樣的，但可以看到map傳回的清單的頭和尾各自都是thunk：f x和map f xs。也就是說，map建立了圖2-4所示的結構。
圖2-4 通過map建立的thunk
下面使用map定義一個簡單的清單結構：
<code>prelude> let xs = map (+1) [1..10] :: [int]</code>
此時xs未被求值：
`prelude> :sprint xs
xs = _`
接着對該清單求值，使之成為弱首範式：
`prelude> seq xs ()
prelude> :sprint xs
xs = _ : _`
目前為止，隻知道xs是一個至少包含一個元素的清單。接着，對該清單應用length函數：
`prelude> length xs
10`
函數length的定義如下：
`length :: [a] -> int
length [] = 0
length (_:xs) = 1 + length xs`
注意到length會忽略清單的頭，而隻對清單的尾xs進行遞歸，因而對清單應用length時，清單的結構會被展開，但元素不會被求值。這點通過:sprint可以清楚地看到：
xs = [_,_,_,_,_,_,_,_,_,_]`
ghci注意到清單已被展開，是以改用方括号顯示清單，而不再使用:。
即使通過求值的方式展開了整個清單，該清單仍不是範式（而仍然是弱首範式）。通過對清單應用一個函數，該函數需要使用清單的所有元素，就可以使之完全求值。例如sum函數：
`prelude> sum xs
65
xs = [2,3,4,5,6,7,8,9,10,11]`
前面這些讨論，對于惰性求值這個精妙而複雜的主題僅觸及了表面。幸運的是，多數情況下，編寫haskell代碼無需了解或擔心求值是何時進行的。的确，haskell語言定義十分仔細，不對如何求值作明确指定；語言的實作可以自由地選擇政策，隻需保證結果正确。這也是程式員大多數時候所關注的。但是，當編寫并行代碼時，了解表達式何時被求值變得重要起來，因為隻有這樣才能對并行化計算進行安排。
第4章使用par monad，對資料流進行明确的描述，是另一種使用惰性求值進行并行程式設計的方法。該方法犧牲了部分簡潔性進而避免了一些惰性求值相關的微妙的問題。由于會出現一種方法比另一種解決問題更自然或更高效的情況，是以兩種方法都值得學習。
__
1weak head normal form，函數式程式設計中的一種範式。——譯者注
2技術上說，這并不正确。haskell實際上是一門非嚴格（non-strict）的語言，惰性求值隻是幾種正确的實作政策之一。不過ghc使用的是惰性求值，是以這裡忽略這個技術細節。
3嚴格地說，是被一個到該值的間接引用所覆寫，不過這些細節在這裡并不重要。感興趣的讀者可以到ghc wiki上閱讀關于該實作的文檔，以及許多關于該設計的論文。
4即弱首範式英文weak head normal form的首字母縮寫。——譯者注
5即表達式裡面所有的部分、各層次均被求值，不存在未求值的部分。——譯者注