# 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

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

```

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

All Articles