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的：折叠的地图，同时更新的二次地图

回答

相关问题