Тип Scala, который является Iterable и имеет длину?

Question

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

С другой стороны, у меня есть функции «провайдера», которые генерируют коллекции и поэтому уже знают длину.Сгенерированные коллекции могут быть List[T], Array[T] или Set[T] и т. Д., Но даже в случае List[T] мой генератор знает размер (даже если тип List не сохраняет его).

Таким образом, я бы естественным образом объявил, что функции «процессора» принимают в качестве параметра наиболее общий тип, который, по-видимому, подходит для всех типов коллекций, Iterable[T].Тем не менее, им затем нужно внутренне определить размер с помощью итеративного обхода коллекции за счет O (N), что нежелательно.

Таким образом, мое наивное решение состояло бы в том, чтобы создать новый тип, такой как IterableWithSize[T], и заставить функции провайдера и процессора создавать и принимать этот тип.Ни Seq[T], ни IndexedSeq[T], кажется, не отвечают всем требованиям.Но это похоже на довольно распространенный вариант использования, поэтому я подозреваю, что есть более идиоматический способ сделать это.Что бы это было?

Answer 1

На самом деле, идиоматического пути нет. Коллекции Scala действительно предназначались для обхода или использования другими предписанными способами (такими как Set.contains или Map.get). Проверка размера не является частью их, а некоторые из них даже не являются конечными.

Теперь IndexedSeq - относительно безопасная ставка - она ​​гарантирует индексированный доступ O (logn), что возможно только при размере O (logn). Кроме того, Set и Map также достаточно безопасны по аналогичным причинам. Но если вы ищете черту, которая дает вам гарантию скорости size, ее нет.

Answer 2

В коллекциях Scala чувствительные к производительности методы, такие как size, не наследуются от признаков, а переопределяются в нижнем типе.Например, смотрите реализацию immutable.HashSet:

https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_0_1/src//library/scala/collection/immutable/HashSet.scala

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

Answer 3

Я не думаю, что есть идиоматический способ сделать это.Но вот две альтернативы:

(1) Расширить коллекции Scala's List / Set / Array и переопределить метод size.Это не так сложно, как кажется на первый взгляд.

(2) Оберните ваши коллекции List / Set / Array вместе с размером и определите неявный распаковщик, например:

class IterableWithSizeWrapper[E](private val c: Iterable[E], val size: Int)
object IterableWithSizeWrapper {
  implicit def unwrap[E](iws: IterableWithSizeWrapper[E]): Iterable[E] = iws.c
}

object ListWithSizeTest {

  def process[E](iws: IterableWithSizeWrapper[E]) {
        // iws.size uses your cached size value
        // iws.take(i) forces the unwrap to the original collect
        // so iws.take(i).size takes the calculated size
    for (i <- 0 to iws.size) assert(iws.take(i).size == i)
  }

  def main(args: Array[String]) {
    process(new IterableWithSizeWrapper(List(1,2,3), 3))
    process(new IterableWithSizeWrapper(Set(1,2,3), 3))
    process(new IterableWithSizeWrapper(Array(1,2,3), 3))
  }
}

Answer 4

Как насчет Traversable? Все упомянутые вами коллекции наследуются от него (Array косвенно через WrappedArray), и он обеспечивает size и toIterable (или toIterator) для обхода.

Answer 5

Функции вашего процессора должны принимать Seq[T].Seq - это точно Iterable, который "имеет длину".Ваша единственная оставшаяся проблема - сделать length эффективным.AFAIK уже эффективен во всех случаях, кроме List.Чтобы сделать List.length эффективным, просто сделайте так, как описывают другие: Создайте реализацию Seq, которая обернет List и сохранит его длину.