Scala данный список карт / фильтр / дубль без перебора всего списка

Question

Учитывая список элементов, мне нужно отобразить (получить ответ) / отфильтровать (проверить ответ действителен) / взять (взять только первые действительные n элементов) без перебора всего списка.

Например, яиметь список из 10 элементов.
1-й действительный
2-й недействительный
3-й действительный
4-й и последующие действительные

Пример кода

List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
    .map{x => println("Some req/res"); x}
    .filter{_ % 2 == 0} //filter for valid responses
    .take(3) //take first 3 valid ones

Я ожидаю, что println («Some req / res») будет печататься только 4 раза, но печатается все 20 раз.
Как получить первые n допустимых элементов, не просматривая весь список?

Прямо сейчас я использую цикл for со списком аккумуляторов и проверяю его размер, пока он не заполнится корректным ответом. Я ищу более функциональный подход.

Спасибо.

Answer 1

Вы хотите сделать результат коллекцией с ленивой оценкой. Один из простых способов сделать это - добавить .view.

val res = List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
  .view
  .map{x => println("Some req/res"); x}
  .filter{_ % 2 == 0} //filter for valid responses
  .take(3) //take first 3 valid ones
//res: scala.collection.View[Int] = View(<not computed>)

. Вы заметите, что теперь у вас нет вывода println(). Это потому, что результат еще не был «вынужденным». Но это все еще хороший результат, который вы можете обработать дальше.

Если просто хотите увидеть результат, есть много способов форсировать оценку. Вот простой.

res.toList
//Some req/res
//Some req/res
//Some req/res
//Some req/res
//Some req/res
//Some req/res
//res0: List[Int] = List(2, 4, 6)

Answer 2

, как говорили другие, и .map, и .filter нужно будет перебирать весь список.

Простой способ печати только 3 раза - изменить порядок ваших операций:

List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
    .filter{_ % 2 == 0} //filter for valid responses
    .take(3) //take first 3 valid ones
    .map{x => println("Some req/res"); x}

Таким образом, он будет печататься только 3 раза (но фильтр по-прежнему будет перебирать всю коллекцию

Если вы действительно хотите избежать перебора всего списка, попробуйте использовать коллекцию lazyНапример, Stream (если вы используете более новые версии scala, LazyList https://www.scala -lang.org / blog / 2018/06/13 / scala-213-collection.html # lazylist-is-предпочитаемый-Более-поток )

Answer 3

Если вы посмотрите на определение map или filter для List, каждая функция должна выполнить итерацию всего списка. В частности, для map он вернет новый List, полученный в результате применения данной функции f к каждому элементу этого списка и сбора результатов.

Затем map вернет новый список с тем жезначения в качестве исходного списка с побочным эффектом печати «Some req / res» один раз для каждого элемента.

res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)

scala>.map{x => println("Some req/res"); x}
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
Some req/res
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)

Затем filter создаст новый список, в который будут возвращены только элементы, соответствующие предикату.

scala> .filter{_ % 2 == 0}
res2: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

Наконец, take(3) создаст новый списокне более 3 элементов.

scala> .take (3)
res3: List[Int] = List(2, 4, 6)

Если вы хотите отложить эффекты map и filter, вам нужен другой тип данных. Вы можете использовать Stream в этом случае, но используйте окончательный toList, чтобы собрать результаты в список.

scala> List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20).toStream
res8: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> .map{x => println("Some req/res"); x}
Some req/res
res9: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> .filter{_ % 2 == 0}
Some req/res
res10: scala.collection.immutable.Stream[Int] = Stream(2, ?)

scala> .take(3)
res11: scala.collection.immutable.Stream[Int] = Stream(2, ?)

scala> .toList
Some req/res
Some req/res
Some req/res
Some req/res
res13: List[Int] = List(2, 4, 6)