How to convert a back-tracking algorithm to a stream?

Question

Is there a way to define stream with backtracking algorithm in Scala?

For example, the following backtracking algorithm prints all binary lines of a given size.

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

I believe that I can determine the stream "binary" strings of a given size using another iterative algorithm. However, I am wondering if I can convert the backtracking algorithm above to stream .

Answer 1

This is pretty straight forward:

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

Pay attention to the use of append - this method is non-standard for other collections, which is a mandatory requirement, since it must take its parameter by name.

Answer 2

You can, but he will not lazily evaluate:

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

For example, when executing bin("", 2).take(2).foreach(println) you get the following output:

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

If you are not opposed to using TraversableView , you can use the conversion fooobar.com/questions/393853 / ... described here. Thus, the code will look like this:

 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 evaluated f(s) } else { recurse(s + '0', f) recurse(s + '1', f) } } toTraversable[String](recurse(str, _)) view } 

Then

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