Haskell的「尾巴」功能有什麼時間複雜性？

Question

當我想到自己時，我正在閱讀關於Haskell的教程; Haskell的tail函數具有何種時間複雜性（以及爲什麼）？（我找不到任何文檔中的答案）

我猜想，對於大小爲n的列表中，tail功能將爲O（n），即只複製過的尾巴到一個新的列表，並返回那個。但是，再次，我不太瞭解Haskell的底層架構（我是這個語言的新手）。

當然，我可以計時。但是我不知道如何在Haskell中實現一些東西，而且我也想了解Haskell如何處理這個問題，以證明爲什麼它是O（n）/ O（1）或其他。

感謝提前:)

Answer 1

Haskell語言沒有指定。但是在GHC（最常用的實現）中，它是O（1）。尾部不需要複製 - 在原始列表和僅使用列表尾部的人之間共享是安全的 - 因爲Haskell中的所有內容都是不可變的。

挑戰問題：爲什麼init，除了最後列表的元素，運行在O（n）？爲什麼上面的分享論點不適用？

Answer 2

簡短的回答：如果列表已經構建到那個節點，O（1）。

Haskell中的列表是鏈表。它被定義爲：

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

因此，這意味着，要麼我們的空單，或a : [a]結構。所以節點帶有head（a），其引用a類型的對象，tail引用列表[a]（可以是空列表或其他節點）。

在base的tail的源代碼被定義爲：

tail     :: [a] -> [a] 
tail (_:xs)    = xs 
tail []     = errorEmptyList "tail" 

它運行在O（1），因爲我們只需按照指針那個節點的「尾巴」。

但是請注意，Haskell懶洋洋地工作。這不是因爲我們得到了一個類型爲[a]的對象，我們有一個物化列表：通常Haskell首先必須評估表達式樹它已放棄給定節點。這可能導致評估複雜和耗時的算法。所以它取決於你給出的表達樹。