Haskell從列表中刪除重複項

我是Haskell的新手，我試着從下面的代碼中刪除列表中的重複項。但它似乎並不奏效。Haskell從列表中刪除重複項

compress []  = [] 
compress (x:xs) = x : (compress $ dropWhile (== x) xs)

我試過了一些搜索，所有的建議都使用foldr/map.head。有基本結構的實現嗎？

2015-06-30 Gaara

提示：你有完全正確的想法，除了'dropWhile'是錯誤的功能。 'dropWhile'刪除列表中的每個元素*直到它碰到一個'== x';你需要的東西，而不是像這樣刪除每個元素。 –

關於這個問題有一個很好的討論[這裏]（http://stackoverflow.com/questions/16108714/haskell-removing-duplicates-from-a-list）。 –

請注意，從'Data.List'模塊中有一個內置命名'nub'。 – Sibi

我認爲你在代碼中提到的問題是你當前的實現只會擺脫相鄰的重複。當它發佈在評論中時，內置函數nub將消除每個重複，即使它不相鄰，也只保留任何元素的第一次出現。但是既然你問過如何用基本的構造來實現這樣一個功能，那麼這個怎麼樣呢？

myNub :: (Eq a) => [a] -> [a] 
myNub (x:xs) = x : myNub (filter (/= x) xs) 
myNub [] = []

，我介紹給你有過濾，其過濾基於謂詞（名單在這種情況下，該列表中匹配的其餘擺脫每一個元素目前唯一的新功能當前元素）。

我希望這會有所幫助。

2015-07-01 01:13:30 fgv

foldr and map是非常基本的FP構建體。然而，它們非常普遍，我發現它們有一段時間瞭解它的想法。 Tony Morris' talk Explain List Folds to Yourself幫了我很多。

在你的情況下，現有的列表功能像過濾::（一 - >布爾） - > [A] - > [A]與exludes您的重複可以代替dropWhile使用的謂語。

2015-06-30 23:58:41

大多數Haskell實現（當然是GHC）包含的** base **庫包含有效設置數據結構，這些數據結構在您添加到它們時執行此操作。結合** Data.Set.fromList **和** Data.Set.toList **可以讓你做到這一點，但我不認爲圖書館在這裏使用你的意圖。 –

但是，將列表轉換爲集合將對元素進行排序並需要Ord約束。 Nub只需要一個Eq約束並保留排序。當然，設置選項在O（n log n）和O（n^2）更有效。在這種情況下，重新排序和/或附加限制可能不是期望的。 – fgv

@fgv你對我的回答有什麼看法？我保留Set的建議作爲評論，因爲它似乎並不符合OP的意圖。 –

首先，從來沒有簡單地陳述「不起作用」的問題。這留給讀者檢查它是編譯時錯誤，運行時錯誤還是錯誤的結果。

在這種情況下，我猜測這是一個錯誤的結果，這樣的：

> compress [1,1,2,2,3,3,1] 
[1,2,3,1]

與您的代碼的問題是，它消除連續重複，只。第一對1被壓縮，但最後的唯一1並未因此而被刪除。

如果可以，請提前對列表進行排序。這將使相同的元素關閉，然後compress做適當的工作。當然，輸出的順序是不同的。如果需要，還可以保留訂單（從zip [0..] xs開始，然後進行排序，然後...）。

如果你不能排序因爲沒有實際的方法來定義比較，但只有一個平等，然後使用nub。請注意，這比分類壓縮的效率低得多。這種性能損失是內在的：沒有比較器，只能使用低效的二次算法。

2015-07-01 08:27:06 chi

OP的問題是關於實現nub，而不是在庫中找到它。對這些問題的討論很有趣，但沒有解決OP或摺疊和地圖混淆的問題。 –

回答