Geri izleme algoritması akışa nasıl dönüştürülür?

Question

Scala'da backtracking algoritması ile stream tanımlamak için herhangi bir yolu var mı? Örneğin, aşağıdaki backtracking algoritması, belirli bir boyuttaki tüm "ikili" dizeleri yazdırır.

def binaries(s:String, n:Int) { 
    if (s.size == n) 
    println(s) 
    else { 
    binaries(s + '0', n) 
    binaries(s + '1', n) 
    } 
}

ben başka yinelemeli algoritması kullanarak belirli bir boyutta "ikili" dizeleri bir stream tanımlayabilirsiniz inanıyoruz. Ancak yukarıdaki geri izleme algoritmasını yukarıdaki stream'a dönüştürebilir miyim merak ediyorum.

Answer 1

Bu oldukça düz ileri:

def binaries(s: String, n: Int): Stream[String] = 
    if (s.size == n) Stream(s) 
    else binaries(s + "0", n) append binaries(s + "1", n) 

Not append kullanımı - bu yöntemin diğeri için standart dışı olduğunu Bir gereksinim olan koleksiyonlar, kendi adına parametresini alması gerektiğinden.

Answer 2

yapabilirsiniz, ancak lazily değerlendirmek olmaz: Mesela

def bin(s: String, n: Int): Stream[String] = { 
    if (s.length == n) { 
    println("got " + s) // for figuring out when it's evaluated 
    Stream(s) 
    } else { 
    val s0 = s + '0' 
    val s1 = s + '1' 
    bin(s0, n) ++ bin(s1, n) 
    } 
} 

, bin("", 2).take(2).foreach(println) çalıştırırken, aşağıdaki çıktıyı alırsınız:

scala> bin("", 2).take(2).foreach(println) 
got 00 
got 01 
got 10 
got 11 
00 
01 

Eğer sakıncası yoksa TraversableView kullanarak, burada açıklanan dönüştürmeyi kullanabilirsiniz https://stackoverflow.com/a/3816012/257449. Öyleyse kod olur: Sonra

def toTraversable[T](func : (T => Unit) => Unit) = new Traversable[T] { 
    def foreach[X](f : T => X) = func(f(_) : Unit)      
} 

def bin2(str: String, n: Int) = { 
    def recurse[U](s: String, f: (String) => U) { 
    if (s.length == n) { 
     println("got " + s) // for figuring out when it's evaluated 
     f(s) 
    } else { 
     recurse(s + '0', f) 
     recurse(s + '1', f) 
    } 
    } 
    toTraversable[String](recurse(str, _)) view 
} 

scala> bin2("", 2).take(2).foreach(println) 
got 00 
00 
got 01 
01 
got 10