Y at-il un moyen sûr à Scala de transposer une liste de listes de longueur inégale?

Question

Compte tenu de la liste suivante:

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

Si je tente de le transposer, Scala jeter l'erreur suivante:

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

Ceci est parce que List.transpose suppose des listes de longueur égale et utilise alors la méthode de 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
}

Je voudrais obtenir ce qui suit:

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

est écrit ma propre version de transpose la meilleure façon de le faire? C'est ce que je suis venu avec:

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
}

Mise à jour: Je me suis intéressé à comparer la vitesse des différentes solutions proposées ici, donc je mets ensemble le petit indice de référence suivant:

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

Mes commandes sont:

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

Mes résultats étaient les suivants:

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

Answer 1

Que diriez-vous ceci:

    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

Je soupçonne que la raison ne se définit pas transposée sur une liste « non rectangulaire » des listes est parce que mathématiquement l'opération de transposition est bien défini que sur les « structures rectangulaires ». Une propriété souhaitable d'une opération de transposition est que transposition (transposition (x)) == x. Ce n'est pas le cas dans votre généralisation de l'opération de transposition sur la liste non rectangulaire des listes.

De plus, jetez un oeil à mon poste sur Transposer arbitraire collection-of collections Scala et pensent à ce faire pour les collections-de-collections non rectangulaires. Vous finirez avec des définitions mathématiquement incohérentes, laisser les implémentations seuls.

Je suis d'accord que les opérations idiosyncrasique « transposent » sont souvent utiles, mais je pense aussi qu'ils ne devraient pas être mis à la disposition dans les bibliothèques standard en raison de la confusion possible au sujet de leurs définitions précises.

Answer 3

Je ne sais pas (et ne peux pas imaginer - est-ce pas un peu bizarre ?! [voir la discussion dans les commentaires]) une fonction de bibliothèque, mais je peux polir un peu le code:

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

Ceci est probablement le plus propre:

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 une version modifiée qui est encore plus efficace:

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'en est-ce une doublure en utilisant l'API standard de la Scala:

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

fait le travail et est O(N*M), où N est la longueur de la liste d'emballage et M est la longueur de la plus longue liste dans la liste d'emballage.