Haskell列表（時間複雜性？Haskell數據類型？） - 作業相關

我目前正在Haskell中學習CS課程，並且在理解一些材料時遇到了一些嚴重問題。Haskell列表（時間複雜性？Haskell數據類型？） - 作業相關

對於我的任務之一，我給了2個數據類型，並要求我編寫一個追加函數，它具有不變的時間追加。

我給出：

data NNList a = Sing a | Append (NNList a) (NNList a) deriving (Eq) 
data CList a = Nil | NotNil (NNList a) deriving (Eq)

，我要求寫一個函數：

CListAppend :: CList a -> CList a -> CList a

我不知道我錯過了我的CS教育，但我經常發現自己與時間和空間的複雜性相混淆，我怎麼會知道一個函數是否爲constant time？任何人都可以提供一些關於如何處理這個問題的想法嗎？

我嘗試：

CListAppend :: CList a -> CList a -> CList a 
CListAppend Nil rl = rl 
CListAppend ll Nil = ll 
CListAppend ll rl = NotNil $ Append ll rl

該報告並返回，而不是欄列表NNList的錯誤。無論如何要轉換嗎？

來源

2013-03-26 rlhh

您不希望在您的功能中執行的工作在輸入大小方面發生顯着變化。在你的情況下，你可能不希望在一個恆定時間的解決方案中使用遞歸。 – copumpkin 2013-03-26 01:54:29

提示：你必須返回一個'CList'。「CList」的構造函數是什麼？ – hammar 2013-03-26 02:11:38

@hammar，我怎樣才能在Haskell中構建一些東西？它肯定不是'CList $ Append ll rl'或類似的東西.. – rlhh 2013-03-26 02:14:56

時間複雜度是描述多少步都需要計算相對於輸入的大小答案的方式。什麼構成步驟以及如何計算大小取決於問題。

例如，如果您有一堆未排名的名片，搜索特定的名片將需要一些與卡數成正比的步驟。如果你的堆的大小加倍，你必須檢查的平均卡數也會增加一倍。另一方面，如果您預先對卡片進行了分類，則可以在每次觀看卡片時玩「高低」遊戲以減少一半的大小。現在只需加倍一堆一個尋找一個特定的卡。

這些分別是線性和對數時間複雜度的例子。在你的情況下，你需要不斷的時間複雜性。這意味着無論這兩個列表有多大，追加它們都需要相同數量的步驟。

您通常可以通過在不同輸入的紙張上演算算法來獲得想法，但有更精確的方法。下面是一個的例子使用標準[]列表實現附加功能：

append []  bs = bs 
append (a:as) bs = a : append as bs

我們會數到遞歸調用追加爲一步;或者我們可以統計(:)的調用次數。當第一個參數是空列表時，[]，沒有遞歸調用。當列表包含單個元素[1]時，我們評估1 : append [] bs，所以我們有一個遞歸調用。現在用[1,2]加倍輸入大小並計算遞歸調用。然後再加上[1,2,3,4]等。然後，您可以粗略估計步驟數是否是輸入大小中的常數，線性，對數，指數等。

來源

2013-03-26 02:41:16 kputnam

最後一個定義是錯誤的。如果ll是NotNil x和rl是NotNil y那麼你的定義應該是

CListAppend (NotNil x) (NotNil y) = NotNil (Append x y)

不過，您在CList a類型的值將追加。

此外這種解決方案是恆定的時間。追加構造函數沒有處理。模式匹配也會在不斷的時間內發生。

來源

2013-03-27 02:04:32

Haskell列表（時間複雜性？Haskell數據類型？） - 作業相關

回答

相關問題