# 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`

source share

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`

source share

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 .

source share

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`

source share

@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.

source share