瞭解遞歸惰性列表

我試圖獲得舒適與來自Haskell wiki下面的代碼片段：瞭解遞歸惰性列表

primesPE = 2 : oddprimes 
    where 
    oddprimes = sieve [3,5..] 9 oddprimes 
    sieve (x:xs) q [email protected] ~(p:t) 
     | x < q  = x : sieve xs q ps 
     | otherwise =  sieve (xs `minus` [q, q+2*p..]) (head t^2) t 

minus (x:xs) (y:ys) = case (compare x y) of 
    LT -> x : minus xs (y:ys) 
    EQ -> minus xs ys 
    GT -> minus (x:xs) ys 
minus xs _ = xs

我就要絆倒了對oddprimes遞歸定義和minus上無限列出了使用一個遞歸的函數。

我想部分我很困惑，因爲我不明白Haskell編譯器如何執行此代碼。它如何不會耗盡內存？我懷疑答案是<magic> lazy evaluation </magic>，但我認爲我需要更堅定地掌握如何在實踐中評估這一點，以便感覺舒適。

來源

2015-12-29 Chris

[此程序員在堆棧交換站點中的線程]（http://programmers.stackexchange.com/questions/304019/how-does-repeat-x-xrepeat-x-return-a-list-in-haskell/ ）可能會有所幫助。 –

在幕後，Haskell系統通常用一種稱爲thunk的結構來表示內存中的值。一個thunk看作一個對象，該對象具有兩種狀態：

Uncomputed
已計算

一種uncomputed形實轉換包含一個指向其計算其結果的目標代碼子例程，和一個指針thunk提供執行該計算所需的值。（如果您遇到closures的概念，則未計算的thunk就是關閉。）

計算的thunk僅包含原始結果值。在thunk上的基本操作被稱爲強迫。當你強制一個未計算的thunk時，它的子程序被捕獲的參數調用，thunk被替換爲計算結果值（從而將其狀態轉換爲計算值），並返回該值。當你強制一個已經計算的thunk時，你只需要獲得已經計算的值。

如果我們用僞代碼編寫，也許這樣更容易。我會做一些Java的ISH：

class Thunk<A> { 
    private final Supplier<A> computation; 
    private boolean computed = false; 
    private A result; 

    Thunk(Supplier<A> computation) { 
     this.computation = computation; 
    } 

    public A force() { 
     if (!computed) { 
      result = computation.get(); 
      computed = true; 
     } 
     return result; 
    } 
}

這不正好就是上面描述我的東西，但它確實表現得像它。

現在，讓我們來看一個簡單的例子，即構建一個元素的重複列表的功能：

repeat :: a -> [a] 
repeat a = a : repeat a

的repeat功能被編譯成目標代碼程序，在僞代碼，可能看起來是這樣的：

Thunk<List<A>> repeat(Thunk<A> a) { 
    return new Thunk<A>(() -> new Cons<A>(a, repeat(a))); 
} 

class Cons<A> extends List<A> { 
    Thunk<A> head; 
    Thunk<List<A>> tail; 
    // ... 
}

如果您不熟悉與Java 8，() -> new Cons<A>(a, repeat(a))是一個lambda。這是一個函數，它接受零參數，並在被調用時構造一對。遞歸調用repeat在內部爲，因此調用repeat不會遞歸 - 它返回一個Thunk，它捕獲lambda，而不立即執行它。當該thunk爲force d時，只有然後將調用lambda，這將調用repeat，這將返回另一個類似的thunk馬上。

基本上，在Haskell中，代碼被編譯爲一個優化的低級版本。

來源

2015-12-29 21:34:55

我喜歡從外部重寫術語來考慮懶惰評估。你知道如何簡潔地將這些觀點聯繫起來嗎？ – dfeuer

@dfeuer你可以這樣說：懶惰評估提供了評估haskell表達式的指稱語義。帶有thunk的GHC運行時系統的設計爲這種指稱語義提供了一種可能的解釋（有時稱爲*銳化*）作爲操作語義。 –

@ReinHenrichs，我想這可能是公平的說，術語重寫給出了指稱語義（按名稱調用），圖形重寫給出了操作語義（按需調用）。但是，通過在紙上書寫條款，並用繪製的箭頭替換變量引用，似乎很容易從一個到另一個。我從來沒有真正看過這是如何形式化的。 – dfeuer

答案的確是簡單的懶惰評估。 Haskell不評估任何內容，甚至不評估列表的尾部，除非它明確標記爲嚴格，或者IO操作需要它（甚至IO操作本身可能是懶惰的，有時令人困惑）

所以，如果你評價像

head (1 : undefined)

您將獲得1，即使是在有一個未定義的，因爲列表的尾部不會求。

來源

2015-12-29 16:10:12 YuriAlbuquerque

瞭解遞歸惰性列表

回答

相關問題