3
\$\begingroup\$

I was asked to submit my request for code review on https://stackoverflow.com/questions/10672046/defining-transpose-on-a-collection-of-irregular-collections here.

This is a follow-up to the post I made in https://stackoverflow.com/questions/1683312/is-there-a-safe-way-in-scala-to-transpose-a-list-of-unequal-length-lists/10663749#10663749. I want to propose a definition of transpose for a list of unequal-sized lists by viewing List[A] as a mapping from Int to A. First, here's why I think the transpose defined in the referenced post is problematic.

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

So, transpose( transpose( l ) ) is not the same as l. The problem arises from the fact that this definition of transpose does not respect the precise indices associated with the elements (there is implicit "shifting" of elements when preparing the inner lists).

So I am proposing that transpose on a list of unequal-sized lists (List[List[A]]) be more abstractly viewed as an operation on a Map[Int,Map[Int,A]] (because a List[A] can be viewed as a Map[Int,A]). This operation is well-defined and can be further abstracted to operate on a Map[A,Map[B,C]] as follows:

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
} 

To transform a list of lists to the more-abstract map of maps, zipping is convenient.

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
}

Now, things are clean:

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

I see plenty of use for this generalized transpose operation in my work (and I'm sure for many others - across languages). But I'd like for people to review my transpose definition and implementation before I put it into my core library and start using it (I'm relatively new to Scala and am sure my implementation can be improved).

\$\endgroup\$
3
\$\begingroup\$

Yes, traspose defined such that it shrings the result to the size of the shortest list isn't an involution. Your idea of viewing lists as maps is nice, but I suppose once you leave Lists, there are other easier options.

As you observed, List[A] is also a PartialFunction[Int,A] that works on integers that are between 0 and the size of the list. Now if we have a list of lists, it's PartialFunction[Int,PartialFunction[Int,A]]. Now we can convert such functions into a single function by a process called un-currying. While Scala has uncurried for plain functions, it lacks it for PartialFunctions. But it's not difficult to define it:

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

So we can apply uncurried immediately on List[List[A]] (or rather to Seq[Seq[A]] to avoid O(n) access for lists) and we get a functional representation that accepts a pair of indices and gives the result. If we swap the indices in a pair, we get a transposed view.

The problem with this representation is that we can't enumerate all matching indices easily. If this is required, we could instead convert a list of lists into Map[(Int,Int),A], perhaps a SortedMap so that we can enumerate the indices in a proper order. Again, this will be a PartialFunction[(Int,Int),A], but also with this additional ability.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.