역 추적 알고리즘을 스트림으로 변환하는 방법은 무엇입니까?

Question

stream을 스칼라에서 알고리즘으로 정의하는 방법이 있습니까?

예를 들어, 다음 backtracking 알고리즘은 주어진 크기의 모든 "2 진"문자열을 인쇄합니다.

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

은 내가 다른 반복 알고리즘을 사용하여 주어진 크기의 "이진"문자열 stream을 정의 할 수 있습니다 생각합니다. 그러나 알고리즘을 stream으로 역 추적 할 수 있는지 궁금합니다.

Answer 1

이 꽤 솔직하다 :

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

주 append의 사용 -이 방법은 다른 비 표준 이는 매개 변수별로 매개 변수를 가져와야하기 때문에 요구 사항입니다.

Answer 2

당신은 할 수 있지만,이 게으르게 평가하지 않습니다 예를 들어

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)을 실행하면 다음과 같은 출력을 얻을 것이다 :

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

당신이 괜찮다면 TraversableView을 사용하면 https://stackoverflow.com/a/3816012/257449에 설명 된 변환을 사용할 수 있습니다. 그럼 코드가된다 : 다음

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