Kotlinの無限シーケンスの再帰的定義

Question

私はKotlinシーケンス、特に以前の値の簡単な計算ではない複雑なものを試しています。

私が定義したい1つの例は、すべての素数のシーケンスです。

次の素数を定義する簡単な方法は、シーケンス内の前の素数のいずれかで割り切れない次の整数です。私はKotlinにこれを翻訳する問題を抱えてい

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で

。スケーラでは、遅れて評価されるシーケンスを返す関数を渡すことができるので動作しますが、私はKotlinで同じことをすることはできません。 Kotlinで

私は

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の怠惰は、すべてのトリックを行います。otherIteratorがアクセスされた場合にのみotherGeneratorは、呼び出されますすなわち、第1のシーケンスが終了したときである。

さて、エラトステネスのふるいの再帰的な変種を書いてみましょう：

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()) 
} 

---

として表すことができます。 10,000素数の評価は数秒かかるが、1000秒素数は約0.1秒で放出される。

Answer 2

あなたはSequence<Sequence<Int>>発電機の内部で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

私の現在の回答は再帰関数を使用しないことです。私はまだ素数の無限のシーケンスを取得することができます。最初の素数と2番目の現在のフィルタリングされたシーケンスとの値のペアとしてシーケンスをモデリングすることによって、素数の無限シーケンスを得ることができます。私は最初の要素だけを選択するためにマップを適用します。

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}