В настоящее время я нахожусь в главе 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)
Как это работает: (foldr step done xs) возвращает функцию, которая потребляет YS; поэтому мы идем вниз по списку xs, создавая вложенный состав функции, которые будут применены к соответствующей части ys.
Как это сделать: я начал с общей идеи (из аналогичных примеры, увиденные ранее), написал
zip2 xs ys = foldr step done xs ys
затем заполнил каждую из следующих строк, в свою очередь, тем, что ей было чтобы сделать типы и значения правильными. Проще всего было рассмотрите простейшие случаи сначала перед более трудными.
Первая строка может быть написана просто как
zip2 = foldr step done
как показал матиаст.
Я нашел способ, использующий довольно похожий метод для вашего:
myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
where step a f (b:bs) = (a,b):(f bs)
step a f [] = []
Ответ уже был дан здесь, но не (иллюстративный) вывод. Поэтому даже после всех этих лет, возможно, стоит добавить его.
На самом деле это довольно просто. Во-первых,
foldr f z xs = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn]) = ... = f x1 (f x2 (f x3 (... (f xn z) ...)))
следовательно, eta-разложением,
foldr f z xs ys = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys = ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys
Как видно здесь, если f не является принудительным во втором аргументе, он сначала начинает работать на x1 и ys, f x1 r1 ys где r1 = (f x2 (f x3 (... (f xn z) ...))) = foldr f z [x2,x3,...,xn].
Итак, используя
f x1 r1 [] = [] f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1
мы организуем прохождение информации слева направо по списку, вызывая r1 с остальной частью списка ввода ys1, foldr f z [x2,x3,...,xn] ys1 = f x2 r2 ys1, как следующий шаг. И это.
Когда ys короче xs (или той же длины), срабатывает случай [] для f, и обработка останавливается. Но если ys больше, чем xs, тогда f [] случай не срабатывает, и мы перейдем к окончательному приложению f xn z (yn:ysn),
f xn z (yn:ysn) = (xn,yn) : z ysn
Поскольку мы достигли конца xs, обработка zip должна быть остановлена:
z _ = []
И это означает, что нужно использовать определение 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 s ", а z = const [], nil -case в foldr, - это" что сделано с ys, когда больше нет x s ". Или f может остановиться сам по себе, возвращая [], когда ys исчерпан.
Обратите внимание, что ys используется как своего рода накопительное значение, которое передается слева направо по списку xs, от одного вызова f к следующему (этап "накапливания", снятие с него элемента головки).
Естественно это соответствует левой складке, где этап накопления - "применение функции", при этом z = id возвращает окончательное накопленное значение когда "больше нет x s":
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
и др.
Для нелокальных Haskellers здесь я написал версию этого алгоритма, чтобы сделать более понятным, что на самом деле происходит:
> (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 скрывает внутренний lambda из-за ленивой оценки.
Чтобы сломать его дальше:
Возьмите zip на входе: '(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))))
Это func, который теперь берет список с двумя элементами и застегивает их с помощью (list 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, в этом случае, (list 9 1)
(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))
И, как вы помните, f связывает свой аргумент с 3.
И это продолжается и т.д.
Я попытался понять это элегантное решение самостоятельно, поэтому я попытался получить типы и оценку самостоятельно. Итак, нам нужно написать функцию:
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]
Это означает, что наша конструкция 1 `step` (2 `step` (3 `step` done)) должна создать рекурсивную функцию, которая пройдет через [4,5,6,7] и застегнет элементы. (Имейте в виду, что если один из исходных списков длиннее, избыточные значения отбрасываются). IOW, наша конструкция должна иметь тип [b] -> [(a,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] -> [(a,b)].
В 3 `step` done мы знаем, что результат результата, который позже перейдет в наш zip-список, должен быть (3,6) (зная исходные xs и ys). Поэтому 3 `step` done должно оцениваться в:
\(y:ys) -> (3,y) : done ys
Помните, мы должны вернуть функцию, внутри которой мы как-то застегиваем элементы, приведенный выше код - это то, что имеет смысл и typechecks.
Теперь, когда мы предположили, насколько точно следует оценивать 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
PS: Если вы вдохновлены элегантностью складок, прочитайте Написание сложения с помощью foldr, а затем Graham Hutton Учебник по универсальности и выразительности складок.
Проблема со всеми этими решениями для zip заключается в том, что они только складываются по одному списку или другому, что может быть проблемой, если оба они являются "хорошими производителями", на языке списка слияния. То, что вам действительно нужно, - это решение, которое складывается по обоим спискам. К счастью, есть статья о том, что называется "Coroutining Folds with Hyperfunctions" .
Вам нужен вспомогательный тип - гиперфункция, которая в основном является функцией, которая принимает в качестве аргумента другую гиперфункцию.
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 ed вместе, до конца, до тех пор, пока он не достигнет 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 действительно называется списком fusion, о котором говорится в модуле GHC.Base, но, вероятно, должно быть гораздо более известным. Являясь хорошим составителем списка и используя build с foldr, вы можете предотвратить много бесполезного производства и немедленного потребления элементов списка, а также предоставить дополнительные оптимизации.
Простой подход:
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)