В Real World Haskell , Глава 4. Функциональное программирование :
Напишите foldl с помощью foldr:
-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
Приведенный выше код меня сильно смутил, и кто-то позвонил в dps и переписал его с осмысленным именем, чтобы было немного понятнее:
myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)
Затем кто-то другой, Джеф Джи, отлично поработал, предоставив пример и шаг за шагом продемонстрировав базовый механизм:
myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3
Но я все еще не могу полностью это понять, вот мои вопросы:
- Для чего нужна функция id? Какая роль? Зачем оно нам здесь?
- В приведенном выше примере функция id является аккумулятором в лямбда-функции?
- Прототип foldr есть
foldr :: (a -> b -> b) -> b -> [a] -> b
, и первый параметр - это функция, которой требуются два параметра, но пошаговая функция в реализации myFoldl использует 3 параметра, я полностью запутался!
step = curry $ uncurry (&) <<< (flip f) *** (.)
Ответы:
Некоторые пояснения по порядку!
Для чего нужна функция id? Какая роль? Зачем оно нам здесь?
id
это функция тождества ,id x = x
и используется как эквивалент нуля при наращивании цепочки функций с функцией состава ,(.)
. Вы можете найти его определение в Prelude .В приведенном выше примере функция id является аккумулятором в лямбда-функции?
Аккумулятор - это функция, которая создается с помощью повторяющихся функций. Явного лямбда-выражения нет, поскольку мы называем аккумулятор
step
. Вы можете написать это с помощью лямбды, если хотите:foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
Или, как написал бы Грэм Хаттон :
Прототип foldr - foldr :: (a -> b -> b) -> b -> [a] -> b
Haskell программист хотел бы сказать , что тип из
foldr
вне(a -> b -> b) -> b -> [a] -> b
.и первый параметр - это функция, которой требуются два параметра, но пошаговая функция в реализации myFoldl использует 3 параметра, я полностью запутался
Это сбивает с толку и волшебно! Мы играем в шутку и заменяем аккумулятор функцией, которая, в свою очередь, применяется к начальному значению, чтобы получить результат.
Graham Hutton объясняет трюк , чтобы включить
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
!Это похоже на рекурсивную схему, очень похожую на нашу
g
функцию. Теперь уловка: используя всю доступную магию (также известную как Бёрд, Меертенс и Малкольм), мы применяем специальное правило, универсальное свойство свёртки , которое является эквивалентом двух определений для функцииg
, обрабатывающей списки, а именно:Итак, универсальное свойство складок гласит:
где
g
должно быть эквивалентно двум уравнениям для некоторыхk
иv
:Из наших предыдущих дизайнов складок мы знаем
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 как: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
каждого элемента списка в обратном порядке (поэтому мы сворачиваем влево, а не вправо).Это определенно несколько продвинуто, поэтому, чтобы глубоко понять это преобразование, универсальное свойство складок , которое делает преобразование возможным, я рекомендую учебник Хаттона, ссылка на который приведена ниже.
Рекомендации
источник
k = \x g' -> (\a -> g' (f v x))
и(\x g -> (\a -> g (f v x)))
Рассмотрим тип
foldr
:foldr :: (b -> a -> a) -> a -> [b] -> a
Тогда как типа
step
что-то вродеb -> (a -> a) -> a -> a
. Поскольку step передаетсяfoldr
, мы можем сделать вывод, что в этом случае складка имеет тип, подобный(b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a)
.Пусть вас не смущают разные значения
a
в разных подписях; это просто переменная типа. Кроме того, имейте в виду, что стрелка функции является правой ассоциативной, поэтомуa -> b -> c
это то же самое, что иa -> (b -> c)
.Итак, да, значение аккумулятора для
foldr
- это функция типаa -> a
, а начальное значение -id
. В этом есть смысл, потому чтоid
это функция, которая ничего не делает - по той же причине, по которой вы начинаете с нуля в качестве начального значения при добавлении всех значений в список.Что касается
step
принятия трех аргументов, попробуйте переписать его так:step :: b -> (a -> a) -> (a -> a) step x g = \a -> g (f a x)
Это облегчает понимание того, что происходит? Требуется дополнительный параметр, поскольку он возвращает функцию, и два способа его записи эквивалентны. Также обратите внимание на дополнительный параметр по очереди
foldr
:(foldr step id xs) z
. Часть в скобках - это сама свёртка, которая возвращает функцию, к которой затем применяетсяz
.источник
(быстро просмотрите мои ответы [1] , [2] , [3] , [4], чтобы убедиться, что вы понимаете синтаксис Haskell, функции высшего порядка, каррирование, композицию функций, оператор $, инфиксные / префиксные операторы, разделы и лямбда-выражения )
Универсальное свойство складки
Раз просто кодификация определенных видов рекурсии. А свойство универсальности просто утверждает, что если ваша рекурсия соответствует определенной форме, она может быть преобразована в свертку согласно некоторым формальным правилам. И наоборот, каждую складку можно преобразовать в такую рекурсию. Опять же, некоторые рекурсии можно преобразовать в свертки, которые дают точно такой же ответ, а некоторые рекурсии - нет, и для этого существует точная процедура.
По сути, если ваша рекурсивная функция работает со списками, которые выглядят как слева , вы можете преобразовать ее, чтобы свернуть один вправо , подставляя
f
и вместоv
того, что на самом деле есть.g [] = v ⇒ g (x:xs) = f x (g xs) ⇒ g = foldr f v
Например:
sum [] = 0 {- recursion becomes fold -} sum (x:xs) = x + sum xs ⇒ sum = foldr 0 (+)
Здесь
v = 0
иsum (x:xs) = x + sum xs
эквивалентноsum (x:xs) = (+) x (sum xs)
, поэтомуf = (+)
. Еще 2 примераproduct [] = 1 product (x:xs) = x * product xs ⇒ product = foldr 1 (*) length [] = 0 length (x:xs) = 1 + length xs ⇒ length = foldr (\_ a -> 1 + a) 0
Сложить через foldr
Как написать рекурсивную функцию, которая суммирует числа слева направо?
sum [] = 0 -- given `sum [1,2,3]` expands into `(1 + (2 + 3))` sum (x:xs) = x + sum xs
Первая рекурсивная функция, которую нужно найти, полностью раскрывается еще до того, как начинает складываться, это не то, что нам нужно. Один из подходов - создать рекурсивную функцию с аккумулятором , которая немедленно складывает числа на каждом шаге (прочтите о хвостовой рекурсии, чтобы узнать больше о стратегиях рекурсии):
suml :: [a] -> a suml xs = suml' xs 0 where suml' [] n = n -- auxiliary function suml' (x:xs) n = suml' xs (n+x)
Хорошо, стой! Запустите этот код в GHCi и убедитесь, что вы понимаете, как он работает, затем внимательно и вдумчиво продолжайте.
suml
не может быть переопределен сгибом, ноsuml'
может быть.suml' [] = v -- equivalent: v n = n suml' (x:xs) n = f x (suml' xs) n
suml' [] n = n
из определения функции, верно? Иv = suml' []
из формулы универсального свойства. Вместе это даетv n = n
, функцию , которая немедленно возвращает то , что получает:v = id
. Рассчитаемf
:suml' (x:xs) n = f x (suml' xs) n -- expand suml' definition suml' xs (n+x) = f x (suml' xs) n -- replace `suml' xs` with `g` g (n+x) = f x g n
Таким образом,
suml' = foldr (\x g n -> g (n+x)) id
и, таким образом,suml = foldr (\x g n -> g (n+x)) id xs 0
.foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55
Теперь нам просто нужно обобщить, заменив
+
переменной функцией:foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a foldl (-) 10 [1..5] -- returns -5
Заключение
Теперь прочтите Учебник Грэма Хаттона по универсальности и выразительности складки . Возьмите ручку и бумагу, постарайтесь понять все, что он пишет, пока не получите большую часть складок самостоятельно. Не переживайте, если вы чего-то не понимаете, вы всегда можете вернуться позже, но и не откладывайте на потом.
источник
Вот мое доказательство, которое
foldl
можно выразить в терминахfoldr
, которое я считаю довольно простым, если не считать названия спагетти, котороеstep
вводит функция.Предложение состоит в том, что
foldl f z xs
эквивалентноmyfoldl f z xs = foldr step_f id xs z where step_f x g a = g (f a x)
Первое, на что следует обратить внимание, это то, что правая часть первой строки фактически оценивается как
поскольку
foldr
принимает только три параметра. Это уже намекает на то, чтоfoldr
будет вычисляться не значение, а каррированная функция, к которой затем применяетсяz
. Есть два случая , чтобы провести расследование , чтобы выяснить ,myfoldl
являетсяfoldl
:Базовый случай: пустой список
myfoldl f z [] = foldr step_f id [] z (by definition of myfoldl) = id z (by definition of foldr) = z foldl f z [] = z (by definition of foldl)
Непустой список
myfoldl f z (x:xs) = foldr step_f id (x:xs) z (by definition of myfoldl) = step_f x (foldr step_f id xs) z (-> apply step_f) = (foldr step_f id xs) (f z x) (-> remove parentheses) = foldr step_f id xs (f z x) = myfoldl f (f z x) xs (definition of myfoldl) foldl f z (x:xs) = foldl f (f z x) xs
Поскольку в 2. первая и последняя строки имеют одинаковую форму в обоих случаях, ее можно использовать для свертывания списка до тех пор
xs == []
, пока , в этом случае 1. не гарантирует одинаковый результат. Итак, по индукцииmyfoldl == foldl
.источник
Нет Королевской дороги к математике, даже через Haskell. Позволять
h z = (foldr step id xs) z where step x g = \a -> g (f a x)
Что это за хрень
h z
? Предположим, чтоxs = [x0, x1, x2]
.Примените определение foldr:
h z = (step x0 (step x1 (step x2 id))) z
Примените определение шага:
Подставляем в лямбда-функции:
Применить определение id:
Примените определение foldl:
Это Королевская дорога или что?
источник
Перед тем как голосовать против, прочтите следующий абзац.
Я отправляю ответ для тех людей, которым этот подход может лучше соответствовать их образу мышления. Ответ, возможно, содержит избыточную информацию и мысли, но это то, что мне нужно для решения проблемы. Кроме того, поскольку это еще один ответ на тот же вопрос, очевидно, что он существенно пересекается с другими ответами, однако он рассказывает историю о том, как я мог понять эту концепцию.
На самом деле я начал записывать эти заметки как личную запись своих мыслей, пытаясь понять эту тему. Мне потребовался целый день, чтобы коснуться его сути, если я действительно понял.
Мой долгий путь к пониманию этого простого упражнения
Легкая часть: что нам нужно определить?
Что происходит в следующем примере вызова
foldl f z [1,2,3,4]
можно визуализировать с помощью следующей диаграммы (которая есть в Википедии , но я впервые увидел ее в другом ответе ):
_____results in a number / f f (f (f (f z 1) 2) 3) 4 / \ f 4 f (f (f z 1) 2) 3 / \ f 3 f (f z 1) 2 / \ f 2 f z 1 / \ z 1
(В качестве примечания, при использовании
foldl
каждого приложенияf
не выполняется, а выражения обрабатываются так же, как я написал их выше; в принципе, они могут быть вычислены, когда вы идете снизу вверх, и это именно то, чтоfoldl'
делает.)Упражнение по существу заставляет нас использовать
foldr
вместоfoldl
соответствующего изменения пошаговой функции (поэтому мы используемs
вместоf
) и начального аккумулятора (так что мы используем?
вместоz
); список остается прежним, иначе о чем мы говорим?Вызов
foldr
должен выглядеть так:foldr s ? [1,2,3,4]
и соответствующая диаграмма такова:
_____what does the last call return? / s / \ 1 s / \ 2 s / \ 3 s / \ 4 ? <--- what is the initial accumulator?
Звонок приводит к
s 1 (s 2 (s 3 (s 4 ?)))
Что такое
s
и?
? А какие у них виды? Похоже, чтоs
это функция с двумя аргументами, очень похожеf
, но не будем торопиться с выводами. Кроме того, давайте?
на мгновение оставим в стороне и заметим, чтоz
это должно вступать в игру, как только1
вступает в игру; однако, как это можетz
сыграть роль в вызове функции с двумя аргументамиs
, а именно в вызовеs 1 (…)
? Мы можем решить эту часть загадки, выбрав функцию,s
которая принимает 3 аргумента, а не 2, о которых мы упоминали ранее, так что внешний вызовs 1 (…)
приведет к функции, принимающей один аргумент, которому мы можем передатьz
!Это означает, что нам нужен исходный вызов, который расширяется до
f (f (f (f z 1) 2) 3) 4
быть эквивалентным
s 1 (s 2 (s 3 (s 4 ?))) z
или, другими словами, мы хотим, чтобы частично примененная функция
s 1 (s 2 (s 3 (s 4 ?)))
быть эквивалентным следующей лямбда-функции
(\z -> f (f (f (f z 1) 2) 3) 4)
Опять же, «единственные» части, которые нам нужны, - это
s
и?
.Поворотный момент: распознать состав функций
Давайте перерисуем предыдущую диаграмму и напишем справа, чему мы хотим, чтобы каждый вызов
s
был эквивалентен:s s 1 (…) == (\z -> f (f (f (f z 1) 2) 3) 4) / \ 1 s s 2 (…) == (\z -> f (f (f z 2) 3) 4) / \ 2 s s 3 (…) == (\z -> f (f z 3) 4) / \ 3 s s 4 ? == (\z -> f z 4) / \ 4 ? <--- what is the initial accumulator?
Я надеюсь, что из структуры диаграммы ясно, что
(…)
на каждой строке находится правая часть строки под ней; лучше, это функция, возвращенная из предыдущего (ниже) вызоваs
.Также должно быть ясно, что вызов
s
с аргументамиx
иy
является (полным) приложениемy
к частичному применениюf
к единственному аргументуx
. Поскольку частичное применениеf
tox
может быть записано как лямбда(\z -> f z x)
, полное применениеy
к нему приводит к лямбде(\z -> y (f z x))
, которую в данном случае я бы переписал какy . (\z -> f z x)
; переводя слова в выражение, потому чтоs
мы получаемs x y = y . (\z -> f z x)
(Это то же самое
s x y z = y (f z x)
, что и книга, если вы переименуете переменные.)Последний бит: каково начальное «значение»
?
аккумулятора? Приведенную выше диаграмму можно переписать, расширив вложенные вызовы, чтобы сделать их композиционными цепочками:s s 1 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1) / \ 1 s s 2 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) / \ 2 s s 3 (…) == (\z -> f z 4) . (\z -> f z 3) / \ 3 s s 4 ? == (\z -> f z 4) / \ 4 ? <--- what is the initial accumulator?
Здесь мы видим, что
s
просто «накапливаются» последовательные частичные примененияf
, ноy
ins x y = y . (\z -> f z x)
предполагает, что интерпретацияs 4 ?
(и, в свою очередь, всех остальных) упускает ведущую функцию, которая должна быть составлена с самой левой лямбдой.Это и есть наша
?
функция: пора дать ему причину его существования, помимо того, что он занимает место в вызовеfoldr
. Что мы можем выбрать, чтобы не менять результирующие функции? Ответ:id
, на единичный элемент по отношению к оператору композиции(.)
.s s 1 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1) / \ 1 s s 2 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) / \ 2 s s 3 (…) == id . (\z -> f z 4) . (\z -> f z 3) / \ 3 s s 4 id == id . (\z -> f z 4) / \ 4 id
Итак, искомая функция
myFoldl f z xs = foldr (\x g a -> g (f a x)) id xs z
источник
Это может помочь, я пробовал расширяться другим способом.
myFoldl (+) 0 [1,2,3] = foldr step id [1,2,3] 0 = foldr step (\a -> id (a+3)) [1,2] 0 = foldr step (\b -> (\a -> id (a+3)) (b+2)) [1] 0 = foldr step (\b -> id ((b+2)+3)) [1] 0 = foldr step (\c -> (\b -> id ((b+2)+3)) (c+1)) [] 0 = foldr step (\c -> id (((c+1)+2)+3)) [] 0 = (\c -> id (((c+1)+2)+3)) 0 = ...
источник
foldr step zero (x:xs) = step x (foldr step zero xs) foldr _ zero [] = zero myFold f z xs = foldr step id xs z where step x g a = g (f a x) myFold (+) 0 [1, 2, 3] = foldr step id [1, 2, 3] 0 -- Expanding foldr function step 1 (foldr step id [2, 3]) 0 step 1 (step 2 (foldr step id [3])) 0 step 1 (step 2 (step 3 (foldr step id []))) 0 -- Expanding step function if it is possible step 1 (step 2 (step 3 id)) 0 step 2 (step 3 id) (0 + 1) step 3 id ((0 + 1) + 2) id (((0 + 1) + 2) + 3)
Ну, по крайней мере, мне это помогло. Даже не совсем верно.
источник
foldr step id [1, 2, 3] 0
->step 1 (foldr step id [2, 3]) 0
->(foldr step id [2, 3]) (0 + 1)
->step 2 (foldr step id [3]) (0 + 1)
->(foldr step id [3]) ((0 + 1) + 2)
->step 3 (foldr step id []) ((0 + 1) + 2)
->(foldr step id []) (((0 + 1) + 2) + 3)
->id (((0 + 1) + 2) + 3)
.Этот ответ позволяет легко понять приведенное ниже определение за три шага.
-- file: ch04/Fold.hs myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f z xs = foldr step id xs z where step x g a = g (f a x)
Шаг 1. Преобразуйте кратность оценки функции в комбинацию функций
foldl f z [x1 .. xn] = z & f1 & .. & fn = fn . .. . f1 z
. в которомfi = \z -> f z xi
.(Используя
z & f1 & f2 & .. & fn
это означаетfn ( .. (f2 (f1 z)) .. )
.)Шаг 2. выразите комбинацию функций в
foldr
видеfoldr (.) id [f1 .. fn] = (.) f1 (foldr (.) id [f2 .. fn]) = f1 . (foldr (.) id [f2 .. fn])
. Остальное разверните, чтобы получитьfoldr (.) id [f1 .. fn] = f1 . .. . fn
.Заметив, что последовательность перевернута, мы должны использовать перевернутую форму
(.)
.rc f1 f2 = (.) f2 f1 = f2 . f1
Тогда дайте определениеfoldr rc id [f1 .. fn] = rc f1 (foldr (.) id [f2 .. fn]) = (foldr (.) id [f2 .. fn]) . f1
. Остальное разверните, чтобы получитьfoldr rc id [f1 .. fn] = fn . .. . f1
.Шаг 3. Преобразуйте свертку в списке функций в свертку в списке операндов.
Найдите
step
то, что делаетfoldr step id [x1 .. xn] = foldr rc id [f1 .. fn]
. Легко найтиstep = \x g z -> g (f z x)
.В 3 шага определение
foldl
использованияfoldr
ясно:Докажите правильность:
foldl f z xs = foldr (\x g z -> g (f z x)) id xs z = step x1 (foldr step id [x2 .. xn]) z = s1 (foldr step id [x2 .. xn]) z = s1 (step x2 (foldr step id [x3 .. xn])) z = s1 (s2 (foldr step id [x3 .. xn])) z = .. = s1 (s2 (.. (sn (foldr step id [])) .. )) z = s1 (s2 (.. (sn id) .. )) z = (s2 (.. (sn id) .. )) (f z x1) = s2 (s3 (.. (sn id) .. )) (f z x1) = (s3 (.. (sn id) .. )) (f (f z x1) x2) = .. = sn id (f (.. (f (f z x1) x2) .. ) xn-1) = id (f (.. (f (f z x1) x2) .. ) xn) = f (.. (f (f z x1) x2) .. ) xn in which xs = [x1 .. xn], si = step xi = \g z -> g (f z xi)
Если вы обнаружите, что что-то неясно, добавьте комментарий. :)
источник