周期函數的意外內存使用

Question

在下面的程序中，我只希望cycle3使用常量內存運行（它明確地連接了結）。但是，由於我無法理解的原因，cycle2也在恆定內存中運行。我希望cycle2到做同樣的工作，爲cycle1因爲

xs' = xs ++ xs' 
xs' = xs ++ xs ++ xs' -- substitute value of xs' 
xs' = xs ++ xs ++ xs ++ xs' -- substitute value of xs' again 
xs' = xs ++ xs ++ xs ++ ... -- and so on 

---

有人能解釋什麼，我在這裏失蹤？

---

module Main where 

import System.Environment (getArgs) 

cycle1 :: [a] -> [a] 
cycle1 [] = error "empty list" 
cycle1 xs = xs ++ cycle1 xs 

cycle2 :: [a] -> [a] 
cycle2 [] = error "empty list" 
cycle2 xs = xs' where xs' = xs ++ xs' 

cycle3 :: [a] -> [a] 
cycle3 [] = error "empty list" 
cycle3 xs = let 
    xs' = go xs' xs 
    in xs' 
    where 
    go :: [a] -> [a] -> [a] 
    go start [last] = last : start 
    go start (x:xs) = x : go start xs 

testMem :: (Show a) => ([a] -> [a]) -> [a] -> IO() 
testMem f xs = print (xs', xs') -- prints only first val, need second val holds onto reference 
    where 
    xs' = f xs 

main :: IO() 
main = do 
    args <- getArgs 
    let mCycleFunc = case args of 
     ["1"] -> Just cycle1 
     ["2"] -> Just cycle2 
     ["3"] -> Just cycle3 
     _ -> Nothing 
    case mCycleFunc of 
    Just cycleFunc -> testMem cycleFunc [0..8] 
    Nothing -> putStrLn "Valid args are one of {1, 2, 3}." 

Answer 1

歸結爲共享或不共享相等的thunk。兩個相等的thunk是thunk，保證產生相同的結果。在cycle1的情況下，每當您在xs的末尾點擊[]時，就會爲cycle1 xs創建一個新的thunk。需要爲該thunk分配新內存，並且其值需要從頭開始計算，在您經歷它時分配新的列表對。

我的思維方式cycle2避免了這個變得更容易，如果您重命名xs'到result瞭解（和我刪除了「錯誤的[]」的情況下）：

cycle2 :: [a] -> [a] 
cycle2 xs = result 
    where result = xs ++ result 

這個定義是語義上等同於cycle1（生產對於相同的參數，結果相同），但理解內存使用情況的關鍵是從Thunk創建的角度來看待它。當您執行此函數的編譯代碼時，它立即執行的是爲result創建一個thunk。你能想到形實轉換爲一個可變類型的更多或更少的這樣的（總虛構的僞代碼）：

type Thunk a = union { NotDone (ThunkData a), Done a } 
type ThunkData a = struct { force :: t0 -> ... -> tn -> a 
          , subthunk0 :: t0 
          , ... 
          , subthunkn :: tn } 

這可能是包含指向所述的thunk爲所需要的值加上一個指向代碼的記錄強制這些thunk，或只是計算的結果。在cycle2的情況下，result的thunk指向(++)的目標代碼，xs和result的thunk。最後一位表示result的thunk有一個指向自身的指針，這說明了恆定的空間行爲;強制result的最後一步是讓它指向自己。

在cycle1的情況下，另一方面在thunk具有用於(++)代碼，用於xs一個thunk和新形實轉換從頭計算cycle1 xs。原則上，編譯器可以認識到對後一個thunk的引用可以用「父」塊代替，但編譯器不會這樣做;而在cycle2它不能做到這一點（一個實例化一個變量綁定=一個塊）。

注意，這種自我指涉的thunk的行爲可以被分解成一個合適的實現的fix：

-- | Find the least fixed point of @f@. This implementation should produce 
-- self-referential thunks, and thus run in constant space. 
fix :: (a -> a) -> a 
fix f = result 
    where result = f result 

cycle4 :: [a] -> [a] 
cycle4 xs = fix (xs++) 

Answer 2

cycle1創建一個新的列表中的每一個週期中被消耗的時間。這應該是明顯的原因。

cycle2但是，不這樣做。它創建一個變量xs'，它在自己的定義中使用。在cycle1它不得不重新評估cycle1函數每次您消耗xs，但在cycle2它沒有任何遞歸函數。它只是引用相同的變量，它已經有一個已知的值。