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

Question

Проходя Functional Programming in Scala, я наткнулся на этот вопрос:

Можете ли вы право foldLeft с точки зрения foldRight? Как насчет другого способа вокруг?

В растворе, представленный авторы, они обеспечили реализацию следующим образом:

def foldRightViaFoldLeft_1[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) 

    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) 

Может кто-нибудь помочь мне проследить через это решение и заставить меня понять, как это на самом деле получает foldl, реализованный в терминах foldr и наоборот?

Благодаря

Answer 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. Эта функция может быть выражена в виде композиции с gf(_, a):

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

Мы можем рассматривать процесс следующим образом: Для каждого элемента a из 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) 

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

Answer 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)) 

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

Answer 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 и положите его в нужное место.

• E.g. после первого шага (после действия на 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 

Что с точки зрения f1f2?

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)) и ОРЗ таких же, как 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):

• первый аргумент к g имеет тип A
• второй 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.

Answer 4

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