Haskell：將（a，b）鍵值對（可能重複的鍵）列表轉換爲按鍵分組的列表（a，[b]）

Question

我是一名Haskell初學者。假設我想編寫一個函數convertKVList，該函數使用一系列鍵值對，其中一些鍵可能會重複，並將其轉換爲從鍵到值列表的映射，其中所有鍵都是唯一的。例如，對Int s的名單上，我想這種行爲：

> convertKVList [(1, 2), (1, 4), (1, 3), (2, 3)] 
[(1,[3,4,2]),(2,[3])] 

這似乎是一個足夠常見的任務，就必須有可用的做我想做的庫函數，但我不能」當我看時，我找不到任何東西。最後，有人建議我撰寫Map.toList與Map.fromListWith (++)，我結束了與此：

import Data.Map as Map (toList, fromListWith) 

convertKVList :: (Ord a) => [(a, b)] -> [(a, [b])] 
convertKVList ls = 
    (Map.toList . Map.fromListWith (++) . map (\(x,y) -> (x,[y]))) ls 

我的問題是更有經驗的Haskellers並分爲兩個部分：首先，這是你將如何去了解它，或有沒有「更好」（更容易閱讀，或更有效率，或兩者兼而有之）？

其次，我怎麼能自己想出這個呢？我知道我想要的類型是[(a, b)] -> [(a, [b])]，但將它放入Hoogle中並沒有提供任何有用的信息。我曾看過Data.Map文檔，但fromListWith和toList都沒有跳出來，因此特別有用。那麼，你將如何去思考這個問題呢？ （我意識到這兩個問題都是主觀的，尤其是第二個問題。）

謝謝！

Answer 1

編寫函數時最重要的一點是試圖將它應該做的事分解成單獨的子任務（最終通常由函數組合構成）。例如，在定義你來了，有三個任務（在應用程序的順序，即從右側的定義至左）：

1. 每一對的第二個組件映射到一個單列表（從而能夠使用的Map.fromListWith）
2. 創建地圖（需要合併同鍵條目）
3. 把它變成一個列表

我想後不同的解決方案（這是一個精確副本的護理在此期間發佈的代碼Mark）;））。只是爲了清楚表明大部分時間有不同的路線來實現同一個目標。在他的定義，你有不同的任務：

1. 排序列表中通過按鍵
2. 組的結果通過按鍵
3. 把它變成了所需類型的列表中再次

一次，分離關注（模塊化）是一個重要的原則。試着將它應用於小問題，一旦你獲得了一些經驗，你將能夠爲看似困難的問題提出令人驚訝的簡單解決方案。

Answer 2

而這絕不是指規範：

import Data.List 
import Data.Ord 
import Data.Function (on) 

convertKVList :: Ord a => [(a,b)] -> [(a,[b])] 
convertKVList = map (\x -> (fst $ head x, map snd x)) . groupBy ((==) `on` fst) . sortBy (comparing fst) 

它確實有Data.Map不拉的優勢。應該是漸近相同的，沒有基準。我認爲你可以用Control.Arrow清理第一個塊（類似於（fst。head & & & map snd）），但它並不明顯更清潔。

不知道你是如何找到它的，除非知道它或者在#haskell中詢問。

Answer 3

所以，我的解決方案過度使用模式匹配，因爲我實際上並不知道標準庫中有哪些函數。

想法是，如果列表按鍵排序，那麼您可以隨時收集鍵值。爲了執行檢查是否添加到第一個鍵值列表或創建新條目的邏輯，我使用模式和警衛來定義條件。自由利用利弊將價值列入清單。

而如果原來的列表是沒有排序，有一個sortBy。

import Data.List 
import Data.Ord 

ls = [(2, 1), (1, 2), (1, 4), (1, 3), (2, 3)] 

addval [] (k, v)= [(k, [v])] 
addval ((k1, vals) : xs) (k2, v) | k1 == k2 
    = ((k1, (v : vals)) : xs) 
addval ls (k, v) = ((k, [v]) : ls) 

convert ls = foldl addval [] (sortBy (comparing fst) ls) 

醜陋的代碼，但它避免使用地圖。

Answer 4

Hoogle無法通過類型簽名搜索哈斯克爾圖書館唯一的搜索引擎，它肯定，不幸的是只覆蓋Hackage的一小部分。與Hayoo尋找一個類型簽名[(a,b)]->[(a,[b])]長大的這兩種實現方式：

• aggregateAL
• alistCollect

關於你對這個問題，因爲在你的功能，你已經帶來了一個更高的層次數據結構（Map），它沒有任何意義降級到輸出更原始的關聯列表，因爲：

1. 大部分的算法，你都不可能利用這些數據將只得到一個Map輸入中受益，因爲它是更有效的處理鍵值存儲，如果你發現自己仍然需要一個列表，你可以隨時使用toList就位。
2. Map意味着對類型級別沒有重複鍵，這是沒有任何不那麼重要，因爲在Haskell，你總是應該使用類型系統的最大證據。這個原則實質上是使得「如果它編譯，它的工作」最接近真實的說法。

換句話說，這是你的函數的正確定義：

convertKVList :: (Ord a) => [(a, b)] -> Map a [b] 
convertKVList ls = 
    Map.fromListWith (++) . map (\(x,y) -> (x,[y])) $ ls 

Hayooing該類型簽名帶來了幾個已經實施結果了。

關於接近的問題，它的經典之作："Divide and conquer!"。克里斯在他的回答中也有一些優點。

Answer 5

這看起來像一個可以理解的解決方案，你可以清理它稍微：

 
import Data.Map (toList, fromListWith) 
import Control.Arrow (second) 

convertKVList :: Ord a => [(a, b)] -> [(a, [b])] 
convertKVList = toList . fromListWith (++) . map (second (:[])) 

至於你怎麼可能想出這個你自己：假設你開始Data.Map，那麼你要使用的映射以將值與相等的鍵相結合。關於Hackage的Data.Map的文檔說a是鍵值類型，k是鍵值。

知道了這一點，您可以搜索a -> a -> a以查找可能組合Map k a中的兩個值以產生新的a值的函數。這將API縮小爲幾個函數，如insertWith,fromListWith和fromAscListWith。

同樣，轉換您的Map k a到[(k, a)]，您可以搜索文檔Map k a -> [(k, a)]和發現只有少數功能，如assocs，toList，toAscList和toDescList。請注意，在你的情況下，[(k, a)]被實例化爲[(Int, [Int])]。

我發現有一點對於理解標準Haskell庫很有幫助，可以在Hackage上查看源代碼。看到哪些功能是以其他方式實現的有助於使API變得更小，並且我可以看到哪些功能是基本構建塊。

Answer 6

我懷疑，如果沒有浸入突變和ST monad，您不可能在Map.fromListWith解決方案（或基本相當的替代方案，如使用HashMap.fromListWith）方面得到改進。我只想跟那個一起去。

基本上，突變可以通過使用一個可變的哈希表a作爲鍵和b的值可變名單做分組在接近線性的時間。然而，如果沒有突變，它會變得更糟，因爲每個插入到一個平衡的搜索樹中都是O（log n）;這是因爲「插入」意味着構建每個樹節點的新副本，這會導致插入的元素進入到該元素中。並且您需要執行n次插入 - 這正確地爲您提供了O（n * log n）範圍，即Map.fromListWith功能有。提前對關聯列表進行排序並不能從根本上改善這一點，因爲排序也是O（n * log n）。

因此，要改進O（n * log n），您需要具有突變的數據結構。我只是做了一個快速Google，最好的選擇是使用類似hashtables庫（我從來沒有嘗試過，所以我不能擔保它）實施標準的命令式算法。要使用這個，你需要了解Control.Monad.ST和Data.STRef。該單子是GHC提供的在純函數中「內部」使用突變的技術 - 它使用某些類型的系統擴展來保證副作用不能在有問題的函數之外被觀察到。 HaskellWiki has some examples，但這可能需要一些學習和練習來感覺舒服。

我會建議，如果你覺得你想了解Data.Map或類似的庫更好的另一件事，是看克里斯·奧卡薩基的純功能性數據結構書（或his dissertation (PDF) that the book is based on）。它基於Standard ML而不是Haskell，數據結構不盡相同，可能有點困難，但它是一本基礎性的書。