Поток строк, соответствующих простому регулярному выражению в Scala

Question

Это продолжение моего предыдущего вопроса. Предположим, я хотел бы сделать Stream всех строк, соответствующих ^a+b+$ (один или несколько «а», а затем один или несколько «b»).

Я кодирования его следующим образом:

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

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

def as:Stream[String] = Stream.cons("a", as.map(_ + "a")) 

def bs:Stream[String] = Stream.cons("b", bs.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)) 

Таким образом генерировать будет рекурсивных не называть себя до 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>