Haskell: складной над картой, при обновлении вторичной карты

Question

Рассмотрим следующую карту: Map.fromList [(1,"foo"), (2,"bar"), (3,"foo")]

я хотел бы произвести: Map.fromList [(1,"foo"), (2,"bar"), (3,"1")]. Последний ключ 3, ранее связанный с «foo», теперь связан с «1», поэтому, следуя этому значению (и преобразовая строку в число), я все равно могу получить «foo». Если результат был Map.fromList [(1,"3"), (2,"bar"), (3,"foo")], все было бы в порядке.

В идеале я бы выполнил это, сложив исходную карту. Наряду с этим я постепенно добавлял вторичную (обратную) карту с элементами («foo», 1), («bar», 2) и т. Д. Если текущий ключ находится на вторичной карте, вместо вставки он в окончательную карту, я бы вставлял его связанное значение.

Есть ли простой/изящный способ последовательности, без нескольких проходов или монады?

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' 

Answer 1

Я думаю, что лучшее, что вы можете сделать, это использовать 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")].