Реализация zip с помощью Foldr
https://stackoverflow.com/questions/235148
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Сейчас я просматриваю главу 4 Real World Haskell и пытаюсь осмыслить реализация Foldl с точки зрения Foldr.
(Вот их код:)
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)
Я подумал, что попробую реализовать zip используя ту же технику, но, похоже, я не добился никакого прогресса.Возможно ли это вообще?
Решение
zip2 xs ys = foldr step done xs ys
where done ys = []
step x zipsfn [] = []
step x zipsfn (y:ys) = (x, y) : (zipsfn ys)
Как это работает: (шаг сворачивания сделан xs) возвращает функцию, которая потребляет YS; поэтому мы идем вниз по списку XS создание вложенной композиции функции, каждая из которых будет применена к соответствующей части ys.
Как придумать это: я начал с общей идеи (из аналогичного примеры видели раньше) писал
zip2 xs ys = foldr step done xs ys
затем заполнял каждую из следующих строк по очереди быть, чтобы типы и значения вышли правильно. Это было проще всего сначала рассмотрим самые простые случаи, а не самые сложные.
Первая строка может быть написана более просто как
zip2 = foldr step done
как показал маттиаст.
Другие советы
Здесь уже был дан ответ, но не (иллюстративный) вывод.Так что даже спустя все эти годы, возможно, стоит добавить это.
На самом деле это довольно просто.Первый,
foldr f z xs = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn]) = ... = f x1 (ф х2 (ф х3 (...(ф хн з) ...)))
следовательно, посредством эта-разложения,
foldr f z xs ys = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys = ... = f x1 (ф х2 (ф х3 (...(ф хн з) ...))) ys
Как здесь видно, если f не является принудительным во втором аргументе, оно начнет работать первый на x1 и ys, f x1r1ys где r1 =(f x2 (f x3 (... (f xn z) ...)))= foldr f z [x2,x3,...,xn].
Итак, используя
f x1 р1 [] = [] f x1 р1 (y1:ys1) = (x1,y1) : р1 ys1
мы организуем передачу информации слева направо по списку, по звоню r1 с отдых из входного списка ys1, foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1, как следующий шаг.И это все.
Когда ys короче, чем xs (или той же длины), [] Чехол для f сгорает и обработка останавливается.Но если ys длиннее, чем xs затем f's [] дело не выстрелит и мы дойдем до финала f xnz(yn:ysn) приложение,
f xn я (yn:ysn) = (xn,yn) : я ysn
Поскольку мы достигли конца xs, zip обработка должна прекратиться:
я _ = []
А это означает определение z = const [] должен быть использован:
zip xs ys = foldr f (const []) xs ys
where
f x r [] = []
f x r (y:ys) = (x,y) : r ys
С точки зрения f, r играет роль продолжение успеха, который f вызывает, когда обработка должна продолжаться после отправки пары (x,y).
Так r является "что делается с более ys когда будет больше xс", и z = const [], nil-дело в foldr, является «что сделано с ys когда их больше нет xс".Или f может остановиться сам, вернувшись [] когда ys исчерпан.
Обратите внимание, как ys используется как своего рода накапливаемое значение, которое передается слева направо по списку xs, от одного вызова f к следующему (шагом накопления здесь является удаление из него головного элемента).
Естественно это соответствует левому сгибу, где шагом накопления является «применение функции», с z = id возврат окончательного накопленного значения, когда «нет больше xс":
foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a
Аналогично для конечных списков
foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a
А поскольку функция объединения решает, продолжать или нет, теперь можно сделать левый сгиб, который может остановиться раньше:
foldlWhile t f a xs = foldr cons id xs a
where
cons x r a = if t x then r (f a x) else a
или пропуск левой складки, foldlWhen t ..., с
cons x r a = if t x then r (f a x) else r a
и т. д.
Я нашел способ, очень похожий на ваш:
myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
where step a f (b:bs) = (a,b):(f bs)
step a f [] = []
Для не родных Хаскелеров здесь я написал версию этого алгоритма для Scheme, чтобы прояснить, что на самом деле происходит:
> (define (zip lista listb)
((foldr (lambda (el func)
(lambda (a)
(if (empty? a)
empty
(cons (cons el (first a)) (func (rest a))))))
(lambda (a) empty)
lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))
foldr приводит к функции, которая при применении к списку возвращает zip списка, свернутого со списком, переданным функции. Haskell скрывает внутреннюю лямбду из-за ленивой оценки.
Чтобы разбить его дальше:
Взять почтовый индекс на входе: '(1 2 3) Функция Foldr вызывается с помощью
el->3, func->(lambda (a) empty)
Это расширяется до:
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))
Если бы мы вернули это сейчас, у нас была бы функция, которая принимает список из одного элемента и возвращает пару (3 элемента):
> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))
Продолжая, теперь foldr вызывает func с помощью
el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))
Это функция, которая теперь берет список с двумя элементами и архивирует их с помощью (список 2 3) :
> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))
Что происходит?
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))
a , в данном случае это (список 9 1)
(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))
И, как вы помните, f объединяет свой аргумент с 3 .
И это продолжается и т.д. ...
Проблема всех этих решений для zip заключается в том, что они сворачиваются только в один или другой список, что может быть проблемой, если оба они являются "хорошими производителями", на языке список слияния. Что вам действительно нужно, так это решение, которое объединяет оба списка К счастью, есть статья именно об этом, которая называется " Сопоставление складок с гиперфункциями " . р>
Вам нужен вспомогательный тип, гиперфункция, которая в основном является функцией, которая принимает другую гиперфункцию в качестве аргумента.
newtype H a b = H { invoke :: H b a -> b }
Гиперфункции, используемые здесь, в основном действуют как "стек" обычных функций.
push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q
Вам также нужен способ соединить две гиперфункции, одна в другую.
(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k
Это связано с push по закону:
(push f x) .#. (push g y) = push (f . g) (x .#. y)
Это оказывается ассоциативный оператор, и это тождество:
self :: H a a
self = H $ \k -> invoke k self
Вам также нужно что-то, что игнорирует все остальное в " стеке " и возвращает конкретное значение:
base :: b -> H a b
base b = H $ const b
И, наконец, вам нужен способ получить значение из гиперфункции:
run :: H a a -> a
run q = invoke q self
run объединяет все функции push , вместе, от начала до конца, пока не достигнет base или не зациклится бесконечно.
Итак, теперь вы можете сложить оба списка в гиперфункции, используя функции, которые передают информацию от одного к другому и собирают окончательное значение.
zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
first _ Nothing = []
first x (Just (y, xys)) = (x, y):xys
second y xys = Just (y, xys)
Причина, по которой сворачивание обоих списков имеет значение, заключается в том, что GHC делает это объединение списков , о котором говорится в модуль GHC.Base , но, вероятно, он должен быть гораздо более известным. Будучи хорошим производителем списков и используя build с foldr , вы сможете избежать большого количества бесполезного производства и немедленного потребления элементов списка, а также подвергнуть дальнейшей оптимизации.
Я пытался понять это элегантное решение сам, поэтому я попытался вывести типы и оценку самостоятельно. Итак, нам нужно написать функцию:
zip xs ys = foldr step done xs ys
Здесь нам нужно извлечь step и done , какими бы они ни были. Вспомните foldr Тип , созданный для списков:
foldr :: (a -> state -> state) -> state -> [a] -> state
Однако наш вызов foldr должен быть реализован примерно так, как показано ниже, потому что мы должны принять не один, а два аргумента списка:
foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]
Поскольку - > является ассоциативным правом , это эквивалентно:
foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])
Наш ([b] - > [(a, b)]) соответствует переменной типа state в исходном типе foldr подпись, поэтому мы должны заменить каждое вхождение state на нее:
foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
-> ([b] -> [(a,b)])
-> [a]
-> ([b] -> [(a,b)])
Это означает, что аргументы, которые мы передаем в foldr , должны иметь следующие типы:
step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]
Напомним, что foldr (+) 0 [1,2,3] расширяется до:
1 + (2 + (3 + 0))
Поэтому, если xs = [1,2,3] и ys = [4,5,6,7] , наш foldr вызов расширится до:
1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]
Это означает, что наша конструкция Поэтому мы не можем вернуть только Теперь давайте начнем выяснять, каким должен быть В Помните, что мы должны возвращать функцию, внутри которой мы каким-то образом заархивируем элементы. Приведенный выше код имеет смысл и проверки типов. Теперь, когда мы предположили, как именно должен оцениваться Оценка дает начало этой реализации шага (обратите внимание, что мы учитываем, что Таким образом, полная функция PS. Если вас вдохновляет элегантность сгибов, прочитайте Написание фолдов с использованием фальцовщика а затем учебник по универсальности и выразительности сгиба . 1 `step` (2` step` (3 `step` done)) должна создать рекурсивную функцию, которая будет проходить через [4,5,6 , 7] и заархивируйте элементы. (Имейте в виду, что если один из исходных списков длиннее, лишние значения отбрасываются). Итак, наша конструкция должна иметь тип [b] - > [(А, б)] .
3 `step` done - это наш базовый случай, где done - начальное значение, например 0 в foldr (+ ) 0 [1..3] . Мы не хотим архивировать что-либо после 3, потому что 3 является окончательным значением xs , поэтому мы должны прекратить рекурсию. Как прекратить рекурсию по списку в базовом случае? Вы возвращаете пустой список [] . Но вспомните подпись типа done : done :: [b] -> [(a,b)]
[] , мы должны вернуть функцию, которая игнорировала бы все, что она получает. Поэтому используйте const : done = const [] -- this is equivalent to done = \_ -> []
step . Он объединяет значение типа a с функцией типа [b] - > [(a, b)] и возвращает функцию типа [b] - > [(А, б)] .
и 3 `step` done мы знаем, что значение результата, которое позже попадет в наш сжатый список, должно быть (3,6) (зная из оригинала < code> xs ys ). Поэтому 3 `step` done должно вычисляться в: \(y:ys) -> (3,y) : done ys
step , давайте продолжим оценку. Вот как выглядят все этапы сокращения в нашей оценке foldr : 3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)
ys заканчивает элементы раньше, возвращая пустой список): step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys
zip реализована следующим образом: zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
where done = const []
step x f [] = []
step x f (y:ys) = (x,y) : f ys
Простой подход:
lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]
-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
where f (zs, (y:ys)) x = ((x,y):zs, ys)
-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
where f x (zs, (y:ys)) = ((x,y):zs, ys)
