Некоторые пояснения приведены по порядку!
Для чего нужна функция id?Какова роль?Зачем нам здесь это нужно?
id - это тождественная функция , id x = x и используется как эквивалент нуля при построении цепочки функций с функция композиции , (.).Вы можете найти его , определенный в прелюдии .
В приведенном выше примере функция id является аккумулятором в лямбда-функции?
Аккумулятор - это функция, которая создается с помощью повторного применения функции.Там нет явного лямбда, так как мы называем аккумулятор, step.Вы можете написать это с лямбдой, если хотите:
foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
Или как Грэм Хаттон напишет :
5.1 Оператор foldl
Теперь давайте обобщим пример suml и рассмотрим стандартный оператор foldl, который обрабатывает элементы списка в порядке слева направо, используя функцию f для объединения значений и значения.v в качестве начального значения:
foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs
Используя этот оператор, suml можно просто переопределить с помощью suml = foldl (+) 0.Многие другие функции могут быть определены простым способом, используя foldl.Например, стандартная функция reverse может быть переопределена с помощью foldl следующим образом:
reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]
Это определение более эффективно, чем наше первоначальное определение с использованием сгиба, поскольку оно позволяет избежать использования неэффективного оператора добавления (++) для списков.
Простое обобщение вычисления в предыдущем разделе для функции suml показывает, как переопределить функцию foldl в терминах fold:
foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v
В отличие от этого, невозможно переопределить fold в терминах foldl из-за того, что foldl является строгим в хвосте аргумента списка, а fold - нет.Существует ряд полезных «теорем двойственности», касающихся fold и foldl, а также некоторые рекомендации для определения, какой оператор лучше всего подходит для конкретных приложений (Bird, 1998).
* 1067Прототип * foldr - это foldr :: (a -> b -> b) -> b -> [a] -> b
Программист на Haskell скажет, что type из foldr равно (a -> b -> b) -> b -> [a] -> b.
, и первый параметр - это функция, для которой нужны два параметра, но функция шага в реализации myFoldl использует 3 параметра, я совершенно запутался
Это запутанно и волшебно!Мы разыгрываем трюк и заменяем аккумулятор функцией, которая, в свою очередь, применяется к начальному значению для получения результата.
Грэм Хаттон объясняет трюк, чтобы превратить foldl в foldr в приведенной выше статье,Мы начнем с записи рекурсивного определения foldl:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x : xs) = foldl f (f v x) xs
, а затем рефакторинг его с помощью преобразования статического аргумента на f:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs = g xs v
where
g [] v = v
g (x:xs) v = g xs (f v x)
Давайте теперь переписать g чтобы всплывать v внутрь:
foldl f v xs = g xs v
where
g [] = \v -> v
g (x:xs) = \v -> g xs (f v x)
То же самое, что думать о g как функции одного аргумента, который возвращает функцию:
foldl f v xs = g xs v
where
g [] = id
g (x:xs) = \v -> g xs (f v x)
Теперь у нас есть g, функция, которая рекурсивно просматривает список, применила некоторую функцию f.Конечным значением является функция тождества, и каждый шаг также приводит к функции.
Но , у нас уже есть очень похожая рекурсивная функция в списках, foldr!
2 Оператор свертки
Оператор fold берет свое начало в теории рекурсии (Kleene, 1952), в то время как использование fold в качестве центрального понятия в языке программирования восходит к оператору редукции APL (Iverson, 1962), а позже к вставкеоператор ФП (Бакус, 1978).В Haskell оператор fold для списков может быть определен следующим образом:
fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)
То есть с учетом функции f типа α → β → β и значения v типа βфункция fold f v обрабатывает список типа [α] для получения значения типа β, заменяя nil constructor [] в конце списка по значению v, а каждый конструктор cons (:) в списке по функции f.Таким образом, оператор fold инкапсулирует простой шаблон рекурсии для обработки списков, в котором два конструктора для списков просто заменяются другими значениями и функциями.Ряд знакомых функций в списках имеет простое определение, используя fold.
Это похоже на рекурсивную схему, очень похожую на нашу g функцию.Теперь хитрость: используя всю доступную магию под рукой (иначе говоря, Берд, Меертенс и Малкольм), мы применяем специальное правило, универсальное свойство складки , которое является эквивалентностью между двумя определениями для функции gкоторый обрабатывает списки, указанные как:
g [] = v
g (x:xs) = f x (g xs)
тогда и только тогда, когда
g = fold f v
Итак, универсальное свойство сгибов гласит:
g = foldr k v
, где g должно быть эквивалентно двум уравнениям, для некоторых k и v:
g [] = v
g (x:xs) = k x (g xs)
Из наших более ранних схем складывания мы знаем v == id.Однако для второго уравнения нам нужно вычислить определение k:
g (x:xs) = k x (g xs)
<=> g (x:xs) v = k x (g xs) v -- accumulator of functions
<=> g xs (f v x) = k x (g xs) v -- definition of foldl
<= g' (f v x) = k x g' v -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x)) -- expand k. recursion captured in g'
Что, подставляя наши вычисленные определения k и v, дает определениеfoldl as:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs =
foldr
(\x g -> (\a -> g (f v x)))
id
xs
v
Рекурсив g заменяется комбинатором foldr, и аккумулятор становится функцией, построенной через цепочку композиций f для каждого элемента списка, в обратном порядке.(поэтому мы сворачиваем влево вместо права).
Это определенно несколько продвинуто, поэтому, чтобы глубоко понять это преобразование, универсальное свойство складок , которое делает возможным преобразование, я рекомендую Hutton'sучебник, ссылка ниже.
Список литературы