Описание первых нескольких шагов оценки данной функции свёртывания

Question

Дана следующая функция:

mystery a b c xs = 
  foldr (\x rec a b -> rec x (b + c)) (\a b -> a + b - c) xs a b

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

mystery 1 2 3 [1, 2, 3]

Особенно использование rec доставляет мне трудности. Я предполагаю, что один из последних шагов выглядит так:

(\a b -> 3 + (b + 3 + 3 + 3) - 3) [] 1 2

Таким образом, на выходе получается 11. Может ли кто-нибудь описать первые несколько шагов казни? Что происходит после:

foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [1, 2, 3] 1 2

Answer 1

Ключевым моментом здесь является то, что операция foldr создает функцию, затем , применяя ее к a и b;мы можем уточнить это, добавив скобки:

mystery a b c xs = 
(foldr (\x rec a b -> rec x (b + c)) (\a b -> a + b - c) xs) a b

Если список xs пуст, вы получите просто начальную функцию \a b -> a + b - c, которая затем применяется к a и b.

, еслиона не пустая, тогда она выполняет последовательные преобразования в эту функцию (в каждой итерации «rec» - это предыдущая функция, которая используется для создания новой).

Для иллюстрации давайте запустим foldrрука для mystery 1 2 3 [1, 2, 3];изначально мы имеем:

foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [1,2,3]

Применение уравнений для foldr:

foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

Сокращает выражение до:

(\rec a b -> rec 1 (b + 3)) (foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [2,3])

Повторяется для следующего значения всписок, который мы получаем:

(\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [3])

Затем, для последнего:

(\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\rec a b -> rec 3 (b + 3)) (\a b -> a + b - 3)

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

(\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\rec a b -> rec 3 (b + 3)) (\a b -> a + b - 3)
=> (\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\a b -> (\a b -> a + b - 3) 3 (b + 3))
=> (\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\a b -> 3 + (b + 3) - 3))
=> (\rec a b -> rec 1 (b + 3)) (\a b -> (\a b -> 3 + (b + 3) - 3)) 2 (b + 3))
=> (\rec a b -> rec 1 (b + 3)) (\a b -> 3 + ((b + 3) + 3) - 3))
=> \a b -> (\a b -> 3 + ((b + 3) + 3) - 3)) 1 (b + 3)
=> \a b -> 3 + (((b + 3) + 3) + 3) - 3)
=> \a b -> b + 9

затем мы применяем \a b -> b + 9 к исходным "a" и "b" (которые равны 1 и 2), и получаем 2 + 9 = 11

Answer 2

Подставляя определение для foldr, функция проявляет себя как

mystery a b c xs = 
 = foldr (\x rec a b -> rec x (b + c)) (\a b -> a + b - c) xs a b
 = let { g x r   a b =  r   x (b + c); z a b =  a + b - c } in 
     foldr g z xs a b
     =>  foldr g z [] a b = z a b            = a  + b       - c
     =>  foldr g z [x1,x2,...,xn] a  b
          = g x1 (foldr g z [x2,...,xn]) a b   -- g x r a b = r x (b+c)
          = foldr g z [x2,...,xn] x1 (b+c)
          = foldr g z [x3,...,xn] x2 (b+c*2)
          = foldr g z [         ] xn (b+c*n) = xn + b + c*n - c
 = last (a:xs) + b + c * (length xs - 1)

Именование двух лямбда-функций с использованием коротких имен значительно упрощает визуальную обработку выражений.

Answer 3

Когда функция сворачивания, заданная для foldr, принимает более двух параметров, часто это действительно скрытый foldl.Давайте посмотрим, правда ли это здесь.

mystery a b c xs = foldr (\x rec a b -> rec x (b + c)) (\a b -> a + b - c) xs a b

Вывод двух «дополнительных» аргументов для функции свертывания:

mystery a b c xs = foldr (\x rec (a,b) -> rec (x,b + c)) (\(a,b) -> a + b - c) xs (a,b)

Извлечение функции f из функции свертывания и finalStep из нулевого случая:

mystery a b c xs = foldr (\x rec z -> rec (f z x)) finalStep xs (a,b)
  where
    f (a,b) x = (x,b + c)
    finalStep (a,b) = a + b - c

Заменить foldr явной рекурсией:

mystery a b c xs = go xs (a,b)
  where
    go [] = finalStep
    go (x:xs) = \z -> go xs (f z x)
    f (a,b) x = (x,b + c)
    finalStep (a,b) = a + b - c

Переместить вызов на finalStep вне go:

mystery a b c xs = finalStep $ go xs (a,b)
  where
    go [] = id
    go (x:xs) = \z -> go xs (f z x)
    f (a,b) x = (x,b + c)
    finalStep (a,b) = a + b - c

Эта-расширение go и обратный порядок аргументов:

mystery a b c xs = finalStep $ go (a,b) xs
  where
    go z [] = z
    go z (x:xs) = go (f z x) xs
    f (a,b) x = (x,b + c)
    finalStep (a,b) = a + b - c

Теперь go - это в точности определение foldl f, поэтому замените его следующим:

mystery a b c xs = finalStep $ foldl f (a,b) xs
  where
    f (a,b) x = (x,b + c)
    finalStep (a,b) = a + b - c

Теперь у нас есть очень простая операция сгиба, которую можно легко выполнить.Основным выводом из вышесказанного является тот факт, что foldr (\x rec -> rec . f x) finalStep xs z и finalStep $ foldl (flip f) z xs одинаковы для любых f, z и xs.