Является ли это foldRight для реализации Streams ленивым или строгим? - PullRequest
Новая
       75

Является ли это foldRight для реализации Streams ленивым или строгим?

3 голосов
/ 19 сентября 2019

Я читаю Функциональное программирование в Scala и занимаюсь 5-й главой, посвященной строгости и лени.Я выполнил все задачи в книге до 5.13.

Одна вещь, которую я понял, работая над проблемами, заключалась в том, что я не понимал все нюансы foldRight, пока не начал заниматься проблемами.в этой главе.Мой вопрос касается реализации foldRight, приведенной в этой главе.

Давайте начнем с рассмотрения реализации потоков, приведенной в этой главе. 

import Stream._
trait Stream[+A] {

  def toList: List[A] = this match {
    case Empty => Nil
    case Cons(h, t) => h() :: t().toList
  }

  def foldRight[B](z: => B)(f: (A, => B) => B): B = // The arrow `=>` in front of the argument type `B` means that the function `f` takes its second argument by name and may choose not to evaluate it.
    this match {
      case Cons(h,t) => f(h(), t().foldRight(z)(f)) // If `f` doesn't evaluate its second argument, the recursion never occurs.
      case _ => z
    }

  def map[B](f: A => B): Stream[B] =
    foldRight(empty[B])((h,t) => cons(f(h), t))

  def filter(f: A => Boolean): Stream[A] =
    foldRight(empty[A])((h,t) =>
      if (f(h)) cons(h, t)
      else t)
}

case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }

  def empty[A]: Stream[A] = Empty

  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty
    else cons(as.head, apply(as.tail: _*))
}

В частности, давайте увеличим масштабОпределение foldRight дано здесь: 

  def foldRight[B](z: => B)(f: (A, => B) => B): B = // The arrow `=>` in front of the argument type `B` means that the function `f` takes its second argument by name and may choose not to evaluate it.
    this match {
      case Cons(h,t) => f(h(), t().foldRight(z)(f)) // If `f` doesn't evaluate its second argument, the recursion never occurs.
      case _ => z
    }

Из текста в книге мы знаем, что эта реализация foldRight не будет оценивать второй аргумент функции "chain", если она не вызывается.Следовательно, foldRight может завершиться досрочно, прежде чем оценивать все элементы Stream.Рассмотрим эту реализацию takeWhile в терминах foldRight в качестве примера: 

  def takeWhile(f: A => Boolean): Stream[A] =
    foldRight(empty[A])((h,t) =>
      if (f(h)) cons(h,t)
      else      empty)

Этот вызов foldRight в определении takeWhile может завершиться рано, прежде чем пройти через все элементы потока.Итак, мы знаем, что foldRight может закончиться рано.Однако это не то же самое, что сказать, что foldRight ленив.Мой вопрос заключается в том, является ли эта реализация foldRight самой ленивой или строгой.То есть, применяется ли f к каждому соответствующему элементу в потоке?

Например, давайте возьмем такой пример: 

val someStream = Stream.apply(0, 1, 2, 3, 5)
someStream.foldRight(Empty:Stream[Int]){ (e, acc) =>
  Cons(()=>e, ()=>acc)
}

Что обычно делает этот вызов foldRight дляНе ленивая коллекция, такая как список, состоит в том, что он будет копировать список.Однако для этого вызова someStream он создаст копию всех членов потока?Или он будет оценивать только первый член?

Напомним, что функция в foldRight имеет следующую сигнатуру: (A, => B) => B.Мой вопрос действительно сводится к тому, когда acc, второй аргумент вызова по имени типа B, оценивается.Оценивается ли он при первом вызове f?Или acc оценивается при оценке ()=>acc?В зависимости от того, какой это будет, мы будем либо оценивать всех членов потока, либо только первого, когда выполняем сворачивание.

И еще раз повторяем, говоря, что foldRight заканчивается рано, и говоря, что foldRight является ленивымэто две разные вещи.Обсуждение в книге дает понять, что первое утверждение может быть правдой.Это foldRight может закончиться рано, не пересекая все элементы потока.Но верно ли второе утверждение?Неужели у нас тут ленивые права?

Я поднял этот вопрос, потому что на странице 72 есть трассировка программы, которую, я думаю, я не до конца понимаю.Это связано с тем, является ли foldRight самим ленивым или нет. 

Stream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).toList
cons(11, Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0).toList
Stream(2,3,4).map(_ + 10).filter(_ % 2 == 0).toList
cons(12, Stream(3,4).map(_ + 10)).filter(_ % 2 == 0).toList
12 :: Stream(3,4).map(_ + 10).filter(_ % 2 == 0).toList
12 :: cons(13, Stream(4).map(_ + 10)).filter(_ % 2 == 0).toList
12 :: Stream(4).map(_ + 10).filter(_ % 2 == 0).toList
12 :: cons(14, Stream().map(_ + 10)).filter(_ % 2 == 0).toList
12 :: 14 :: Stream().map(_ + 10).filter(_ % 2 == 0).toList
12 :: 14 :: List()

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

Итак, давайте подведем итог моего вопроса:

1) Является ли foldRight в реализации заданным ленивым или строгим?Этот вопрос отличается от того, завершается ли он раньше.

2) Для следующего примера кода: 

val someStream = Stream.apply(0, 1, 2, 3, 5)
someStream.foldRight(Empty:Stream[Int]){ (e, acc) =>
  Cons(()=>e, ()=>acc)
}

Когда оценивается acc, параметр call-by-name?Это когда f вызывается и (e, acc) => Cons(()=>e, ()=>acc) создается впервые?Или это когда ()=>acc оценивается?

3) Пожалуйста, объясните, почему в данной трассировке программы первый член проходит через карту и фильтруется первым, прежде чем перейти ко второму.

Вам предлагается использовать текст Функциональное программирование в Scala , чтобы высказать свою точку зрения.

...