Скала вернуться на первую строчку в списке - PullRequest
Новая
       20

Скала вернуться на первую строчку в списке

14 голосов
/ 05 сентября 2010

У меня есть список l:List[T1], и в настоящее время я делаю следующее: 

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

Функция myfun возвращает None или Some, flatten отбрасывает все None и find возвращает первый элемент списка, если таковой имеется.

Это кажется мне немного хакерским. Я думаю, что может быть какое-то понимание или что-то подобное, что сделает это менее расточительным или более умным. Например: мне не нужны никакие последующие ответы, если myfun возвращает any Some в течение map списка l.

Ответы [ 5 ]

12 голосов
/ 05 сентября 2010

Как насчет: 

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

Поток ленив, поэтому он не будет отображать все заранее, но и не будет заново отображать вещи.Вместо того, чтобы выравнивать вещи, конвертируйте Option в List, чтобы можно было использовать flatMap.

3 голосов
/ 05 сентября 2010

Ну, это почти, но не совсем 

val x = (l flatMap myfun).headOption

Но вы возвращаете Option вместо List от myfun, так что это может не сработать. Если это так (у меня нет REPL в руки), тогда попробуйте вместо этого: 

val x = (l flatMap(myfun(_).toList)).headOption
2 голосов
/ 02 октября 2018

В дополнение к использованию toStream, чтобы сделать поиск ленивым, мы можем использовать 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

Это:

  • Преобразует List в Stream, чтобы досрочно остановить поиск.

  • Преобразует элементы, используя myFun как Option[T] s.

  • Собирает первый сопоставленный элемент, который не является None, и извлекает его.

Начиная с Scala 2.13, с амортизацией Stream с в пользу LazyList с, это станет: 

List(1, 2, 3, 4, 5, 6, 7, 8).to(LazyList).map(function).collectFirst { case Some(d) => d }
2 голосов
/ 05 сентября 2010

Что ж, эквивалент для понимания довольно прост 

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

, который, если вы на самом деле делаете, перевод работает так же, как дал oxbow_lakes. Предполагая разумную лень List.flatmap, это чистое и эффективное решение.

0 голосов
/ 22 декабря 2017

По состоянию на 2017 год предыдущие ответы, похоже, устарели.Я провел несколько тестов (список из 10 миллионов Ints, первое совпадение примерно посередине, Scala 2.12.3, Java 1.8.0, 1,8 ГГц Intel Core i5).Если не указано иное, list и map имеют следующие типы: 

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

Просто позвоните map в списке: ~ 1000 мс 

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

Первый вызов toStream в списке: ~ 1200 мс 

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

вызов toStream.flatMap в списке: ~ 450 мс 

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

вызов flatMap в списке: ~ 100 мс 

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

Первый вызов iterator в списке: ~ 35 мс 

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

Рекурсивная функция find(): ~ 25 мс 

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

Итерационная функция find(): ~ 25 мс 

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
}

Вы можете еще больше ускорить процесс, используя Java вместо коллекций Scala и менее функциональный стиль.

Зацикливание индексов в java.util.ArrayList: ~ 15 мс

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
}

Зацикливание индексов в java.util.ArrayList с функцией, возвращающей null вместо None: ~ 10 мс 

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
}

(Конечно, обычно можно объявить параметрвведите как java.util.List, а не java.util.ArrayList. Я выбрал последний здесь, потому что это класс, который я использовал для тестов. Другие реализации java.util.List будут показывать другую производительность - большинство будет хуже.)

...