在Scala中匹配一个简单regexp的字符串流

Question

这是我上一个问题的后续问题。假设我想让所有匹配^a+b+$的字符串(一个或多个"a"，然后一个或多个"b")的Stream。

我将其编码如下:

<>之前def interleave(s1:Stream[String]， s2:Stream[String]): Stream[String] =if (s1. isempty) s2 else流。头部，交织(s2, s1.tail))def generate(s1:Stream[String]， s2:Stream[String]): Stream[String] = .使用实例if (s1. isempty) s1 else interleave(s2.map(s1. isempty))头+ _)，生成(s1。尾巴,s2))def:Stream[String] = Stream。缺点("一个"。Map(_ +"a")def:Stream[String] = Stream。缺点("b",废话。Map (_ + "b"))Def solve = generate(as, bs)之前

不幸的是，solve与out of memory失败。然而，它可以很好地用于有限流:例如solve(as take 10, bs take 10)

你会如何修复上面的代码?你喜欢另一种方法来解决这个问题吗?

Answer 1

问题是，为了能够调用interleave，必须计算generate:

def generate(s1:Stream[String], s2:Stream[String]): Stream[String] =
  if (s1.isEmpty) ... else interleave(..., generate(s1.tail, s2))

因此generate将递归调用自身直到s1.isEmpty，此时它将最终调用所有挂起的interleave .由于s1是无限的，因此它永远不会为空。

如果将interleave的第二个参数转换为按名称参数，则递归可以延迟:

def interleave(s1:Stream[String], s2: => Stream[String]): Stream[String] =

Answer 2

这个怎么样:

scala> val asbs = for(n <- Stream.from(2);k <- 1 until n) yield "a"*k + "b"*(n-k)
asbs: scala.collection.immutable.Stream[String] = Stream(ab, ?)
scala> asbs.take(10).toList
res0: List[String] = List(ab, abb, aab, abbb, aabb, aaab, abbbb, aabbb, aaabb, aaaab)
scala>