Clever Geek Handbook

Invert nested dictionaries in f # Map <'a, Map <' b, 'T >>) & # 8594; Map <'b, Map <' a, 'T >>

I have a nested dictionary Map<'a,Map<'b,'T>>

so the a*b

entry is unique for the combination .

To effectively convert, I would need to invert the keys to Map<'b,Map<'a,'T>>

I have several higher order methods that do the job ( |/>

will apply an operation in a nested sequence |//>

the same, but 2 levels deep, will |*>

enumerate the cartesian product of the nested sequence), but I'm wondering if there is a better way to do this, just in case there is a nice code to share this.

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
+3


source share


4 answers


I think @pad's solution is definitely more idiomatic than F # than using non-standard operators like |/>

and |*>

. I would prefer a version that uses sequence expressions instead of Seq.collect

one that looks like this (the second part is the same as @pad's version):



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
+5


source


The problem you are trying to solve is called directed graph transposition and can be calculated using double fold as follows:

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


For more information, see the article F # .NET Journal Graphical Algorithms: Topological Sorts and All Paired Shortest Paths .

+7


source


I'm not sure I understand your intentions. But from your function signature, we could do something like this:

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
+2


source


@pad's solution is surprisingly similar to what I came up with - I think it just goes to show that with problems like this, you keep an eye on your nose, doing the only thing that might work until you get there.

Alternatively, if you want to stick to folds, you can do:

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

While @Tomas Petricek's solution is more readable to me, it is about 25% faster.

+2


source






More articles:


All Articles