Cách chức năng để chia bản đồ danh sách thành danh sách bản đồ

Question

Tôi có chút khó khăn về vấn đề này. Tôi cảm thấy như tôi đang "suy nghĩ ngược" và nó làm tôi bối rối một chút.

Tôi có một số Map[Long, Seq[String]] mà tôi muốn chuyển đổi thành một số Seq[Map[Long, String]]. Đi theo một hướng khác là khá đơn giản, vì chúng ta chỉ có thể nhóm các phần tử lại với nhau, tuy nhiên, tôi không chắc chắn làm thế nào để tách nó ra một cách chức năng.

Vì vậy,

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

nên trở thành

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

Tôi đã suy nghĩ dọc theo dòng của việc sử dụng x.partition và sau đó recursing trên mỗi tuple kết quả, nhưng tôi không thực sự chắc chắn những gì tôi muốn phân vùng trên:/

Tôi viết bằng scala, nhưng mọi câu trả lời chức năng đều được chào đón (ngôn ngữ thuyết bất khả tri).

Answer 1

Trong 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 và M.fromList chuyển đổi một bản đồ đến một danh sách các cặp hiệp hội, và ngược lại.

map ((,) i) xs cũng giống như [(i,x) | x<-xs], thêm (i,...) cho từng phần tử.

transpose trao đổi "hàng" và "cột" trong danh sách danh sách, tương tự như chuyển vị ma trận.

Answer 2

Trong 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

Dưới đây là câu trả lời của tôi trong OCaml (chỉ sử dụng thư viện chuẩn):

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 

Nó làm việc cho tôi:

# 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

Vay một gọn gàng transpose phương thức từ SO answer, đây là một cách khác để thực hiện:

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) 
//)