ritorno Scala il primo Alcuni in lista

Question

Ho una lista l:List[T1] e attualmente sto facendo il seguente:

myfun : T1 -> Option[T2]
val x: Option[T2] = l.map{ myfun(l) }.flatten.find(_=>true)

Il myfun funzione restituisce None o Alcuni, appiattirla butta via tutto il Nessuno dei rendimenti e trovare il primo elemento della lista se presente.

Questo sembra un po 'hacky per me. Im pensare che possa esistere un po 'per-di comprensione o simili che lo farà un po' meno dispendioso e più intelligente. Per esempio: non ho bisogno di risposte successivi se i rendimenti myfun qualsiasi Some durante la map della lista l

.

Answer 1

Come su:

l.toStream flatMap (myfun andThen (_.toList)) headOption

Stream è pigro, in modo da non mappare tutto in anticipo, ma non lo farà cose rimappare neanche. Invece di appiattire le cose, convertito Option a List in modo che flatMap può essere utilizzato.

Answer 2

Bene, questo è quasi, ma non del tutto

val x = (l flatMap myfun).headOption

Ma si restituisce un Option piuttosto che un List da myfun, quindi questo non può funzionare. Se è così (non ho REPL a mano) quindi provare invece:

val x = (l flatMap(myfun(_).toList)).headOption

Answer 3

Oltre a utilizzare toStream per rendere la ricerca pigri, siamo in grado di utilizzare Stream::collectFirst :

List(1, 2, 3, 4, 5, 6, 7, 8).toStream.map(myfun).collectFirst { case Some(d) => d }
// Option[String] = Some(hello)
// given def function(i: Int): Option[String] = if (i == 5) Some("hello") else None

Questa:

• Trasforma il List in un Stream al fine di interrompere la ricerca in anticipo.

• Trasforma elementi che utilizzano myFun come Option[T]s.

• raccoglie il primo elemento mappato che non è None ed estrarlo.

A partire Scala 2.13, con la disapprovazione di Streams a favore di LazyLists, questo sarebbe diventato:

List(1, 2, 3, 4, 5, 6, 7, 8).to(LazyList).map(function).collectFirst { case Some(d) => d }

Answer 4

Bene, il per-la comprensione equivalente è abbastanza facile

(for(x<-l, y<-myfun(x)) yield y).headOption

che, se effettivamente fare la traduzione funziona lo stesso di quello che ha dato oxbow_lakes. Assumendo ragionevole pigrizia di List.flatmap, questo è sia una soluzione pulita ed efficiente.

Answer 5

A partire dal 2017, le risposte precedenti sembrano essere superata. Ho eseguito alcuni benchmark (elenco di 10 milioni di Ints, prima partita all'incirca nel mezzo, Scala 2.12.3, Java 1.8.0, 1.8 GHz Intel Core i5). Se non diversamente specificato, list e map hanno i seguenti tipi:

list: scala.collection.immutable.List
map: A => Option[B]

Chiamate map sulla lista: ~ 1000 ms

list.map(map).find(_.isDefined).flatten

Per prima chiamata toStream della lista: ~ 1200 ms

list.toStream.map(map).find(_.isDefined).flatten

Chiamata toStream.flatMap sulla lista: ~ 450 ms

list.toStream.flatMap(map(_).toList).headOption

Chiamata flatMap sulla lista: ~ 100 ms

list.flatMap(map(_).toList).headOption

Per prima chiamata iterator della lista: ~ 35 ms

list.iterator.map(map).find(_.isDefined).flatten

funzione ricorsiva find(): ~ 25 ms

def find[A,B](list: scala.collection.immutable.List[A], map: A => Option[B]) : Option[B] = {
  list match {
    case Nil => None
    case head::tail => map(head) match {
      case None => find(tail, map)
      case result @ Some(_) => result
    }
  }
}

Funzione iterativo find(): ~ 25 ms

def find[A,B](list: scala.collection.immutable.List[A], map: A => Option[B]) : Option[B] = {
  for (elem <- list) {
    val result = map(elem)
    if (result.isDefined) return result
  }
  return None
}

Si può ulteriormente accelerare le cose utilizzando Java al posto di collezioni Scala e uno stile meno funzionale.

Loop oltre indici java.util.ArrayList: ~ 15 ms

def find[A,B](list: java.util.ArrayList[A], map: A => Option[B]) : Option[B] = {
  var i = 0
  while (i < list.size()) {
    val result = map(list.get(i))
    if (result.isDefined) return result
    i += 1
  }
  return None
}

Loop su indici java.util.ArrayList con funzione che restituisce null invece di None: ~ 10 ms

def find[A,B](list: java.util.ArrayList[A], map: A => B) : Option[B] = {
  var i = 0
  while (i < list.size()) {
    val result = map(list.get(i))
    if (result != null) return Some(result)
    i += 1
  }
  return None
}

(Naturalmente, si potrebbe solito dichiarare il tipo di parametro come java.util.List, non java.util.ArrayList Ho scelto la seconda qui perché è la classe che ho usato per i benchmark Altre implementazioni di java.util.List mostreranno prestazioni diverse -.. La maggior parte sarà peggio.)