Попытка заставить ленивую оценку работать на бесконечный поток - PullRequest
Новая
       20

Попытка заставить ленивую оценку работать на бесконечный поток

3 голосов
/ 12 апреля 2019

Я пытаюсь реализовать бесконечный поток с помощью операции фильтра. Я хочу, чтобы он не зависал с ошибкой переполнения стека, используя ленивую оценку для хвоста. 

abstract class MyStream[+A] {
  def head: A
  def tail: MyStream[A]

  def #::[B >: A](element: B): MyStream[B] // prepend operator

  def filter(predicate: A => Boolean): MyStream[A]
}

class FiniteStream[+A](val head: A, val tail: MyStream[A]) extends MyStream[A] {    
  override def #::[B >: A](element: B): MyStream[B] = new FiniteStream[B](element, this)

  override def filter(predicate: A => Boolean): MyStream[A] = {
    lazy val filteredTail = tail.filter(predicate)
    if (predicate(head)) filteredTail
    else filteredTail
  }
}

class InfiniteStream[+A](override val head: A, generator: A => A) extends MyStream[A] {
  override def tail: MyStream[A] = {
    lazy val tail = new InfiniteStream[A](generator(head), generator)
    tail
  }

  override def #::[B >: A](element: B): MyStream[B] =
    new FiniteStream[B](element, this)

  override def filter(predicate: A => Boolean): MyStream[A] = {
    lazy val filteredTail = tail.filter(predicate)
    if (predicate(head)) head #:: filteredTail
    else filteredTail
  }
}

object MyStream {
    def from[A](start: A)(generator: A => A): MyStream[A] = new InfiniteStream[A](start, generator)
}

val stream: MyStream[Int] = MyStream.from(1)((n: Int) => n + 1)
val filtered = stream.filter(_ % 2 == 0)

Но эта программа действительно завершается с ошибкой переполнения стека. Кажется, моя стратегия ленивых оценок не работает. Хвост все еще оценивается. Почему?

1 Ответ

6 голосов
/ 12 апреля 2019

Проблема вызвана InfiniteStream.filter, он создает хвостовой фильтр как ленивое значение, но затем немедленно обращается к нему, что вынуждает оценить значение.Это приводит к тому, что весь поток оценивается как рекурсивные вызовы, взрывающие стек.

Ленивый val задерживает выполнение выражения, используемого для создания переменной, до тех пор, пока к ней не будет получен доступ.Поэтому вам нужно отложить доступ к tail.filter(predicate) до тех пор, пока пользователь потока не получит доступ к хвосту.

Самый простой и более функциональный способ добиться этого - реализовать фильтр с представлением.То есть фильтр возвращает новый поток, который фильтрует только хвост по требованию.

EG 

class FilterStream[+A] private (predicate: predicate: A => Boolean, stream: MyStream) extends MyStream[A] {
  override def head: A = stream.head
  override def tail: MyStream[A] = FilterStream.dropWhile(!predicate(_), stream)
}


object FilterStream {
  def apply[A](predicate: predicate: A => Boolean, stream: MyStream[A]): MyStream[A] = {
    new FilterStream(predicate, dropWhile(!predicate(_), stream))
  }

  @tailrec
  def dropWhile[A](predicate: predicate: A => Boolean, stream: MyStream[A]): MyStream[A] = {
    if (stream.isEmpty || predicate(stream.head)) stream
    else dropWhile(predicate, stream.tail)
  }
}

Наконец, вы должны рассмотреть возможность реализации пустого потока со своим собственным типом и объектом по многим причинам, но такжетак что вы можете завершить бесконечный поток, если ваш generator решит, что он хочет. 

object Nil extends MyStream[Nothing] {
  override def head: A = throw NoSuchElement
  override def tail: MyStream[A] = throw NoSuchElement
}

Голова и хвост всегда небезопасные методы, еще одним улучшением было бы использование классов case для раскрытия формы вашего потока.тогда пользователи будут сопоставлять паттерны в потоке.Это защитит ваших пользователей от необходимости использовать небезопасные методы, такие как head и tail.

...