FoldLeft с использованием FoldRight в scala

Ответ 1

Посмотрим на

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

(другая справка похожа). Фокус в том, что во время операции правой складки мы не строим окончательное значение типа B. Вместо этого мы строим функцию от B до B. Шаг сбрасывания принимает значение типа a: A и функцию g: B => B и создает новую функцию (b => g(f(b,a))): B => B. Эта функция может быть выражена как композиция g с f(_, a):

  l.foldRight(identity _)((a,g) => g compose (b => f(b,a)))(z);

Мы можем просмотреть процесс следующим образом: для каждого элемента a of l мы берем частичное приложение b => f(b,a), которое является функцией B => B. Затем мы составляем все эти функции таким образом, чтобы функция, соответствующая самому правому элементу (с которым мы начинаем обход), находится в левом конце композиции. Наконец, мы применяем большую сложенную функцию на z. Это приводит к последовательности операций, которая начинается с самого левого элемента (который находится далеко справа в цепочке композиций) и заканчивается правым большинством.

Обновление: В качестве примера рассмотрим, как это определение работает в двухэлементном списке. Во-первых, мы перепишем функцию как

def foldLeftViaFoldRight[A,B](l: List[A], z: B)
                             (f: (B,A) => B): B =
{
  def h(a: A, g: B => B): (B => B) =
    g compose ((x: B) => f(x,a));
  l.foldRight(identity[B] _)(h _)(z);
}

Теперь давайте вычислим, что происходит, когда мы передаем его List(1,2):

List(1,2).foldRight(identity[B] _)(h _)
  = // by the definition of the right fold
h(1, h(2, identity([B])))
  = // expand the inner `h`
h(1, identity[B] compose ((x: B) => f(x, 2)))
  =
h(1, ((x: B) => f(x, 2)))
  = // expand the other `h`
((x: B) => f(x, 2)) compose ((x: B) => f(x, 1))
  = // by the definition of function composition
(y: B) => f(f(y, 1), 2)

Применение этой функции к z дает

f(f(z, 1), 2)

по мере необходимости.

Ответ 2

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

val f = (a: Int, b: Int) => a+b
val list = List(2,3,4)
println(list.foldLeft(1)(f))

val f1 = (b: Int) => f(b, 2)
val f2 = (b: Int) => f(b, 3)
val f3 = (b: Int) => f(b, 4)
val f4 = (b: Int) => b

val ftotal = f1 andThen f2 andThen f3 andThen f4
println(ftotal(1))

Вы можете представить это как связанный список объектов функций. Когда вы передаете значение, оно "течет" через все функции. Это немного похоже на программирование потока данных.

Ответ 3

Я только что сделал это упражнение и хотел бы поделиться тем, как я пришел к ответу (в основном то же, что и в вопросе, только буквы разные), в надежде, что это может быть полезно кому-то.

В качестве фона, давайте начнем с того, что делают foldLeft и foldRight. Например, результат foldLeft в списке [1, 2, 3] с операцией * и начальным значением z является значением ((z * 1) * 2) * 3

Мы можем думать о foldLeft как о потребляющих значениях списка поэтапно, слева направо. Другими словами, мы сначала начинаем со значения z (что будет результатом, если список пуст), затем мы показываем foldLeft, что наш список начинается с 1, а значение становится z * 1, затем foldLeft наш следующий список имеет 2, и значение становится (z * 1) * 2, и, наконец, после действия на 3 оно становится значением ((z * 1) * 2) * 3.

                             1    2    3
Initially:               z
After consuming 1:      (z * 1)
After consuming 2:     ((z * 1) * 2
After consuming 3:    (((z * 1) * 2) * 3

Это конечное значение - это значение, которое мы хотим достичь, за исключением (как это требует нас упражнение) с использованием foldRight. Обратите внимание, что так же, как foldLeft потребляет значения списка слева направо, foldRight потребляет значения списка справа налево. Итак, в списке [1, 2, 3],

• Это foldRight будет действовать на 3 и [что-то], давая [результат]
• Затем он будет действовать на 2 и [результат], давая [result2]
• Наконец, он будет действовать на 1 и [result2], давая окончательное выражение
• Мы хотим, чтобы наше окончательное выражение было (((z * 1) * 2) * 3

Другими словами: используя foldRight, мы сначала получаем результат, если бы список был пустым, а затем результат, если список содержал только [3], тогда результат, если список был [2, 3 ] и, наконец, результат для списка [1, 2, 3].

То есть, это значения, которые мы хотели бы получить, используя foldRight:

                             1    2    3
Initially:                             z
After consuming 3:                 z * 3
After consuming 2:           (z * 2) * 3
After consuming 1:     ((z * 1) * 2) * 3

Итак, нам нужно перейти от z в (z * 3) к (z * 2) * 3 в ((z * 1) * 2) * 3.

В качестве значений мы не можем этого сделать: нет естественного способа перейти от значения (z * 3) к значению (z * 2) * 3 для произвольной операции *. (Существует для умножения как коммутативный и ассоциативный, но мы используем * для обозначения произвольной операции.)

Но как функции мы можем это сделать! Нам нужно иметь функцию с "заполнителем" или "дыркой": что-то, что займет z и поместит ее в нужное место.

• например. после первого шага (после действия на 3) мы имеем функцию-заполнитель z => (z * 3). Вернее, поскольку функция должна принимать произвольные значения, и мы использовали z для определенного значения, напишите это как t => (t * 3). (Эта функция, примененная на входе z, дает значение (z * 3).)
• После второго шага (после действия на 2 и результата) у нас есть функция-заполнитель t => (t * 2) * 3 может быть?

Можно ли перейти от первой функции-заполнителя к следующей? Пусть

      f1(t) = t * 3
and   f2(t) = (t * 2) * 3

Что такое f2 в терминах f1?

f2(t) = f1(t * 2)

Да, мы можем! Поэтому требуемая функция принимает 2 и f1 и дает f2. Позвольте называть это g. Мы имеем g(2, f1) = f2 где f2(t) = f1(t * 2) или, другими словами,

g(2, f1) = 
    t => f1(t * 2)

Посмотрим, будет ли это работать, если мы перенесем его вперед: следующим шагом будет g(1, f2) = (t => f2(t * 1)), а RHS будет таким же, как t => f1((t * 1) * 2)) или t => (((t * 1) * 2) * 3).

Похоже, он работает! И, наконец, мы применим к этому результату z.

Каким должен быть начальный шаг? Применим g к 3 и f0, чтобы получить f1, где f1(t) = t * 3, как определено выше, а также f1(t) = f0(t * 3) из определения g. Похоже, нам нужна f0 функция тождества.

Пусть начнется заново.

Our foldLeft(List(1, 2, 3), z)(*) is ((z * 1) * 2) * 3
Types here: List(1, 2, 3) is type List[A]
             z is of type B
             * is of type (B, A) -> B
             Result is of type B
We want to express that in terms of foldRight
As above:
 f0 = identity. f0(t) = t.
 f1 = g(3, f0). So f1(t) = f0(t * 3) = t * 3
 f2 = g(2, f1). So f2(t) = f1(t * 2) = (t * 2) * 3
 f3 = g(1, f2). So f3(t) = f2(t * 1) = ((t * 1) * 2) * 3

И, наконец, мы применим f3 на z и получим требуемое выражение. Все работает. Итак,

f3 = g(1, g(2, g(3, f0)))

что означает f3 = foldRight(xs, f0)(g)

Определим g, на этот раз вместо x * y, используя произвольную функцию s(x, y):

• first arg to g имеет тип A
• second arg to g относится к типу этих f, которые B => B
• Таким образом, тип g равен (A, (B=>B)) => (B=>B)

• Итак, g:

  def g(a: A, f: B=>B): B=>B = 
      (t: B) => f(s(t, a))
  

Объединяя все это

def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B = {
    val f0 = (b: B) => b

    def g(a: A, f: B=>B): B=>B =
        t => f(s(t, a))

    foldRight(xs, f0)(g)(z)
}

На этом уровне работы над книгой я действительно предпочитаю эту форму, поскольку она более ясна и понятна. Но чтобы приблизиться к форме решения, мы можем встраивать определения f0 и g (нам больше не нужно объявлять тип g при вводе в foldRight, а компилятор его выводит), давая:

def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B =
  foldRight(xs, (b: B) => b)((a, f) => t => f(s(t, a)))(z)

что и есть вопрос, только с разными символами. Аналогично для foldRight в терминах foldLeft.

Ответ 4

Авторы книги дают хорошее объяснение на странице github/fpinscala.