Haskell列表的複雜性

對不起，如果這個問題已經被問到，我沒有找到它。對於我可憐的英語感到抱歉。Haskell列表的複雜性

我在學習Haskell並嘗試使用列表。我寫了一個函數，它轉換一個特定模式後的列表，我不能檢查它現在是否有效，但我認爲是。

此功能是不是尾調用函數，所以我認爲這將是可怕的計算這個功能有一個大名單：

transform :: [Int] -> [Int] 
transform list = case list of 
    (1:0:1:[]) -> [1,1,1,1] 
    (1:1:[]) -> [1,0,1] 
    [1]   -> [1,1] 
    (1:0:1:0:s) -> 1:1:1:1: (transform s) 
    (1:1:0:s) -> 1:0:1: (transform s) 
    (1:0:s)  -> 1:1: (transform s) 
    (0:s)  -> 0: (transform s)

所以我想到了另一種功能，這將是「好」：

transform = reverse . aux [] 
    where 
    aux buff (1:0:[1]) = (1:1:1:1:buff) 
    aux buff (1:[1])  = (1:0:1:buff) 
    aux buff [1]   = (1:1:buff) 
    aux buff (1:0:1:0:s) = aux (1:1:1:1:buff) s 
    aux buff (1:1:0:s) = aux (1:0:1:buff) s 
    aux buff (1:0:s)  = aux (1:1:buff) s 
    aux buff (0:s)  = aux (0:buff) s

問題是我不知道它是如何編譯的，如果我錯了第二個函數。你能向我解釋清單是如何工作的嗎？最後使用（++）還是反轉列表更好？

預先感謝您爲您的回答

來源

2014-02-27 Shumush

另請參閱http://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons; HTTP：//計算器。COM /問題/ 13042353 /的確，哈斯克爾具備尾遞歸優化。 –

第一個功能是完全正常的，並最好到第二個我的意見。

原因是懶惰。如果代碼中有transform someList表達式，除非您要求，否則結果列表將不會被評估。特別是，根據需要，列表將僅評估至; print $ take 10 $ transform xs將比print $ take 20 $ transform xs做更少的工作。

用嚴格的語言transform確實會阻礙堆棧，因爲它必須在返回任何使用之前評估整個列表（以非尾遞歸方式）。在Haskell transform (0:xs)評估爲0 : transform xs，一個可用的部分結果。我們可以檢查這個結果的頭部而不接觸尾部。沒有堆棧溢出的危險：任何時候最多隻有一個未評估的thunk（如前例中的transform xs）在列表尾部。如果你需要更多的元素，thunk會被推回更遠，並且前一個thunk的堆棧幀可以被垃圾收集。

如果我們總是對列表進行全面評估，那麼這兩個函數的性能應該是相似的，或者即使如此，由於缺少反轉或額外的-s，懶惰版本可能會稍快一些。所以，通過切換到第二個功能，我們失去了懶惰，並沒有獲得額外的性能。

來源

2014-02-27 17:09:00

非常感謝您的回答，我明白我現在在做什麼，所以我必須更經常地指望懶惰。我習慣嚴格限制語言。 – Shumush

你的第一個版本看起來好多了。這很好，它不是尾遞歸的：你不希望它是尾遞歸的，你希望它是懶惰的。第二個版本在不處理整個輸入列表的情況下不能生成單個元素，因爲爲了reverseaux的結果，必須知道整個aux。然而，

take 10 . transform $ cycle [1,0,0,1,1,1]

會很好地工作的transform你的第一個定義，因爲你只爲你才能做出決定需要消耗盡可能多的名單。

但請注意(1:0:1:[])只是[1,0,1]。

來源

2014-02-27 17:44:41 amalloy

謝謝，我認爲，將[1,0,1]與模式匹配匹配是行不通的，但它只是一個值，所以當然這是可行的。 – Shumush

Haskell列表的複雜性

回答

相關問題