6

有没有办法在 Scala stream中用算法定义 a ？backtracking

例如，以下backtracking算法打印给定大小的所有“二进制”字符串。

def 二进制文件(s:String, n:Int) {
  如果（s.size == n）
    println(s)
  别的 {
    二进制文件(s + '0', n)
    二进制文件(s + '1', n)
  }
}

我相信我可以使用另一种迭代算法定义stream给定大小的“二进制”字符串。但是我想知道我是否可以将上面的回溯算法转换为.stream

4

2 回答 2

11

这很简单：

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-- 这种方法对于其他集合来说是非标准的，这是一个要求，因为它必须按名称获取其参数。

于 2011-12-24T21:55:53.140 回答
3

你可以，但它不会懒惰地评估：

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

如果您不介意使用 aTraversableView您可以使用此处描述的转换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
于 2011-12-24T20:16:46.627 回答