將元素添加到列表中

我想寫一個函數，以正確的順序將項添加到列表中，例如1，其中[2, 3]。我是haskell的新手，需要關於如何在不使用Ord的情況下提供幫助。將元素添加到列表中

2011-03-13 Louie

如何判斷列表是否以「正確的順序排列」而沒有Ord' – kennytm 2011-03-13 21:47:44

在你設定這個之前，也許你應該更清楚你想要什麼？我認爲'louie 1 [2,3]'和'louie 2 [1,3]'都應該是'[1,2,3]''。但是，例如，「louie 1 [3,2]」或「louie 2 [3,1]」或「louie 6 [5,3,17,2]」應該是什麼？ – applicative 2011-03-13 21:55:34

編寫一個將元素插入到排序列表中的函數並不難。它看起來像這樣：

insert :: Ord a => a -> [a] -> [a] 

insert x [] = [x] 

insert x (y:ys) 
    | x > y  = y : insert x ys 
    | otherwise = x : y : ys

但是，這對您的用例來說不太可能有效。列表的問題是，最終你會用這種插入問題重複創建大部分脊柱的新副本。您還必須在列表中線性掃描，直到找到正確的位置，這不是搜索正確位置的最快方法。

使用數據結構（如Data.Set或Data.IntSet中的數據結構）可能會更好。這些通常用於插入O（log n），因爲它們使用樹或其他數據結構，允許進行比列表更多的共享，並快速找到正確的位置。

來源

2011-03-13 22:04:53 chrisdb

需要說明的是，對於較大的n（列表/集合大小），O（log n）明顯優於O（n），如果您按照您的建議使用列表，則會得到該結果。 – chrisdb 2011-03-13 22:08:11

我必須返回[a]嗎？你能否詳細說明答案？ – 2017-02-22 14:11:14

沒有使用Ord，你的問題就沒有意義了。

使用ord，你想要的功能是insert

插入函數接受一個元素和列表，並插入元素到列表中的最後一個位置，它仍然是小於或等於下一個元件。

來源

2011-03-13 22:05:51

傳入的列表的順序是 – Louie 2011-03-13 22:14:32

@Louie，那麼文檔中的下一句適用：「特別是，如果列表在調用之前被排序，那麼結果也將被排序。」 – 2011-03-13 22:19:29

將元素添加到列表中

回答

相關問題