Ленивое декартово произведение нескольких последовательностей в Scala

Question

Я реализовал простой метод генерации декартового произведения на нескольких Seq с подобным этому:

object RichSeq {
  implicit def toRichSeq[T](s: Seq[T]) = new RichSeq[T](s)
}

class RichSeq[T](s: Seq[T]) {

  import RichSeq._

  def cartesian(ss: Seq[Seq[T]]): Seq[Seq[T]] = {

    ss.toList match {
      case Nil        => Seq(s)
      case s2 :: Nil  => {
        for (e <- s) yield s2.map(e2 => Seq(e, e2))
      }.flatten
      case s2 :: tail => {
        for (e <- s) yield s2.cartesian(tail).map(seq => e +: seq)
      }.flatten
    }
  }
}

Очевидно, что это действительно медленно, так как он рассчитывает весь продукт сразу. Кто-нибудь реализовывал ленивое решение этой проблемы в Scala?

UPD

Хорошо, я реализовал глупую, но работающую версию итератора над декартовым произведением. Размещение здесь для будущих энтузиастов:

object RichSeq {
  implicit def toRichSeq[T](s: Seq[T]) = new RichSeq(s) 
}

class RichSeq[T](s: Seq[T]) {

  def lazyCartesian(ss: Seq[Seq[T]]): Iterator[Seq[T]] = new Iterator[Seq[T]] {

    private[this] val seqs = s +: ss

    private[this] var indexes = Array.fill(seqs.length)(0)

    private[this] val counts = Vector(seqs.map(_.length - 1): _*)

    private[this] var current = 0

    def next(): Seq[T] = {
      val buffer = ArrayBuffer.empty[T]
      if (current != 0) {
        throw new NoSuchElementException("no more elements to traverse")
      }
      val newIndexes = ArrayBuffer.empty[Int]
      var inside = 0
      for ((index, i) <- indexes.zipWithIndex) {
        buffer.append(seqs(i)(index))
        newIndexes.append(index)
        if ((0 to i).forall(ind => newIndexes(ind) == counts(ind))) {
          inside = inside + 1
        }
      }
      current = inside
      if (current < seqs.length) {
        for (i <- (0 to current).reverse) {
          if ((0 to i).forall(ind => newIndexes(ind) == counts(ind))) {
            newIndexes(i) = 0
          } else if (newIndexes(i) < counts(i)) {
            newIndexes(i) = newIndexes(i) + 1
          }
        }
        current = 0
        indexes = newIndexes.toArray
      }
      buffer.result()
    }

    def hasNext: Boolean = current != seqs.length
  }
}

Answer 1

Вот мое решение данной проблемы. Обратите внимание, что лень просто вызвана использованием .view в «корневой коллекции», используемой для понимания.

scala> def combine[A](xs: Traversable[Traversable[A]]): Seq[Seq[A]] =
     |  xs.foldLeft(Seq(Seq.empty[A])){
     |    (x, y) => for (a <- x.view; b <- y) yield a :+ b }
combine: [A](xs: Traversable[Traversable[A]])Seq[Seq[A]]
scala> combine(Set(Set("a","b","c"), Set("1","2"), Set("S","T"))) foreach (println(_))
List(a, 1, S)
List(a, 1, T)
List(a, 2, S)
List(a, 2, T)
List(b, 1, S)
List(b, 1, T)
List(b, 2, S)
List(b, 2, T)
List(c, 1, S)
List(c, 1, T)
List(c, 2, S)
List(c, 2, T)

Чтобы получить это, я начал с функции combine, определенной в https://stackoverflow.com/a/4515071/53974,, передав ей функцию (a, b) => (a, b). Однако это не совсем работало напрямую, так как этот код ожидает функцию типа (A, A) => A. Поэтому я просто немного адаптировал код.

Answer 2

Это может быть отправная точка:

• Декартово произведение двух списков
• Расширение набора [Set [String]] в декартово произведение в Scala
• https://stackoverflow.com/questions/6182126/im-learning-scala-would-it-be-possible-to-get-a-little-code-review-and-mentori

Answer 3

def cartesian[A](list: List[List[A]]): List[List[A]] = {
  list match {
    case Nil => List(List())
    case h :: t => h.flatMap(i => cartesian(t).map(i :: _))
  }
}

Answer 4

А как же:

  def cartesian[A](list: List[Seq[A]]): Iterator[Seq[A]] = {
    if (list.isEmpty) {
      Iterator(Seq())
    } else {
      list.head.iterator.flatMap { i => cartesian(list.tail).map(i +: _) }
    }
  }

Простой и ленивый;)

Answer 5

Вы можете посмотреть здесь: https://stackoverflow.com/a/8318364/312172 как перевести число в индекс всех возможных значений, не генерируя каждый элемент.

Этот метод может использоваться для реализации потока.