Семантика Scala Traversable, Iterable, Sequence, Stream и View?

Question

Существуют и другие вопросы, такие как Scala: в чем разница между чертами Traversable и Iterable в коллекциях Scala? и Как получить сумму квадратов двух списков в Scala? это частично отвечает на вопрос.Я чувствовал, что вопрос, который охватывает все это в одном месте, имеет смысл.

Answer 1

Traversable является вершиной иерархии коллекций.Его основной метод - foreach, поэтому он позволяет сделать что-то для каждого элемента коллекции.

Iterable может создать итератор, на основе которого можно реализовать foreach.Это определяет некоторый порядок элементов, хотя этот порядок может изменяться для каждого итератора.

Seq (uence) - это итерация, где порядок элементов фиксирован.Поэтому имеет смысл говорить об индексе элемента.

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

Представления являются нестрогими версиями коллекций.Такие методы, как filter и map on view, выполняют переданные функции только при доступе к соответствующему элементу.Таким образом, карта огромной коллекции немедленно возвращается, потому что она просто создает оболочку вокруг исходной коллекции.Только когда кто-то обращается к элементу, отображение фактически выполняется (для этого элемента).Обратите внимание, что View не является классом, но существует множество классов XxxView для различных коллекций.

Answer 2

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

Тем не менее, существует сложная проблема с «преждевременным выполнением», которая возникает при этом, чего можно избежать, используя итераторы, но не потоки, и в процессе указывает на важное семантическое различие между ними. Это, возможно, наиболее четко показано следующим образом:

def runiter(start: Int) {
  // Create a stream that returns successive integers on demand, e.g. 3, 4, 5, ....
  val iter = {
    def loop(v: Int): Stream[Int] = { println("I computed a value", v); v} #:: loop(v+1)
    loop(start)
  }
  // Now, sometime later, we retrieve the values ....
  println("about to loop")
  for (x <- iter) {
    if (x < 10) println("saw value", x) else return
  }
}

Этот код создает бесконечный поток, который начинается с заданного значения и возвращает последовательные целые числа. Он используется в качестве замены для более сложного кода, который может, например, открыть интернет-соединение и при необходимости вернуть значения из соединения.

Результат:

scala> runiter(3)
(I computed a value,3)
about to loop
(saw value,3)
(I computed a value,4)
(saw value,4)
(I computed a value,5)
(saw value,5)
(I computed a value,6)
(saw value,6)
(I computed a value,7)
(saw value,7)
(I computed a value,8)
(saw value,8)
(I computed a value,9)
(saw value,9)
(I computed a value,10)

Обратите внимание, как выполнение, необходимое для вычисления первого значения, происходит ДО того места, где значения потока фактически используются. Если это начальное выполнение включает, например, открытие файла или подключения к Интернету, и после создания потока и большой задержки после создания какого-либо значения это может быть очень проблематично - в результате вы получите открытый дескриптор файла. и, что еще хуже, ваше интернет-соединение может прерваться, что приведет к сбою.

Простая попытка исправить это с помощью исходного пустого потока не работает:

def runiter(start: Int) {
  // Create a stream that returns successive integers on demand, e.g. 3, 4, 5, ....
  val iter = {
    def loop(v: Int): Stream[Int] = { println("I computed a value", v); v} #:: loop(v+1)
    Stream[Int]() ++ loop(start)
  }
  // Now, sometime later, we retrieve the values ....
  println("about to loop")
  for (x <- iter) {
    if (x < 10) println("saw value", x) else return
  }
}

Результат (такой же, как и раньше):

scala> runiter(3)
(I computed a value,3)
about to loop
(saw value,3)
(I computed a value,4)
(saw value,4)
(I computed a value,5)
(saw value,5)
(I computed a value,6)
(saw value,6)
(I computed a value,7)
(saw value,7)
(I computed a value,8)
(saw value,8)
(I computed a value,9)
(saw value,9)
(I computed a value,10)

Однако вы можете исправить это, изменив поток на итератор с начальным пустым итератором, даже если далеко не очевидно, что это так:

def runiter(start: Int) {
  // Create an iterator that returns successive integers on demand, e.g. 3, 4, 5, ....
  val iter = {
    def loop(v: Int): Iterator[Int] = { println("I computed a value", v); Iterator(v)} ++ loop(v+1)
    Iterator[Int]() ++ loop(start)
  }
  // Now, sometime later, we retrieve the values ....
  println("about to loop")
  for (x <- iter) {
    if (x < 10) println("saw value", x) else return
  }
}

Результат:

scala> runiter(3)
about to loop
(I computed a value,3)
(saw value,3)
(I computed a value,4)
(saw value,4)
(I computed a value,5)
(saw value,5)
(I computed a value,6)
(saw value,6)
(I computed a value,7)
(saw value,7)
(I computed a value,8)
(saw value,8)
(I computed a value,9)
(saw value,9)
(I computed a value,10)

Обратите внимание, что если вы не добавите исходный пустой итератор, вы столкнетесь с той же проблемой преждевременного выполнения, что и с потоками.