Invert nested dictionaries in f # Map <'a, Map <' b, 'T >>) & # 8594; Map <'b, Map <' a, 'T >>
I have a nested dictionary
entry is unique for the combination .
To effectively convert, I would need to invert the keys to
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
I think @pad's solution is definitely more idiomatic than F # than using non-standard operators like
. I would prefer a version that uses sequence expressions instead of
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
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 .
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
@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.