Читаемый FoldRight через FoldLeft в Scala - PullRequest
Новая
       24

Читаемый FoldRight через FoldLeft в Scala

2 голосов
/ 10 марта 2019

В Функциональное программирование в Scala , автор просит выразить FoldRight через FoldLeft.И тогда автор предлагает следующую реализацию : 

  def foldRightViaFoldLeftAuthor[A, B](l: List[A], z: B)(f: (A, B) => B): B = {
    foldLeft(l, (b: B) => b)((g, a) => b => g(f(a, b)))(z)
  }

Было несколько вопросов, таких как this с просьбой объяснить решение автора.И, вероятно, многие люди все еще пытаются понять это.

Пока я думал о задаче, я придумал другую реализацию, которая кажется гораздо более читабельной и легче понять, по крайней мере, для меня 

  def foldRightViaFoldLeftMy[A, B](l: List[A], z: B)(f: (A, B) => B): B = {
    foldLeft(l, z)(((g: (A, B) => B) => (b: B, a: A) => g(a, b)) (f))
  }

Итак, я в основном готовлю функцию, которая преобразует f(a,b) в f(b,a), и теперь я могу вызвать foldLeft, который является хвостово-рекурсивным.

Итак, мои вопросы:

  1. Есть ли основания для реализации так, как это сделал автор?
  2. Есть ли недостатки в моей реализации по сравнению с авторской?

1 Ответ

3 голосов
/ 10 марта 2019

Вы написали реализацию с такой же сигнатурой, как у foldRight, но у нее нет правильной семантики, когда операция объединения не является коммутативной.Возьмем один пример: сгиб вправо с пустым списком, равным нулю, и минусом в качестве операции объединения должен быть идентичен: 

scala> val input = List(1, 2, 3)
input: List[Int] = List(1, 2, 3)

scala> val f: (Int, List[Int]) => List[Int] = _ :: _
f: (Int, List[Int]) => List[Int] = $$Lambda$1912/991363637@5e9bf744

scala> foldRightViaFoldLeftAuthor(input, List.empty[Int])(f)
res0: List[Int] = List(1, 2, 3)

Но ваша реализация переворачивает список: 

scala> foldRightViaFoldLeftMy(input, List.empty[Int])(f)
res1: List[Int] = List(3, 2, 1)

Этопотому что вы все еще сворачиваете слева направо, даже если вы изменили порядок аргументов комбинированной функции.Я нахожу диаграммы на странице Википедии о fold полезными для визуализации различия.В вашей реализации приложения происходят так: 

scala> f(3, f(2, f(1, Nil)))
res2: List[Int] = List(3, 2, 1)

В то время как в реализации книги у вас есть что-то вроде этого: 

((b3: List[Int]) =>
  ((b2: List[Int]) =>
    ((b1: List[Int]) => identity(f(1, b1)))(f(2, b2)))(f(3, b3)
  )
)(Nil)

Что сводится к: 

scala> f(1, f(2, f(3, Nil)))
res3: List[Int] = List(1, 2, 3)

Итак, ответ на оба ваших вопроса «да», между вашей реализацией и книгой есть важное различие.

...