Lazy foldПравильная путаница с ранним завершением

Изучая Функциональное программирование на Scala, я наткнулся на следующий фрагмент кода:

def foldRight[A](z: => B)(f: (A,=>B) => B):B = uncons match {
  case Some((h,t)) => f(h,t.foldRight(z)(f))
  case None => z 
}

Затем авторы идут дальше и заявляют следующее:

Это выглядит очень похоже на foldRight, который мы написали для List, но обратите внимание, что наша функция объединения f не является строгой по второму параметру. Если f решает не оценивать свой второй параметр, обход завершается досрочно. Мы можем увидеть это, используя foldRight для реализации exists, которая проверяет, соответствует ли какое-либо значение в потоке заданному предикату.

Далее автор сообщает следующее:

def exists(p: A => Boolean): Boolean =
  foldRight(false)((a, b) => p(a) || b)

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


scala functional-programming lazy-evaluation fold
person sc_ray    schedule 27.06.2013    source источник

Ответы (1)


arrow_upward
7
arrow_downward

В f(h,t.foldRight(z)(f)) первым аргументом, предоставленным f, является h, вторым аргументом является t.foldRight(z)(f). Способ определения foldRight заключается в том, что второй аргумент его аргумента f является аргументом по имени, который не будет оцениваться до тех пор, пока он не понадобится (и будет оцениваться каждый раз, когда это необходимо). Таким образом, в f: (A, =>B) => B первый аргумент типа A является обычным аргументом, а второй аргумент типа B является аргументом по имени.

Итак, представьте, что вы определили f следующим образом:

f(a: A, b: => Boolean): Boolean = predicate(a) || b

Если predicate(a) истинно, то b никогда не понадобится и никогда не будет оцениваться. Так работает оператор или.

Так сказать для exists применительно к некоторым Stream. Чтобы исключить первый элемент, который будет существовать (где p(h) равно true), этот код:

uncons match {
  case Some((h,t)) => f(h,t.foldRight(z)(f))
  case None => z 
}

Такой же, как этот код (мы предполагаем, что у нас есть непустой поток, поэтому мы можем удалить второй случай):

f(h,t.foldRight(z)(f))

Что тогда эквивалентно (расширение f):

p(h) || t.foldRight(z)(f)

Но p(h) верно, так что:

true || t.foldRight(z)(f)

И это то же самое, что просто true и не нужно продолжать вызывать foldRight, поэтому происходит досрочное завершение!

person huynhjl    schedule 27.06.2013
comment
@huynhji - имеет смысл. Спасибо! - person sc_ray; 27.06.2013