功能，刪除元素，如果存在但添加它不是

我正在尋找一種更乾淨的方式來編寫一個函數，如果列表中不包含它的元素添加到列表中。或者，如果列表包含它，否則將其刪除，我現在使用if子句並且該函數正在工作。功能，刪除元素，如果存在但添加它不是

但我試圖找到更多的haskell-ish的方式來對此。

這是我的代碼：

removeElemOrAdd :: Eq a => a -> [a] -> [a] 
removeElemOrAdd elem list = if (List.elem elem list) 
          then (filter(\x -> x /= elem) list) 
          else (elem:list)

來源

2015-12-03 demathieu

什麼樣的「清潔」你尋求的？關於簡潔性，您的解決方案看起來不錯。關於性能，您可以掃描一次查看，刪除和添加列表，但時間會更長。（順便說一句對稱性設計打破：你刪除所有匹配的元素，但只添加一個） – 9000

一般情況下，這看起來對我好 - 你可以我想使用的，而不是一個後衛的的if/then/else語句，但它會運行同樣的方式（遞歸），這是'haskellish'。 @ 9000通過 – Hamish

說明了這裏的對稱性，如果元素出現兩次或更多次會怎麼樣？ –

注：在你的問題一個小歧義時x已經發生多個倍，在最初的名單做什麼。我認爲這不會發生，如果是這樣，只有第一個發生被刪除。意思是removeElemOrAdd 2 [4,2,5,2,7]將導致[4,5,2,7]。此外，未指定應添加項目的位置。因爲它有一些優點，所以我選擇在列表末尾執行此操作。

，而無需使用任何文庫方法的實施方案如下：

removeElemOrAdd :: Eq a => a -> [a] -> [a] 
removeElemOrAdd x (y:ys) | x == y = ys 
         | otherwise = y : removeElemOrAdd x ys 
removeElemOrAdd x _ = [x]

或更短的版本：

removeElemOrAdd :: Eq a => a -> [a] -> [a] 
removeElemOrAdd x = reoa 
    where reoa (y:ys) | x == y = ys 
         | otherwise = y : reoa ys 
      reoa _ = [x]

或等效的實現（見下文討論）：

removeElemOrAdd :: Eq a => a -> [a] -> [a] 
removeElemOrAdd x = reoa 
    where reoa (y:ys) | x == y = ys 
         | otherwise = y : reoa ys 
      reoa [] = [x]

該函數的工作原理如下：如果我們談論的是至少有一個ite的列表m (y:ys)，我們將x與y進行比較，如果它們相等，則返回ys：在這種情況下，我們已經移除了該元素，我們完成了。

現在的情況下，這兩個不相等，我們在頭返回一個列表建設(:)與y，因爲我們需要保留y和尾部，我們會做一個遞歸調用removeElemOrAdd與x和ys。事實上：有可能尾部ys中的某個地方有x需要移除，而且如果不發生，我們還需要將x添加到列表中。

該子句將通過列表遞歸循環。從發現y的那一刻開始，x == y它將刪除那個y。然而，我們可能會到達名單的最後，並且仍然沒有找到要素。在這種情況下，我們會調用最後的條款。在這裏我們知道列表是空的（我們可以寫成removeElemOrAdd x []），但爲了使函數定義在語法上總體上，我選擇使用下劃線。如果我們未能在列表中找到x，那麼我們只能達到此狀態，因此我們通過返回[x]將其添加到列表尾部。

這種方法優於使用if-then-else的優點是它可以一次完成所有任務（檢查，刪除和添加），使其更有效。

另一個優點是可以在「無限」列表上運行（例如素數列表）。這個列表是懶惰評估的，所以如果你想取前三項，這個函數只會檢查前三項的相等性。

來源

2015-12-03 15:42:07

這裏的通配符模式感覺很奇怪，因爲它只能匹配一件事情。我的大腦一直在檢查一個警衛失敗。爲什麼不用'[]'模式替換它們？ – dfeuer

@dfeuer：它確實與'[]'等價。問題的關鍵在於，你可以說函數是*語法*總和：不必檢查函數的語義，你知道函數將陷入無限循環或給出答案，但永遠不會在下面進行模式匹配函數定義（和失敗）。 –

這個「句法」整體並不會讓我成爲有價值的東西。第一種模式的守衛包括一個'否則'條款，而列表類型只有兩個構造函數，所以在任何情況下覆蓋率都會立即顯現。如果數據類型的定義可能會發生變化（不像列表），我寧願避免通配符來打敗GHC的覆蓋檢查。正如我所提到的，在這種情況下，通配符給了我一個警衛可能會經歷的錯誤信息。 – dfeuer

我會用摺疊刪除所有副本：

removeOrAdd x xs = foldr go (bool [x] []) xs False where 
    go y r found 
    | y == x = r True 
    | otherwise = y : r found

只刪除一個，一個paramorphism似乎是爲了：

removeOrAdd x = para go [x] where 
    go y ys r 
    | y == x = ys 
    | otherwise = y : r

來源

2015-12-03 17:35:55 dfeuer

我喜歡的其他方法，但不要不喜歡它們的行爲與規範不同。因此，這裏是一個辦法是：

像原來，刪除所有副本，如果有的話，和
想當初，在開頭插入新的值，如果有必要，但
不像根據beautiful folding（以及後續開發）的想法，使用了一個巧妙的技巧來僅僅傳遞數據。

其基本思想是我們將有一個單一的值，它跟蹤到目前爲止所有值是否不匹配以及產生的過濾列表。該injectNE操作將在列表中的單個元素執行此操作，然後我們將使用foldMap擴大從一個元素，其輸入列表。

import Data.Monoid 

injectNE :: Eq a => a -> a -> (All, [a]) 
injectNE old new = (All ne, [new | ne]) where 
    ne = old /= new 

removeElemOrAdd :: Eq a => a -> [a] -> [a] 
removeElemOrAdd x xs = case foldMap (injectNE x) xs of 
    (All nex, noxs) -> [x | nex] ++ noxs

在最後的模式，你應該讀nex爲「無元素等於x」，並noxs爲「列表中沒有的x任何副本」（明白了嗎？「沒有x s」嗎？BA-達姆，TSH）。

雖然說規格寫得不錯，但具體來說，美麗摺疊的賣點之一在於其產生的單次摺疊對垃圾收集器更友好。但是這個規範很難做到這一點，因爲在決定結果列表的第一個元素應該是什麼之前，我們必須遍歷整個輸入列表。通過放寬上述（2）（但是，留下（1）和（3）），可以顯着提高垃圾收集者的友好性。而且差別僅僅是交換的參數(++)，一個很好的語義差異，看看在你的修訂歷史記錄：

-- <snipped identical code> 
removeElemOrAdd x xs = case ... of 
    ... -> noxs ++ [x | nex]

來源

2015-12-03 23:09:18

功能，刪除元素，如果存在但添加它不是

回答

相關問題