在Scala中转移任意集合集合 [英] Transposing arbitrary collection-of-collections in Scala

问题描述

我必须经常在Scala中转置一个矩形集合集合，例如：地图列表，列表地图，地图地图，一组列表，集合地图等。可以统一地视为从特定域到共域的映射（例如：List [A] / Array [A]是从Int域到A共同域的映射，Set [A]是映射从A域到布尔共域等），我想编写一个干净的通用函数来做转置操作（例如：将列表的地图转换为转置的地图列表）。但是，我有麻烦，因为除了（）运算符，Scala似乎没有一个统一的API来抽象地查看集合作为映射？

I have to often transpose a "rectangular" collection-of-collections in Scala, e.g.: a list of maps, a map of lists, a map of maps, a set of lists, a map of sets etc. Since collections can be uniformly viewed as a mapping from a specific domain to a co-domain (e.g.: a List[A]/Array[A] is a mapping from the Int domain to the A co-domain, Set[A]is a mapping from the A domain to the Boolean co-domain etc.), I'd like to write a clean, generic function to do a transpose operation (e.g.: turn a map of lists to the transposed list of maps). However, I'm having trouble because other than the () operator, Scala doesn't seem to have a unified API to view collections abstractly as mappings ?

为每个类型的集合集合编写单独的转置如下：

So I end up writing a separate transpose for each type of collection-of-collections as follows:

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

有人帮我把这些方法统一为一个通用的集合转置？它也将帮助我（和我相信其他人）在过程中学习一些有用的Scala功能。

Can someone help me unify these methods into one generic collection-of-collections transpose ? It will also help me (and I am sure others) learn some useful Scala features in the process.

ps：我忽略了异常处理， of-collections是矩形的，即所有内部集合的域元素构成相同的集合。

ps: I have ignored exception handling and have assumed the input collection-of-collections is rectangular, i.e., all of the inner collections' domain elements constitute the same set.

推荐答案

以下使用类型类的杂乱版本可以清理很多，但它作为一个快速概念验证。我没有看到一个简单的方法来获取正确的返回类型没有依赖的方法类型（我相信这是可能的），所以你必须使用 -Xexperimental ：

I'm sure the following messy version using type classes could be cleaned up a lot, but it works as a quick proof-of-concept. I don't see an easy way to get the return types right without dependent method types (I'm sure it's possible), so you'll have to use -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) })
))

现在对于一些测试：

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

因此它可以按照需要工作。

So it's working as desired.

这篇关于在Scala中转移任意集合集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！