Funktionelle Möglichkeit, eine Karte von Listen in eine Liste von Karten zu teilen

Question

Ich bin ein bisschen fest auf dieses Problem. Ich fühle mich, als würde ich "rückwärts denken" und es verwirrt mich ein bisschen.

Ich habe eine Map[Long, Seq[String]], die ich in eine Seq[Map[Long, String]] konvertieren möchte. Die andere Richtung zu gehen ist ziemlich einfach, da wir Elemente einfach gruppieren können, aber ich bin mir nicht sicher, wie man das auf eine funktionale Art aufteilt.

So

val x = Map(1 -> List("a","b","c"), 2 -> List("d", "e"), 3 -> List("f")) 

List(Map(1 -> "a", 2 -> "d", 3 -> "f"), Map(1 -> "b", 2 -> "e"), Map(1 -> "c")) 

werden soll ich wurde entlang der Linien denken x.partition verwenden und dann auf jedes resultierenden Tupel Rekursion, aber ich bin nicht wirklich sicher, was ich würde Partition auf:/

Ich schreibe in Scala, aber jede funktionale Antwort ist willkommen (Sprache Agnostiker).

Answer 1

In Haskell:

> import qualified Data.Map as M 
> import Data.List 
> m = M.fromList [(1,["a","b","c"]), (2,["d","e"]), (3,["f"])] 
> map M.fromList . transpose . map (\(i,xs) -> map ((,) i) xs) . M.toList $ m 
[fromList [(1,"a"),(2,"d"),(3,"f")],fromList [(1,"b"),(2,"e")],fromList [(1,"c")]] 

M.toList und M.fromList konvertieren eine Karte auf eine Liste von Assoziationspaaren und zurück.

map ((,) i) xs ist das gleiche wie [(i,x) | x<-xs], Hinzufügen (i,...) zu jedem Element.

transpose tauscht die "Zeilen" und "Spalten" in einer Liste von Listen aus, ähnlich einer Matrixtransposition.

Answer 2

In Scala:

val result = x.toList 
    .flatMap { case (k, vs) => vs.zipWithIndex.map { case (v, i) => (i, k, v) } } // flatten and add indices to inner lists 
    .groupBy(_._1)     // group by index 
    .toList.sortBy(_._1).map(_._2) // can be replaced with .values if order isn't important 
    .map(_.map { case (_, k, v) => (k, v) }.toMap) // remove indices 

Answer 3

Hier ist meine Antwort in OCaml (mit nur Standard Library):

module M = Map.Make(struct type t = int let compare = compare end) 

let of_bindings b = 
    List.fold_right (fun (k, v) m -> M.add k v m) b M.empty 

let splitmap m = 
    let split1 (k, v) (b1, b2) = 
     match v with 
     | [] -> (b1, b2) 
     | [x] -> ((k, x) :: b1, b2) 
     | h :: t -> ((k, h) :: b1, (k, t) :: b2) 
    in 
    let rec loop sofar m = 
     if M.cardinal m = 0 then 
      List.rev sofar 
     else 
      let (b1, b2) = 
       List.fold_right split1 (M.bindings m) ([], []) 
      in 
      let (ms, m') = (of_bindings b1, of_bindings b2) in 
      loop (ms :: sofar) m' 
    in 
    loop [] m 

Es funktioniert für mich:

# let m = of_bindings [(1, ["a"; "b"; "c"]); (2, ["d"; "e"]); (3, ["f"])];; 
val m : string list M.t = <abstr> 
# let ms = splitmap m;; 
val ms : string M.t list = [<abstr>; <abstr>; <abstr>] 
# List.map M.bindings ms;; 
- : (M.key * string) list list = 
[[(1, "a"); (2, "d"); (3, "f")]; [(1, "b"); (2, "e")]; [(1, "c")]] 

Answer 4

Borrowing eine ordentliche transpose Methode von diesem SO answer, hier ist ein anderer Weg, es zu tun:

def transpose[A](xs: List[List[A]]): List[List[A]] = xs.filter(_.nonEmpty) match {  
    case Nil => Nil 
    case ys: List[List[A]] => ys.map{ _.head }::transpose(ys.map{ _.tail }) 
} 

transpose[(Int, String)](
    x.toList.map{ case (k, v) => v.map((k, _)) } 
).map{ _.toMap } 

// Res1: List[scala.collection.immutable.Map[Int,String]] = List(
// Map(1 -> a, 2 -> d, 3 -> f), Map(1 -> b, 2 -> e), Map(1 -> c) 
//)