3

我有一个嵌套字典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
4

4 回答 4

7

您要解决的问题称为有向图的转置，可以使用双折计算，如下所示：

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 期刊文章图形算法：拓扑排序和所有对最短路径。

于 2012-03-23T13:30:11.763 回答
5

我认为@pad 的解决方案绝对比使用非标准运算符（如|/>and ）更符合 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
于 2012-03-22T13:15:44.097 回答
2

我不确定我是否理解你的意图。但是从你的函数的签名，我们可以做这样的事情：

let reverse (map: Map<'a,Map<'b,'T>>) =
    map |> Seq.collect (fun (KeyValue(a, m)) -> 
                                m |> Seq.map (fun (KeyValue(b, t)) -> b, (a, t)))
        |> Seq.groupBy fst
        |> Seq.map (fun (b, ats) -> b, ats |> Seq.map snd |> Map.ofSeq)
        |> Map.ofSeq
于 2012-03-22T12:36:46.810 回答
2

@pad 的解决方案与我提出的解决方案非常相似——我想它只是表明，对于这些类型的问题，你只能跟着鼻子做唯一可行的事情，直到你到达那里。

或者，如果你想坚持折叠，你可以这样做：

let invertNesting ( map : Map<'a, Map<'b, 'c>> ) =
    let foldHelper ( oldState : Map<'b, Map<'a, 'c>> ) ( k1 : 'a ) ( innerMap : Map<'b, 'c> =
        innerMap |> Map.fold (fun tempState k2 v ->
                                  let innerMap' = match ( tempState |> Map.tryFind k2 ) with
                                                  | Some(m) -> m
                                                  | None -> Map.empty
                                  let innerMap'' = innerMap' |> Map.add k1 v
                                  tempState |> Map.add k2 innerMap'' ) oldState
    map |> Map.fold foldHelper Map.empty

虽然@Tomas Petricek 的解决方案对我来说更具可读性，但这似乎快了大约 25%。

于 2012-03-22T13:14:13.617 回答