《Haskell并行與并發程式設計》——第2章，第2.4節Deepseq

本節書摘來自異步社群《haskell并行與并發程式設計》一書中的第2章，第2.4節deepseq，作者【英】simon marlow，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視

2.4　deepseq

haskell并行與并發程式設計

前面已經用過了force函數，其具體類型如下：

`

force :: nfdata a => a -> a`

函數force會對其參數完全求值，然後傳回。不過該函數并非内建，而是針對每種資料類型，通過nfdata類對該函數的行為進行定義。nfdata的意思是範式資料（normal-form data），其中範式是指不包含未被求值子表達式的值，“資料”則表示範式中不包含函數，因為無法看到函數裡面的内容并對裡面的内容求值1。

類nfdata僅包含一個方法：

class nfdata a where

rnf :: a -> ()

rnf a = a <code>seq</code> ()`

函數rnf名字的意思是“約化為範式”（reduce to normal-form）。該函數對其參數完全求值，然後傳回()。預設通過seq來實作，對于沒有子結構的類型來說很友善，隻需使用預設定義即可。例如：bool的執行個體可以簡單地定義：

<code>instance nfdata bool</code>

子產品control.deepseq對庫中所有其他的常見類型均提供了執行個體。

對于自定義的類型，可能需要實作相應的nfdata的執行個體。例如，對于二叉樹類型：

data tree a = empty | branch (tree a) a (tree a)`

那麼，其nfdata的執行個體如下：

實作的思路為遞歸地對資料類型的組成部分應用rnf，然後将這些rnf的調用通過seq組合起來。

control.deepseq子產品中還有一些其他運算，例如：

函數deepseq因其和seq的相似性而得名：和seq類似，都是強制求值。如果把弱首範式看成是淺（shallow）求值，那麼範式就是深（deep）求值，是以得名deepseq。

函數force是通過deepseq定義的：

函數force的功能應該被認為是将whnf轉換為nf（normal form），也就是，當程式将force x求值成whnf時，x會被求值成nf。

圖像說明文字将表達式求值為範式需要對整個資料結構進行周遊，是以需要銘記，對于大小為n的資料結構，其複雜度是o(n)，而對seq來說，隻有o(1)。是以，應該避免對同一資料反複使用force或deepseq函數。

whnf和nf就像天平的兩端，但是，根據資料類型的不同，還有許多處于中間的“不同程度的求值”。例如：前面的length函數對清單的脊（spine）求值，即展開了清單，但未對清單的元素求值。parallel包中的子產品control.seq提供了一系列組合子，通過組合，可以對資料結構達到不同程度的求值。本書雖然不會在例子中使用這些運算，但對讀者也許會有所幫助。

1不過，純粹為了友善，定義了一個函數的nfdata執行個體，會将函數求值為whnf（弱首範式），因為經常會有資料結構裡面包含函數，而盡管如此，還是想盡可能地對這樣的資料結構進行求值。