列表 - 結合對

Question

我想打一個函數，一個列表如

[('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)] 

，再將該號碼一起當字母相同。所以上面的投入將產生

[('A',8), ('B',2), ('C',7)]. 

可能有人請你只給我如何處理這個想法，我想嘗試做盡可能多的嘍！

Answer 1

您可以使用Data.Map的fromListWith構建地圖具有彙總值。它的類型是這樣的：

fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a 

這需要對列表（如你所述）作爲第一個參數，如果它看到一個副本，它使用了一些功能（第一個參數），原始值與結合一個新的。從那裏，您可以將此映射轉換回成對列表（也是Data.Map中的一個函數）。

你可以用純列出做到這一點，但它可能不會是effecient，因爲你將構建一個新的列表（或其部分），經常。

Answer 2

好，通過下調打破了問題較小的部分開始。

首先，忽略額外的條件。最終的目標是什麼？添加一些數字，你可能已經知道如何做到這一點。

但是，你不想添加所有的數字，你怎麼知道哪些要添加？看看這些字母是否匹配。所以你需要以某種方式比較它們。

所以一旦你知道如何添加數字，並決定是否應該添加任意兩個數字，你需要一種方法來解決整個列表。你不會得到任何混合在一起的任何東西，所以你需要根據要添加的數字來分開。您可以通過創建子列表一次完成所有操作，也可以一次過濾一個或其他各種方法，其中一些可能比其他方法效率更高或更低。

這是基本的想法，反正。所以，通過這些步驟，您首先列出一個列表，然後根據比較字母分出各組項目，然後在每個結果組中添加所有數字。

我明顯跳過了幾個步驟 - 比如如何將兩個字母進行比較並將它們合併爲元組時添加數字 - 因爲您確實說過，您寧願自己想辦法。 ：]

Answer 3

有幾種方法來解決這個和亞當已經給你基於地圖的有效方式。不過，我認爲只使用列表和遞歸的解決方案也很有啓發性，特別是在學習Haskell時。既然你已經得到了答案，我希望我可以在這裏寫一個解決方案，而不會損壞任何東西。

我走近這個問題的方法是考慮我們如何才能輸入列表減少對輸出列表。我們先從

[('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)] 

的目標是每個元組有獨特字符開始用一個結果列表來結束。建設這樣一個結果列表，可以逐步完成：先建立一個空列表，然後插入元組到列表中，確保不重複的字符。類型將是

insertInResult :: (Char, Integer) -> [(Char, Integer)] -> [(Char, Integer)] 

它採用一對，像('A',3)並將其插入到唯一對現有列表。結果是唯一對的新列表。這是可以做到這樣的：

insertInResult (c, n) [] = [(c, n)] 
insertInResult (c, n) ((c', n'):results) 
    | c == c' = (c, n + n') : results 
    | otherwise = (c', n') : (insertInResult (c, n) results) 

說明：插入一個元組到一個空的結果列表很簡單，只需將其插入。如果結果列表不爲空，那麼我們可以通過模式匹配得到第一個結果(c', n')。我們檢查角色是否與警衛相匹配，如果是，則添加數字。否則，我們只複製結果元組並將(c, n)元組插入到其餘的結果中。

我們現在能做的

*Main> insertInResult ('A',3) [] 
[('A',3)] 
*Main> insertInResult ('B',2) [('A',3)] 
[('A',3),('B',2)] 

下一步是使用insertInResult反覆輸入列表中，讓我們建立一個結果列表。我稱這種功能sumPairs'，因爲我所謂的頂級功能sumPairs：

sumPairs' :: [(Char, Integer)] -> [(Char, Integer)] -> [(Char, Integer)] 
sumPairs' [] results = results 
sumPairs' (p:pairs) results = sumPairs' pairs (insertInResult p results) 

這是一個簡單的功能，只是在第一個參數進行迭代，並且插入每一對到結果列表。最後一步是調用這個輔助函數用空的結果列表：

sumPairs :: [(Char, Integer)] -> [(Char, Integer)] 
sumPairs pairs = sumPairs' pairs [] 

它的工作原理！ :-)

*Main> sumPairs [('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)] 
[('A',8),('B',2),('C',7)] 

的這種解決方案的複雜性並不像基於Data.Map的一樣好。對於n對的列表，我們從sumPairs'呼叫insertInResultn次。對insertInResult的每個調用可以迭代高達n次，直到找到匹配的結果元組或達到結果的結尾。這給出了O的時間複雜度（n²）。基於Data.Map該解決方案將具有O（Ñ日誌Ñ）時間複雜度，因爲它使用登錄Ñ時間來插入和更新每個Ñ元件。

注意，這是如果你有排序的輸入列表，你會得到再掃描一次用相同的字符添加了相鄰的元組同樣複雜：

sumPairs pairs = sumSorted (sort pairs) [] 

sumSorted [] result = result 
sumSorted (p:pairs) [] = sumSorted pairs [p] 
sumSorted ((c,n) : pairs) ((c',n') : results) 
    | c == c' = sumSorted pairs ((c,n + n') : results) 
    | otherwise = sumSorted pairs ((c,n) : (c',n') : results) 

Answer 4

除了出色的Map基於列表的解決方案，我認爲純粹的基於列表的解決方案可能非常具有啓發性。與Map一樣，有趣的是將這些元素與相同的第一元素一起分組。有聚結，即相鄰單元內置功能group（和它的廣義版本groupBy）：

groupBy :: (a -> a -> Bool) -> [a] -> [[a]] 

的第一個參數告訴何時合併兩個元素。例如：

> groupBy (\x y -> odd x == odd y) [1,1,3,4,6,5,7] 
[[1,1,3],[4,6],[5,7]] 

不幸的是，我們可以在這裏看到，它只是聚結相鄰元素，所以我們需要找到一種方法來幫了原始列表的元素首先讓那些同鍵是彼此相鄰。還有另外一個內置函數用於做這樣的事情：sort。最後的訣竅是總結大塊的第二個元素，它們都具有相同的第一個元素。讓我們寫這只是假設它是通過一個非空的塊與所有等於第一要素的功能：

sumSnds :: Num b => [(a,b)] -> (a,b) 
sumSnds abs = (a, sum bs) where 
    (a:_, bs) = unzip abs 

現在我們可以串所有這些碎片拼湊起來：

solution :: (Ord a, Ord b, Num b) => [(a,b)] -> [(a,b)] 
solution = map sumSnds . groupBy (\x y -> fst x == fst y) . sort