Рекурсивное определение бесконечной последовательности в Котлине

Question

Я экспериментирую с последовательностями Kotlin и, в частности, более сложными, которые не являются простыми вычислениями по предыдущему значению.

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

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

В Scala это можно перевести:

def primeStream(s: Stream[Int]): Stream[Int] = s.head #:: primeStream(s.tail filter(_ % s.head != 0)) 
val primes = primeStream(Stream.from(2)) 

// first 20 primes 
primes.take(20).toList 

У меня возникли проблемы перевод это Котлин. В scala это работает, потому что вы можете передать функцию, которая возвращает последовательность, которая будет лениво оценена, но я не могу сделать то же самое в Котлине.

В Котлин я попытался

fun primes(seq: Sequence<Int>):Sequence<Int> = sequenceOf(seq.first()) + primes(seq.drop(1).filter {it % seq.first() != 0}) 
val primes = primes(sequence(2) {it + 1}) 

primes.take(20).toList() 

Но это, очевидно, не работает, потому что функция вычисляется сразу и приводит к бесконечной рекурсии.

Answer 1

Ключевым моментом здесь является то, чтобы реализовать Sequence преобразование так, чтобы его первый элемент остается и хвост лениво трансформироваться из оригинального Sequence хвоста к чему-то еще. То есть преобразование выполняется только при запросе элемента.

Во-первых, давайте реализуем ленивую последовательность конкатенации, которая ведет себя как простой конкатенации, но правый операнд лениво:

public infix fun <T> Sequence<T>.lazyPlus(otherGenerator:() -> Sequence<T>) = 
     object : Sequence<T> { 
      private val thisIterator: Iterator<T> by lazy { this@lazyPlus.iterator() } 
      private val otherIterator: Iterator<T> by lazy { otherGenerator().iterator() } 

      override fun iterator() = object : Iterator<T> { 
       override fun next(): T = 
         if (thisIterator.hasNext()) 
          thisIterator.next() 
         else 
          otherIterator.next() 

       override fun hasNext(): Boolean = 
         thisIterator.hasNext() || otherIterator.hasNext() 
      } 
     } 

лени otherIterator делает всю хитрость: otherGenerator будет называться только тогда, когда otherIterator доступ, то есть, когда заканчивается первая последовательность.

Теперь давайте напишем рекурсивный вариант решета Эратосфена:

fun primesFilter(from: Sequence<Int>): Sequence<Int> = from.iterator().let { 
     val current = it.next() 
     sequenceOf(current) lazyPlus { 
      primesFilter(it.asSequence().filter { it % current != 0 }) 
     } 
    } 

Обрати внимание, что lazyPlus позволило нам лениво сделать еще один рекурсивный вызов primesFilter в хвосте последовательности.

После этого вся последовательность простых чисел может быть выражена как

fun primes(): Sequence<Int> { 
    fun primesFilter(from: Sequence<Int>): Sequence<Int> = from.iterator().let { 
     val current = it.next() 
     sequenceOf(current) lazyPlus { 
      primesFilter(it.asSequence().filter { it % current != 0 }) 
     } 
    } 
    return primesFilter((2..Int.MAX_VALUE).asSequence()) 
} 

---

Хотя этот подход не очень быстро. Оценка 10000 простых чисел занимает несколько секунд, однако 1000-й штрих испускается примерно через 0,1 секунды.

Answer 2

Вы можете разместить Sequence<Int> конкатенации внутри Sequence<Sequence<Int>> генератора, а затем расплющить его в Sequence<Int> снова:

fun primes(seq: Sequence<Int>): Sequence<Int> = sequence { 
    seq.take(1) + primes(seq.drop(1).filter { it % seq.first() != 0 }) 
}.flatMap { it } 
val primes = primes(sequence(2) { it + 1 }) 

Выход: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Это кажется немного медленно, хотя. Вероятно, вам нужно кэшировать каждый результат в списке и строить его, вместо того, чтобы пересчитывать простые числа рекурсивно. например:

fun primes() = with(arrayListOf(2, 3)) { 
    asSequence() + sequence(last() + 2) { it + 2 } 
      .filter { all { prime -> it % prime != 0 } } 
      .map { it.apply { add(it) } } 
} 

Answer 3

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

val primes = sequence(2 to sequence(3) {it + 2}) { 
    val currSeq = it.second 
    val nextPrime = currSeq.first() 
    nextPrime to currSeq.filter { it % nextPrime != 0} 
}.map {it.first}