Как написать непротекающую хвостовую рекурсивную функцию, используя Stream.cons в Scala?

При написании функции, работающей на Stream(s), есть разные понятия рекурсии. Первый простой смысл не является рекурсивным на уровне компилятора, поскольку хвост, если не вычисляется мгновенно, поэтому функция возвращается немедленно, но возвращаемый поток является рекурсивным:

final def simpleRec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else someB(a.head) #:: simpleRec(a.tail)

Вышеупомянутое понятие рекурсии не вызывает никаких проблем. Второй действительно хвост рекурсивен на уровне компилятора:

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              // A) degenerated
  else if (someCond) rec(a.tail)           // B) tail recursion
  else someB(a.head) #:: rec(a.tail)       // C) degenerated

Проблема здесь в том, что C) регистр обнаруживает компилятор как не-tailrec-вызов, даже если фактический вызов не выполняется. Этого можно избежать, выделив хвост потока в вспомогательную функцию:

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else if (someCond) rec(a.tail)          // B)
  else someB(a.head) #:: recHelp(a.tail)  

@tailrec
final def recHelp[A](as: Stream[A]): Stream[B] = 
  rec(as)

В то время как это компилируется, этот подход в конечном счете приводит к утечке памяти. Так как хвост рекурсивный rec в конечном итоге вызывается из recHelp функция, кадр стека recHelp Функция хранит ссылку на поток пара и не позволяет собирать поток мусора до тех пор, пока rec возврат вызовов, который может быть довольно продолжительным (с точки зрения шагов рекурсии) в зависимости от количества вызовов на B),

Обратите внимание, что даже в случае без помощника, если компилятор разрешил @tailrec, утечка памяти все еще может присутствовать, так как ленивый хвост потока фактически создает анонимный объект, содержащий ссылку на заголовок потока.

Источник

2 ответа

Решение

Проблема, как вы намекали, заключается в том, что в коде, который вы вставили, функция filterHelp сохраняет голову (следовательно, ваше решение удаляет ее).

Лучший ответ - просто избежать этого удивительного поведения, использовать Scalaz EphemeralStream и увидеть, что он не слишком хорош и работает значительно быстрее, так как его гораздо лучше для gc. Не всегда так просто работать, например, head is a () => A not A, нет экстракторов и т. Д., Но все это направлено на одно целевое, надежное использование потока.

Ваша функция filterHelper, как правило, не заботится о том, хранит ли она ссылку:

import scalaz.EphemeralStream

@scala.annotation.tailrec
def filter[A](s: EphemeralStream[A], f: A => Boolean): EphemeralStream[A] = 
  if (s.isEmpty) 
    s
  else
    if (f(s.head())) 
      EphemeralStream.cons(s.head(), filterHelp(s.tail() , f) )
    else
      filter(s.tail(), f)

def filterHelp[A](s: EphemeralStream[A], f: A => Boolean) =
  filter(s, f)

def s1 = EphemeralStream.range(1, big)

Я бы сказал, что если у вас нет веских причин использовать Stream (другие зависимости от библиотек и т. Д.), А просто придерживаться EphemeralStream, то здесь сюрпризов гораздо меньше.

Источник

Возможный обходной путь - сделать recHelp метод не содержит ссылку на заголовок потока. Это может быть достигнуто путем передачи ему обернутого потока и изменения оболочки для удаления ссылки из него:

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else if (someCond) rec(a.tail)          
  else {
    // don't inline and don't define as def,
    // or anonymous lazy wrapper object would hold reference
    val tailRef = new AtomicReference(a.tail)
    someB(a.head) #:: recHelp(tailRef)  
  }

@tailrec
final def recHelp[A](asRef: AtomicReference[Stream[A]]): Stream[B] = 
  // Note: don't put the content of the holder into a local variable
  rec(asRef.getAndSet(null))

AtomicReference это просто удобство, атомарность в этом случае не требуется, подойдет любой простой объект-держатель.

Также обратите внимание, что с recHelp завернут в поток Cons хвост, поэтому он будет оцениваться только один раз, и Cons также заботится о синхронизации.

Источник
Другие вопросы по тегам