Transposición de colecciones arbitrarias de colecciones en Scala

Question

A menudo tengo que transponer una colección de colecciones "rectangular" en Scala, por ejemplo: una lista de mapas, un mapa de listas, un mapa de mapas, un conjunto de listas , un mapa de conjuntos, etc. Dado que las colecciones se pueden ver de manera uniforme como un mapeo de un dominio específico a un co-dominio (por ej .: una Lista [A]/Array [A] es una asignación del dominio Int al co-A dominio, Set [A] es un mapeo desde el dominio A hasta el co-dominio booleano, etc.), me gustaría escribir una función limpia y genérica para hacer una operación de transposición (por ejemplo: convertir un mapa de listas en el transpuesto lista de mapas). Sin embargo, estoy teniendo problemas porque, aparte del operador(), Scala no parece tener una API unificada para ver las colecciones de forma abstracta como asignaciones.

Así que terminan escribiendo una transposición separado para cada tipo de colección de colecciones de la siguiente manera:

def transposeMapOfLists[A,B](mapOfLists: Map[A,List[B]]) : List[Map[A,B]] = { 
    val k = (mapOfLists keys) toList 
    val l = (k map { mapOfLists(_) }) transpose; 
    l map { v => (k zip v) toMap } 
} 

def transposeListOfMaps[A,B](listOfMaps: List[Map[A,B]]) : Map[A,List[B]] = { 
    val k = (listOfMaps(0) keys) toList 
    val l = (listOfMaps map { m => k map { m(_) } }) transpose; 
    (k zip l) toMap 
} 

def transposeMapOfMaps[A,B,C](mapOfMaps: Map[A,Map[B,C]]) : Map[B,Map[A,C]] = { 
    val k = (mapOfMaps keys) toList 
    val listOfMaps = k map { mapOfMaps(_) } 
    val mapOfLists = transposeListOfMaps(listOfMaps) 
    mapOfLists map { p => (p._1, (k zip p._2) toMap) } 
} 

Puede alguien me ayude a unificar estos métodos en uno colecciones colección de transposición genéricos? También me ayudará (y estoy seguro de que otros) aprenden algunas características útiles de Scala en el proceso.

ps: He ignorado el manejo de excepciones y he asumido que la colección de colecciones de entrada es rectangular, es decir, todos los elementos de dominio de las colecciones internas constituyen el mismo conjunto.

Answer 1

Estoy seguro de que la siguiente versión desordenada que utiliza clases de tipo podría limpiarse mucho, pero funciona como una prueba rápida de concepto. No veo una manera fácil de obtener los tipos de retorno correcto sin tipos de métodos dependientes (estoy seguro de que es posible), por lo que tendrá que usar -Xexperimental:

trait Mapping[A, B, C] { 
    type M[D] <: PartialFunction[A, D] 
    def domain(c: C): Seq[A] 
    def fromPairs[D](ps: Seq[(A, D)]): M[D] 
    def codomain(c: C)(implicit ev: C <:< PartialFunction[A, B]) = 
    domain(c).map(c) 
    def toPairs(c: C)(implicit ev: C <:< PartialFunction[A, B]) = 
    domain(c).map(a => (a, c(a))) 
} 

implicit def seqMapping[A, B <: Seq[A]] = new Mapping[Int, A, B] { 
    type M[C] = Seq[C] 
    def domain(c: B) = 0 until c.size 
    def fromPairs[C](ps: Seq[(Int, C)]) = ps.sortBy(_._1).map(_._2) 
} 

implicit def mapMapping[A, B, C <: Map[A, B]] = new Mapping[A, B, C] { 
    type M[D] = Map[A, D] 
    def domain(c: C) = c.keys.toSeq 
    def fromPairs[D](ps: Seq[(A, D)]) = ps.toMap 
} 

def transpose[A, B, C, M, N](m: M)(implicit 
    pev: M <:< PartialFunction[A, N], 
    qev: N <:< PartialFunction[B, C], 
    mev: Mapping[A, N, M], 
    nev: Mapping[B, C, N] 
) = nev.fromPairs(nev.domain(mev.codomain(m).head).map(b => 
    b -> mev.fromPairs(mev.toPairs(m).map { case (a, c) => a -> c(b) }) 
)) 

Y ahora para algunas pruebas:

scala> println(transpose(List(Map("a" -> 1, "b" -> 13), Map("b" -> 99, "a" -> 14)))) 
Map(a -> Vector(1, 14), b -> Vector(13, 99)) 

scala> println(transpose(Map('a' -> List(1, 2, 3), 'z' -> List(4, 5, 6)))) 
Vector(Map(a -> 1, z -> 4), Map(a -> 2, z -> 5), Map(a -> 3, z -> 6)) 

scala> println(transpose(Map("x" -> Map(4 -> 'a, 99 -> 'z), "y" -> Map(4 -> 'b, 99 -> 's)))) 
Map(4 -> Map(x -> 'a, y -> 'b), 99 -> Map(x -> 'z, y -> 's)) 

Por lo tanto, está trabajando como desee.