Haskell的：摺疊的地圖，同時更新的二次地圖

考慮以下圖：Map.fromList [(1,"foo"), (2,"bar"), (3,"foo")]Haskell的：摺疊的地圖，同時更新的二次地圖

我想產生：Map.fromList [(1,"foo"), (2,"bar"), (3,"1")]。最後一個與之前與「foo」關聯的鍵3現在與「1」相關聯 - 所以通過跟隨該值（並將該字符串轉換爲數字），我仍然可以到達「foo」。如果結果是Map.fromList [(1,"3"), (2,"bar"), (3,"foo")]，那也可以。

理想情況下，我會通過摺疊原始地圖來實現。隨着它，我會增加一個輔助（反向）地圖與元素（「foo」，1），（「bar」，2）等。如果當前鍵在輔助映射中找到，而不是插入它進入最終的地圖，我會插入其相關的值。

有沒有簡單/優雅的方式來排序，沒有多次通過或Monad？

main = do 
    let names = Map.fromList [(1,"foo"), (2,"bar"), (3,"foo")] 
     link acc k v = -- insert into map1, depending map2's lookup 
     names' = Map.foldlWithKey link (Map.empty, Map.empty) names 
    putStrLn $ show names'

來源

2016-08-30 Leandro T. C. Melo

這似乎很奇怪。如果你想產生「Map Integer（整型字符串）」，這看起來會稍微不那麼奇怪，從而明確它的值是最後一個還是一個引用。但即使有這種變化，這有點奇怪。你爲什麼需要這個？ – dfeuer

確實......這是對我的實際情況的一種修改，我可以想出一個最小的例子來展示我懷疑的本質：在映射/摺疊地圖時更新輔助數據結構。 –

我認爲你可以做的最好的就是使用mapAccumWithKey。然後，像這樣：

deduplicate :: Map Int String -> Map Int String 
deduplicate = snd . Map.mapAccumWithKey go Map.empty 
    where 
    go accum k v = case Map.lookup v accum of 
        Nothing -> (Map.insert v (show k) accum, v) 
        Just v' -> (accum, v')

這一個映射按鍵由一個同時通過Map String String其跟蹤已經看到值及其相應的鍵的線程。如果你想嘗試一些平行的東西，顯然有一些更酷的東西要做，但順序地這是最優的 - 它應該是O(n log n)，你至少需要檢測共享密鑰。

隨着names' = deduplicate names，我得到的輸出fromList [(1,"foo"),(2,"bar"),(3,"1")]。

來源

2016-08-30 22:13:18 Alec

謝謝，我不知道mapAccumWithKey。 –

Haskell的：摺疊的地圖，同時更新的二次地圖

回答

相關問題