在f#Map <'a,Map <'b,'T >>)中反转嵌套字典 - > Map <'b,Map <'a,'T >>

Question

我有一个嵌套字典Map<'a,Map<'b,'T>>,因此对于组合a*b,条目是唯一的.

为了有效地进行预计算,我需要反转一个中的键 Map<'b,Map<'a,'T>>

我有一些更高阶的方法来完成这项工作(|/>将在嵌套序列|//>中应用相同的操作,但是2级深度,|*>将枚举嵌套序列的笛卡尔积),但我想知道是否有更好的方法来执行此操作,以防万一有漂亮的代码分享这个.

let reversenmap (x:Map<'a,Map<'b,'T>>) :Map<'b,Map<'a,'T>> = 
      let ret  = x |> Map.toSeq |/> Map.toSeq |*> squash12
      let ret2 = ret |> Seq.groupByn2 (fun (a,b,t) -> b) 
                                      (fun (a,b,t) -> a) |//> Seq.head 
                                                         |//> (fun (a,b,c) -> c)
      ret2 |> Seq.toMapn2

Answer 1

您尝试解决的问题称为有向图的转置,可以使用双折来计算,如下所示:

let invert xyzs =
  Map.fold (fun m x yzs ->
    Map.fold (fun m y z ->
      let m' = defaultArg (Map.tryFind y m) Map.empty
      Map.add y (Map.add x z m') m) m yzs) Map.empty xyzs

有关详细信息,请参阅F#.NET Journal文章图算法:拓扑排序和所有对最短路径.

Answer 2

我认为来自@pad的解决方案肯定比使用像|/>和的非标准运算符更加惯用F#|*>.我可能更喜欢使用序列表达式的版本而不是Seq.collect,它看起来像这样(第二部分与@pad中的版本相同):

let reverse (map: Map<'a,Map<'b,'T>>) = 
  [ for (KeyValue(a, m)) in map do
      for (KeyValue(b, v)) in m do yield b, (a, v) ]
  |> Seq.groupBy fst 
  |> Seq.map (fun (b, ats) -> b, ats |> Seq.map snd |> Map.ofSeq) 
  |> Map.ofSeq