首頁猿問什么是弱頭正常形式？

什么是弱頭正常形式？

源碼算法與數(shù)據(jù)結(jié)構(gòu)

波斯汪 2019-07-25 15:03:52

什么是弱頭正常形式？什么是弱頭范式（WHNF）是什么意思？什么是頭標(biāo)準(zhǔn)型（HNF）和范式（NF）是什么意思？真實(shí)世界Haskell說：熟悉的seq函數(shù)將表達(dá)式計(jì)算為我們稱之為head normal form（縮寫為HNF）的表達(dá)式。它一旦到達(dá)最外面的構(gòu)造函數(shù)（“頭部”）就會(huì)停止。這與正常形式（NF）不同，其中表達(dá)式被完全評(píng)估。您還將聽到Haskell程序員引用弱頭正常形式（WHNF）。對(duì)于正常數(shù)據(jù)，弱頭正常形式與頭部正常形式相同。差異只出現(xiàn)在功能上，而且我們?cè)谶@里無關(guān)緊要。我已經(jīng)閱讀了一些資源和定義（Haskell Wiki和Haskell郵件列表和自由詞典），但我沒有得到它。有人可能舉一個(gè)例子或提供外行定義嗎？我猜它會(huì)類似于：WHNF = thunk : thunk HNF = 0 : thunk NF = 0 : 1 : 2 : 3 : []如何做seq和($!)與WHNF和HNF有關(guān)？更新我還是很困惑。我知道有些答案會(huì)忽略HNF。通過閱讀各種定義，似乎WHNF和HNF中的常規(guī)數(shù)據(jù)之間沒有區(qū)別。但是，它似乎與功能有所區(qū)別。如果沒有差異，為什么還seq需要foldl'？另一個(gè)混淆點(diǎn)來自Haskell Wiki，它指出seq減少到WHNF，并且對(duì)以下示例不做任何處理。然后他們說他們必須seq用來強(qiáng)制評(píng)估。那不是強(qiáng)迫它到HNF嗎？常見的新手堆棧溢出代碼：myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)了解seq和弱頭正常形式（whnf）的人可以立即理解這里出了什么問題。（acc + x，len + 1）已經(jīng)在whnf中，所以seq將值減少到whnf，對(duì)此無效。這段代碼將像原始的foldl示例一樣構(gòu)建thunks，它們只是在元組內(nèi)部。解決方案只是強(qiáng)制元組的組件，例如myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)- Stackoverflow上的Haskell Wiki

查看完整描述

3 回答

狐的傳說

TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超3個(gè)贊

Haskell中關(guān)于Thunks和Weak Head Normal Form的部分Wikibooks 對(duì)懶惰的描述提供了對(duì)WHNF的非常好的描述以及這個(gè)有用的描述：

逐步評(píng)估值（4，[1,2]）。第一階段完全沒有評(píng)估; 所有后續(xù)表格都在WHNF中，最后一個(gè)表格也是正常形式。

反對(duì) 回復(fù) 2019-07-25

米脂

TA貢獻(xiàn)1836條經(jīng)驗(yàn) 獲得超3個(gè)贊

Haskell程序是表達(dá)式，它們通過執(zhí)行評(píng)估來運(yùn)行。

要評(píng)估表達(dá)式，請(qǐng)按其定義替換所有函數(shù)應(yīng)用程序。你這樣做的順序并不重要，但它仍然很重要：從最外面的應(yīng)用程序開始，從左到右進(jìn)行; 這稱為懶惰評(píng)估。

例：

   take 1 (1:2:3:[])=> { apply take }
   1 : take (1-1) (2:3:[])=> { apply (-)  }
   1 : take 0 (2:3:[])=> { apply take }
   1 : []

當(dāng)沒有更多功能應(yīng)用程序需要更換時(shí)，評(píng)估停止。結(jié)果是正常形式（或縮小的正常形式，RNF）。無論您評(píng)估表達(dá)式的順序如何，您總是會(huì)以相同的正常形式結(jié)束（但僅在評(píng)估終止時(shí)）。

懶惰評(píng)估的描述略有不同。也就是說，它表示你應(yīng)該只評(píng)估所有的弱頭正常形式。在WHNF中，表達(dá)式恰好有三種情況：

構(gòu)造函數(shù)： constructor expression_1 expression_2 ...
一個(gè)內(nèi)置函數(shù)，參數(shù)太少，比如(+) 2或sqrt
lambda表達(dá)式： \x -> expression

換句話說，表達(dá)式的頭部（即最外面的函數(shù)應(yīng)用程序）不能再進(jìn)一步求值，但函數(shù)參數(shù)可能包含未評(píng)估的表達(dá)式。

WHNF的例子：

3 : take 2 [2,3,4]   -- outermost function is a constructor (:)(3+1) : [4..]        -- ditto\x -> 4+5            -- lambda expression

筆記

WHNF中的“頭”不是指列表的頭部，而是指最外層的函數(shù)應(yīng)用程序。
有時(shí)候，人們會(huì)將未評(píng)價(jià)的表達(dá)稱為“thunk”，但我認(rèn)為這不是理解它的好方法。
頭部正規(guī)形式（HNF）與Haskell無關(guān)。它與WHNF的不同之處在于，lambda表達(dá)式的實(shí)體也在某種程度上得到了評(píng)估。

反對(duì) 回復(fù) 2019-07-25