बैकट्रैकिंग एल्गोरिदम को स्ट्रीम करने के लिए कैसे परिवर्तित करें?

Question

क्या stream को स्कैला में backtracking एल्गोरिदम के साथ परिभाषित करने का कोई तरीका है?

उदाहरण के लिए, निम्नलिखित backtracking एल्गोरिदम किसी दिए गए आकार के सभी "बाइनरी" तारों को प्रिंट करता है।

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

आप कर सकते हैं, लेकिन यह lazily का मूल्यांकन नहीं होगा:

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