Existe uma maneira segura em Scala para transpor uma lista de listas desiguais?

Question

Dada a seguinte lista:

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

Se eu tentar transpor, Scala lançará o seguinte erro:

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

Isto é porque List.transpose assume listas de comprimento igual e assim usa o head método:

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
}

Eu gostaria de obter o seguinte:

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

Está escrevendo minha própria versão de transpose A melhor maneira de fazer isso? Isso é o que eu criei:

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
}

Atualizar: Eu estava interessado em comparar a velocidade das diferentes soluções oferecidas aqui, então montei o seguinte Little Benchmark:

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

Meus comandos eram:

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

Meus resultados foram:

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

Answer 1

Que tal agora:

    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

Suspeito que o motivo que a transposição não esteja definido em uma lista "não retangular" de listas é porque matematicamente a operação de transposição é bem definida apenas em "estruturas retangulares". Uma propriedade desejável de uma operação de transposição é a transposição (transposição (x)) == x. Este não é o caso na sua generalização da operação de transposição na lista não retangular de listas.

Além disso, dê uma olhada no meu post em Transpondo a coleta de coleta arbitrária em Scala E pense em fazê-lo para coleções de coleções não retangulares. Você acabará com definições matematicamente inconsistentes, deixará implementações em paz.

Concordo que as operações idiossincráticas de "transposição" são frequentemente úteis, mas também acho que elas não devem ser disponibilizadas em bibliotecas padrão devido a uma confusão potencial em relação às suas definições precisas.

Answer 3

Eu não sei (e não posso imaginar - isso não é um pouco estranho?! [Veja discussão em comentários]) Uma função da biblioteca, mas posso polir o código um pouco:

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 4

Este é provavelmente o mais limpo:

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

ou uma versão modificada que é ainda mais 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

Que tal esta linha usando a API padrão do Scala:

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

Isso faz o trabalho e é O(N*M), Onde N é a duração da lista de invólucros e M é o comprimento da lista mais longa dentro da lista de wrapper.