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

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

2 голосов
/ 17 декабря 2011

Это продолжение моего предыдущего вопроса. Предположим, я хотел бы сделать Stream из всех строк, соответствующих ^a+b+$ (одна или несколько "a", а затем одна или несколько "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)

Как бы вы исправили код выше? Вы бы предпочли другой способ решения проблемы?

Ответы [ 2 ]

2 голосов
/ 18 декабря 2011

Проблема в том, что для возможности вызова 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] =
2 голосов
/ 18 декабря 2011

Как насчет этого: 

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>
...