Defining transpose on a collection of irregular collections

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 listOfLis

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.

StackExchange Code Review Q#11924, answer score: 3