文章/答案/技术大牛

发布

社区首页 >问答首页 >定义不规则集合上的转置

问定义不规则集合上的转置
EN

Code Review用户

提问于 2012-05-20 13:30:57

回答 1查看 1.3K关注 0票数 3

--我被要求在这里向https://stackoverflow.com/questions/10672046/defining-transpose-on-a-collection-of-irregular-collections提交代码评审请求.

这是我在https://stackoverflow.com/questions/1683312/is-there-a-safe-way-in-scala-to-transpose-a-list-of-unequal-length-lists/10663749#10663749上写的帖子的后续。我想通过将List一个看作从Int到A的映射来为不等大小的列表提供转置的定义。首先，我认为在引用的文章中定义的转置是有问题的。

scala>  val l = List(List(1, 2, 3), List(4, 5), List(6, 7, 8))
l: List[List[Int]] = List(List(1, 2, 3), List(4, 5), List(6, 7, 8))

scala> val lt = transpose( l )
lt: List[List[Int]] = List(List(1, 4, 6), List(2, 5, 7), List(3, 8))

scala> val ltt = transpose( lt )
ltt: List[List[Int]] = List(List(1, 2, 3), List(4, 5, 8), List(6, 7))

scala> l == ltt
res0: Boolean = false

因此，转座子( transpose( l ))与L不一样，问题的根源在于转置的定义不尊重与元素相关的精确指标(在编制内部列表时存在元素的隐式“转移”)。

因此，我建议将不等大小的列表( list [List一个])上的转置更抽象地看作是对MapInt，地图[国际]的操作。此操作定义明确，可进一步抽象为对Map[A，MapB、C]进行操作，如下所示：

def transpose[A,B,C]( mapOfMaps: Map[A,Map[B,C]] ) : Map[B,Map[A,C]] = {
  val innerKeys = ( mapOfMaps map { p => ( p._2.keys ) toList } ) flatten
  val outerKeys = ( mapOfMaps keys ) toList
  val allValues = innerKeys map { ik => outerKeys filter { ok => mapOfMaps( ok ).contains( ik ) } map { ok => ( ok, mapOfMaps( ok )( ik ) ) } toMap }
  ( innerKeys zip allValues ) toMap
}

要将列表列表转换为更抽象的地图，拉链是很方便的。

def listOfListsToMapOfMaps[A]( l : List[List[A]] ) : Map[Int,Map[Int,A]]= {
  val listOfMaps = l map { x => ( x.indices zip x ) toMap }
  ( listOfMaps.indices zip listOfMaps ) toMap
}

现在，一切都是干净的：

scala> val m = listOfListsToMapOfMaps( l )
m: Map[Int,Map[Int,Int]] = Map(0 -> Map(0 -> 1, 1 -> 2, 2 -> 3), 1 -> Map(0 -> 4, 1 -> 5), 2 -> Map(0 -> 6, 1 -> 7, 2 -> 8))

scala>  val mt = transpose( m )
mt: Map[Int,Map[Int,Int]] = Map(0 -> Map(0 -> 1, 1 -> 4, 2 -> 6), 1 -> Map(0 -> 2, 1 -> 5, 2 -> 7), 2 -> Map(0 -> 3, 2 -> 8))

scala> val mtt = transpose( mt )
mtt: Map[Int,Map[Int,Int]] = Map(0 -> Map(0 -> 1, 1 -> 2, 2 -> 3), 1 -> Map(0 -> 4, 1 -> 5), 2 -> Map(0 -> 6, 1 -> 7, 2 -> 8))

scala> m == mtt
res1: Boolean = true

在我的工作中，我看到了这种广义转置操作的大量用途(而且我肯定还有很多其他的操作--跨语言)。但我希望人们在将其放入核心库并开始使用它之前，先回顾一下我的转置定义和实现(我对Scala还比较陌生，并且确信我的实现可以改进)。

functional-programming

scala

collections

回答 1

Code Review用户

发布于 2013-07-26 18:45:29

是的，traspose定义的结果缩小为最短列表的大小不是对合。你把列表看作地图的想法很好，但是我想一旦你离开Lists，还有其他更简单的选择。

正如您所观察到的，List[A]也是一个在0和列表大小之间的整数上工作的PartialFunction[Int,A]。现在，如果我们有一个列表，它是PartialFunction[Int,PartialFunction[Int,A]]。现在，我们可以通过一个名为不竞逐的进程将这些函数转换为单个函数。虽然Scala有用于普通函数的uncurried，但对于PartialFunctions却缺乏它。但是定义它并不难：

def uncurried[A,B,C](f: PartialFunction[A,PartialFunction[B,C]]):
    PartialFunction[(A,B),C] =
  Function.unlift((x: (A,B)) => f.lift(x._1).flatMap(_.lift(x._2)));

因此，我们可以立即将uncurried应用于List[List[A]] (或者更确切地说是对Seq[Seq[A]]，以避免对列表的O(n)访问)，并得到接受一对索引并给出结果的函数表示。如果我们交换成对的索引，我们会得到一个转置视图。

这种表示的问题是，我们不能很容易地枚举所有匹配的索引。如果需要这样做，我们可以将一个列表转换为Map[(Int,Int),A]，也许是一个SortedMap，这样我们就可以按适当的顺序枚举索引。同样，这将是一个PartialFunction[(Int,Int),A]，但也有这种额外的能力。

票数 3

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/11924

复制

相似问题

问定义不规则集合上的转置
EN

--我被要求在这里向https://stackoverflow.com/questions/10672046/defining-transpose-on-a-collection-of-irregular-collections提交代码评审请求.

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问定义不规则集合上的转置EN

--我被要求在这里向https://stackoverflow.com/questions/10672046/defining-transpose-on-a-collection-of-irregular-collections提交代码评审请求.

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问定义不规则集合上的转置
EN