¿Hay una manera segura en la Scala de transponer una lista de listas de longitud desigual?

Question

Dada la siguiente lista:

val l = List(List(1, 2, 3), List(4, 5), List(6, 7, 8)) 

Si trato de transposición, Scala arrojará el siguiente error:

scala> List.transpose(l) 
java.util.NoSuchElementException: head of empty list 
    at scala.Nil$.head(List.scala:1365) 
    at scala.Nil$.head(List.scala:1362) 
    at scala.List$$anonfun$transpose$1.apply(List.scala:417) 
    at scala.List$$anonfun$transpose$1.apply(List.scala:417) 
    at scala.List.map(List.scala:812) 
    at scala.List$.transpose(List.scala:417) 
    at .<init>(<console>:6) 
    at .<clinit>(<console>) 
    at RequestResult... 

Esto se debe a List.transpose asume listas de igual longitud y por lo tanto utiliza el método head :

def transpose[A](xss: List[List[A]]): List[List[A]] = { 
    val buf = new ListBuffer[List[A]] 
    var yss = xss 
    while (!yss.head.isEmpty) { 
    buf += (yss map (_.head)) 
    yss = (yss map (_.tail)) 
    } 
    buf.toList 
} 

me gustaría obtener la siguiente:

List(List(1, 4, 6), List(2, 5, 7), List(3, 8)) 

¿Está escribiendo mi propia versión de transpose la mejor manera de hacerlo? Esto es lo que ocurrió:

def myTranspose[A](xss: List[List[A]]): List[List[A]] = { 
    val buf = new ListBuffer[List[A]] 
    var yss = xss 
    while (!yss.head.isEmpty) { 
    buf += (yss filter (!_.isEmpty) map (_.head)) 
    yss = (yss filter (!_.isEmpty) map (_.tail)) 
    } 
    buf.toList 
} 

Actualización: que estaba interesado en la comparación de la velocidad de las diferentes soluciones que aquí se ofrecen, por lo que poner juntos los siguientes poca referencia:

import scala.testing.Benchmark 
import scala.collection.mutable.ListBuffer 

trait Transpose extends Benchmark { 
    def transpose[Int](xss: List[List[Int]]): List[List[Int]] = Nil 
    val list: List[List[Int]] = List(List(1,2,3), Nil, List(4,5,99,100), List(6,7,8)) 
    def run = { 
    val l = transpose(list) 
    println(l) 
    l 
    } 
} 

object PRTranspose extends Transpose { 
    override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = { 
    val buf = new ListBuffer[List[Int]] 
    var yss = xss 
    while (!yss.head.isEmpty) { 
     buf += (yss filter (!_.isEmpty) map (_.head)) 
     yss = (yss filter (!_.isEmpty) map (_.tail)) 
    } 
    buf.toList 
    } 
} 

object ACTranspose extends Transpose { 
    override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = { 
    val b = new ListBuffer[List[Int]] 
    var y = xss filter (!_.isEmpty) 
    while (!y.isEmpty) { 
     b += y map (_.head) 
     y = y map (_.tail) filter (!_.isEmpty) 
    } 
    b.toList 
    } 
} 

object ETranspose extends Transpose { 
    override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = xss.filter(!_.isEmpty) match {  
    case Nil => Nil 
    case ys: List[List[Int]] => ys.map{ _.head }::transpose(ys.map{ _.tail }) 
    } 
} 

Mi comandos fueron:

scala PFTranspose 5 out.log 
scala ACTranspose 5 out.log 
scala ETranspose 5 out.log 

Mis resultados fueron los siguientes:

PRTranspose$   10    0    1    1    0 
ACTranspose$   9    2    0    0    0 
ETranspose$    9    3    2    3    1 

Answer 1

¿Qué tal esto:

scala> def transpose[A](xs: List[List[A]]): List[List[A]] = xs.filter(_.nonEmpty) match {  
     |  case Nil => Nil 
     |  case ys: List[List[A]] => ys.map{ _.head }::transpose(ys.map{ _.tail }) 
     | } 
    warning: there were unchecked warnings; re-run with -unchecked for details 
    transpose: [A](xs: List[List[A]])List[List[A]] 

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

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

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

scala> transpose(xs) 
res1: List[List[Int]] = List(List(1, 4, 6), List(2, 5, 7), List(3, 99, 8), List(100)) 

Answer 2

no sé de (y no se puede imaginar - no es esto es un poco extraño ?! [Véase la discusión en los comentarios]) una función de biblioteca, pero puedo pulir el código un poco:

scala> def transpose(x: List[List[Int]]): List[List[Int]] = { 
    | val b = new ListBuffer[List[Int]] 
    | var y = x filter (!_.isEmpty) 
    | while (!y.isEmpty) { 
    |  b += y map (_.head) 
    |  y = y map (_.tail) filter (!_.isEmpty) 
    | } 
    | b.toList 
    | } 

Answer 3

Sospecho que la razón de transposición no está definido en un "no "La lista de listas rectangular" se debe a que matemáticamente la operación de transposición está bien definida solo en "estructuras rectangulares". Una propiedad deseable de una operación de transposición es la transposición (transpose (x)) == x. Este no es el caso en su generalización de la operación de transposición en la lista no rectangular de listas.

También, echar un vistazo a mi post sobre Transposing arbitrary collection-of-collections in Scala y pensar en hacerlo para las colecciones-de-colecciones no rectangulares. Terminará con definiciones matemáticamente inconsistentes, dejando implementaciones solitarias.

Estoy de acuerdo en que las operaciones de "transposición" idiosincrásicas suelen ser útiles, pero también creo que no deberían estar disponibles en las bibliotecas estándar debido a la posible confusión con respecto a sus definiciones precisas.

Answer 4

Este es probablemente el más limpio:

def transpose[T](l: List[List[T]]): List[List[T]] = 
    l.flatMap(_.headOption) match { 
     case Nil => Nil 
     case head => head :: transpose(l.map(_.drop(1))) 
    } 

o una versión modificada que es aún más eficiente:

def transpose[T](l: List[List[T]]): List[List[T]] = 
    l.flatMap(_.headOption) match { 
     case Nil => Nil 
     case head => head :: transpose(l.collect { case _ :: tail => tail }) 
    } 

Answer 5

¿Qué tal esto de una sola línea usando API estándar de la Scala:

((l map (_.toArray)) toArray).transpose map (_.toList) toList 

Esto hace el trabajo y es O(N*M), donde N es la longitud de la lista contenedora y M es la longitud de la lista más larga dentro de la lista contenedora.