Foldr и Foldl Далее объяснения и примеры
-
08-10-2019 - |
Вопрос
Я посмотрел разные складки а также Складной в целом а также несколько других, и они объясняют это довольно хорошо.
У меня все еще есть проблемы на том, как будет работать лямбда в этом случае.
foldr (\y ys -> ys ++ [y]) [] [1,2,3]
Может ли кто-нибудь пройти через этот шаг и попытаться объяснить это мне?
А также как бы foldl
работай?
Решение
С использованием
foldr f z [] = z
foldr f z (x:xs) = x `f` foldr f z xs
А также
k y ys = ys ++ [y]
Давайте распапала:
foldr k [] [1,2,3]
= k 1 (foldr k [] [2,3]
= k 1 (k 2 (foldr k [] [3]))
= k 1 (k 2 (k 3 (foldr k [] [])))
= (k 2 (k 3 (foldr k [] []))) ++ [1]
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1]
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1]
= ((([]) ++ [3]) ++ [2]) ++ [1]
= (([3]) ++ [2]) ++ [1]
= ([3,2]) ++ [1]
= [3,2,1]
Другие советы
Foldr - это легкая вещь:
foldr :: (a->b->b) -> b -> [a] -> b
Требуется функция, которая как-то похожа на (:),
(:) :: a -> [a] -> [a]
и значение, которое похоже на пустой список [],
[] :: [a]
И заменяет каждый: и [] в некоторых списке.
Похоже, это выглядит:
foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e))
Вы можете представить себе Foldr как какой-то государственный механизм тоже:
f Переход,
f :: input -> state -> state
и е - начальное состояние.
e :: state
Foldr (Foldright) запускает станок с переходом F и состоянием запуска e через список входов, начиная с правого конца. Представьте себе f в INFIX LOUTIONATION, как Pacman исходит отправый.
Foldl (Foldleft) делает то же самое излево, но функция перехода, записанная в инфиксированной записи, принимает свой входной аргумент справа. Таким образом, машина потребляет список, начиная с левого конца. Pacman потребляет список излево с открытым ртом вправо, из-за рта (B-> A-> b) вместо (A-> B-> B).
foldl :: (b->a->b) -> b -> [a] -> b
Чтобы сделать это ясно, представьте функцию (-)
Как переход:
foldl (-) 100 [1] = 99 = ((100)-1)
foldl (-) 100 [1,2] = 97 = (( 99)-2) = (((100)-1)-2)
foldl (-) 100 [1,2,3] = 94 = (( 97)-3)
foldl (-) 100 [1,2,3,4] = 90 = (( 94)-4)
foldl (-) 100 [1,2,3,4,5] = 85 = (( 90)-5)
foldr (-) 100 [1] = -99 = (1-(100))
foldr (-) 100 [2,1] = 101 = (2-(-99)) = (2-(1-(100)))
foldr (-) 100 [3,2,1] = -98 = (3-(101))
foldr (-) 100 [4,3,2,1] = 102 = (4-(-98))
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102))
Вы, вероятно, хотите использовать Foldr в ситуациях, когда список может быть бесконечным, а где оценка должна быть ленивая:
foldr (either (\l ~(ls,rs)->(l:ls,rs))
(\r ~(ls,rs)->(ls,r:rs))
) ([],[]) :: [Either l r]->([l],[r])
И вы, вероятно, хотите использовать строгую версию Foldl, которая является Foldl ', когда вы употребляете весь список для создания его вывода. Это может работать лучше и может помешать вам отменить исключение из переполнения стека или внезапных исключений (в зависимости от компилятора) из-за экстремальных длинных списков в сочетании с ленивой оценкой:
foldl' (+) 0 [1..100000000] = 5000000050000000
foldl (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
foldr (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
Первый -step по шагам - создает одну запись списка, оценивает его и потребляет его.
Второй из которых создается очень длинная формула сначала, потраченная воспоминания с ((... (((((0 + 1) +2) +3) + ...) и оценивает все это потом.
Третий как второй, но с другой формулой.
Определение foldr
является:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Итак, вот пошаговый снижение вашего примера:
foldr (\y ys -> ys ++ [y]) [] [1,2,3]
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3])
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1]
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1]
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1]
= [] ++ [3] ++ [2] ++ [1]
= [3,2,1]
INFIX NONATION, вероятно, будет понятнее здесь.
Давайте начнем с определения:
foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)
Ради краткости, давайте напишем g
вместо (\y ys -> ys ++ [y])
. Отказ Следующие строки эквивалентны:
foldr g [] [1,2,3]
1 `g` (foldr g [] [2,3])
1 `g` (2 `g` (foldr g [] [3]))
1 `g` (2 `g` (3 `g` (foldr g [] [])))
1 `g` (2 `g` (3 `g` []))
(2 `g` (3 `g` [])) ++ [1]
(3 `g` []) ++ [2] ++ [1]
[3] ++ [2] ++ [1]
[3,2,1]