名單懶惰評估在Haskell

我做了以下簡單的假設，以瞭解在Haskell名單懶惰的評價，名單懶惰評估在Haskell

head [1, 2]    -- expr1 
head [1 .. 2]    -- expr2 
head [1 ..]    -- expr3 

head . (1 :) $ []   -- eval1 
head . (1 :) . (2 :) $ [] -- eval2

我想這expr3想eval1懶洋洋地評估，如何expr1和expr2？

一般來說，

是懶惰的評價在Haskell在編譯和運行時間的技術？
它在哪裏說效率好，但很難推理，按時，空間複雜性或程序邏輯？

來源

2015-04-02 sof

我不明白你的要求。看起來你試圖推理表達式的評估，但我不知道你在說什麼。在Google上學習更多的關鍵字是「WHNF」。 – kirelagin 2015-04-02 22:36:23

如果有人試圖直接回答你的問題，那麼答案就是：「你的例子中沒有寫出任何表達式。 – kirelagin 2015-04-02 22:38:50

你的意思是'head [1,2]'直接編譯爲'1'嗎？ – sof 2015-04-02 22:47:33

列表沒有什麼特別之處。它們僅僅是遞歸的數據類型：

data [a] = a : [a] | []

現在，當您使用[1 .. 2]，就是不變成了一個列表(1:(2:[]))直接!,它被存儲爲表達[1 .. 2]。

現在head被定義爲：

head :: [a] -> a 
head (x:_) = x

如果你打電話head [1 .. 2]，爲main（因此Haskell是莫名其妙地被迫對其進行評估），它會看到[1 .. 2]不是一個數據結構，而是一個懸而未決的表達，這將解決表達了一下：

[1 .. 2] to (1:[(succ 1) .. 2])

就這樣，現在一曰：

head (1:[(succ 1) .. 2])

（注意，尾巴仍然是一個表情），但由於head只對感興趣，所以 - 「頭」它將返回1。請注意，如果head是例如1+2，則它不會立即評估爲3。

此外，如果你簡單地調用head [1 .. 2]表達將不會自動評估，如果你想爲實例，以顯示結果，哈斯克爾將盡努力來計算它，它僅僅是。

根據編譯器的實現情況，編譯器可以在編譯時盡力傳播常量（文字）並對它們執行操作，但由於編譯器應始終遵循執行標準，因此語義保持不變。

來源

2015-04-02 23:23:53

我應該更好地陳述一些我在'GHCi'中鍵入'head ..'表達式或者從'main = do print $ head ...'抽象它們以避免混淆。 – sof 2015-04-02 23:46:40

在ghci中，它會 - 或多或少 - 在前面放置一個隱式'print $'，從而評估它，直到它可以打印結果。 – 2015-04-02 23:52:11

術語「懶惰評估」以多種方式使用。

懶惰評價是一種語義;它說什麼表達式評估哪些值。（我承認雖然有一些細節從語義中遺漏了！）
懶惰評估是一種實施策略;它提供了一種「運行」符合上述語義的lambda演算術語的方法，並使用共享來改進更明顯的「按名稱」實現策略的時間和內存使用情況。
我想，你還以第三種方式使用它。

在餘下的部分中，我將對實現策略使用「懶惰評估」，對於語義使用「非嚴格語義」。

我想這expr3想eval1懶洋洋地評估，如何expr1和expr2？

一個非嚴格的語義規定所有五個術語的評估應該終止併產生值1，因此任何符合實現將以這種方式表現。懶惰評估將在每個表達式的大約相同的空間和時間內完成。我希望如果你強迫這五個術語中的任何一個，GHC會選擇懶惰評估，儘管優化它可能會在編譯時進行評估。如果您非常感興趣，您可以通過傳遞-ddump-simpl標誌來自己檢查。

Haskell中的懶惰評估技術在編譯和運行時間？

希望上面的討論已經澄清了這個問題。非嚴格語義描述了編譯時和運行時之間的特定連接（即，編譯器必須生成一個程序，其運行時行爲會產生語義指定的值）。懶惰評估是生成符合語義的程序的特定實現策略。 GHC有時在其計劃中使用懶惰評估，但有時使用其他實施策略;但是，它符合非嚴格的語義。（如果你找到一個不存在的地方，這是一個錯誤！）

它說什麼對效率有好處，但很難推論，按時，空間複雜性或程序邏輯？

非嚴格的語義通常不會說在計算過程中使用了多少時間或空間，所以如果您想對此進行推理，則需要完全不同的技術。即使你決定將你的推理限制在用懶惰評估實現的程序中，事情也很難。考慮像[1..]這樣的表達：它使用多少空間？這個問題不能在真空中回答;懶惰評估的基本思想是讓消費者對價值構建的價值進行控制。因此，沒有看到的做與表達[1..]程序，我們無法知道了。它可能會將價值拋開，在這種情況下幾乎不會使用空間;或者它可能沿着列表走下去，在這種情況下使用恆定的空間量;或者它可能在不同的時間遍歷列表兩次，在這種情況下使用無限空間;或者可能會用其他空間要求來做其他事情。

來源

2015-04-02 23:42:13

感謝您的詳細解答。我想知道是否可以找到Haskell的詞彙，包括學術術語和相關的行業術語。 – sof 2015-04-03 00:22:37

@sof根據您的興趣，您可能會喜歡「功能語言的實現」，「Spineless Tagless G-Machine」或「類型和編程語言」。當然，也有Haskell wiki，它具有較低的深度，嚴格性和方向性，但也立即可用且相當平易近人。 – 2015-04-03 03:00:03

要完成其他的答案，你可以在ghci中與:sprint命令檢查有懶評價工作：

Prelude> let xs = [1..10] :: [Int] 
Prelude> :sprint xs 
xs = _ 
Prelude> head xs 
1 
Prelude> :sprint xs 
xs = 1 : _ 
Prelude> take 3 xs 
[1,2,3] 
Prelude> :sprint xs 
xs = 1 : 2 : 3 : _ 
Prelude> length xs 
10 
Prelude> :sprint xs 
xs = [1,2,3,4,5,6,7,8,9,10]

來源

2015-04-03 12:14:59 Eric

名單懶惰評估在Haskell

回答

相關問題