Esiste un modo sicuro in Scala per trasporre un elenco di elenchi di lunghezza non uguale?

Question

Dato il seguente elenco:

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

Se cerco di trasposizione, Scala sarà buttare il seguente errore:

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

Questo perché List.transpose assume liste di uguale lunghezza e quindi utilizza il metodo 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 
} 

Vorrei ottenere le seguenti:

01.235.164,106 mila

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

Sta scrivendo la mia versione di transpose il modo migliore per farlo? Questo è ciò che mi si avvicinò con:

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 
} 

Aggiornamento: ero interessato a confrontare la velocità delle diverse soluzioni proposte qui, così ho messo insieme il seguente piccolo punto di riferimento:

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

mio i comandi sono stati:

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

I miei risultati sono stati:

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

Answer 1

ne dite di questo:

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

Non so (e non riesco a immaginare - non è un po 'strano ?! [Vedi la discussione nei commenti]) una funzione di libreria, ma posso lucidare il codice un po ':

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

Ho il sospetto che la ragione di trasposizione non è definito in un "non "rettangolare" lista di liste è perché matematicamente l'operazione di trasposizione è ben definita solo su "strutture rettangolari". Una proprietà desiderabile di un'operazione di trasposizione è quella trasposizione (transpose (x)) == x. Questo non è il caso della generalizzazione dell'operazione di trasposizione su un elenco non rettangolare di elenchi.

Inoltre, dai un'occhiata al mio post su Transposing arbitrary collection-of-collections in Scala e pensa a farlo per le collezioni non-rettangolari di collezioni. Finirai con definizioni matematicamente incoerenti, implementazioni da lasciare sole.

Sono d'accordo che le operazioni "transpose" idiosincratiche sono spesso utili, ma penso anche che non dovrebbero essere rese disponibili nelle librerie standard a causa della potenziale confusione riguardo alle loro definizioni precise.

Answer 4

Questo è probabilmente il più pulito:

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 versione modificata che è ancora più efficiente:

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

ne dite di questa one-liner utilizzando API standard della Scala:

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

Questo ha portato a termine il lavoro ed è O(N*M), dove N è la lunghezza dell'elenco wrapper e M è la lunghezza dell'elenco più lungo all'interno dell'elenco wrapper.