Выполнить застежку-молнию с помощью foldr

Я нашел способ, очень похожий на ваш:

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

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

как показал Матиаст.

Для неродных 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 из-за ленивого вычисления.

Чтобы разбить это дальше:

Возьмите почтовый индекс при вводе: '(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 вызывает функцию с помощью

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))))

Это функция, которая теперь берет список с двумя элементами и архивирует их с помощью (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.

И это продолжается и т. д.

Ответ здесь уже был дан, но не (иллюстративный) вывод. Так что даже по прошествии всех этих лет, возможно, стоит добавить его.

На самом деле это довольно просто. Первый,

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) ...)))

следовательно, по эта-разложению

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 x1r1ys, где 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 x2r2ys1, в качестве следующего шага. Вот и все.

Когда ys короче, чем xs (или такой же длины), срабатывает корпус [] для f и обработка останавливается. Но если ys длиннее, чем xs, то корпус f[] не сработает, и мы перейдем к финальному приложению f xnz(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", а 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

и т.п.

Я сам попытался разобраться в этом элегантном решении, поэтому сам попытался вывести типы и оценку. Итак, нам нужно написать функцию:

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 мы знаем, что значение результата, которое позже попадет в наш заархивированный список, должно быть (3,6) (известно из исходных 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

P.S .: Если вас вдохновляет элегантность складок, прочтите Написание foldl с помощью foldr, а затем Учебник по универсальности и выразительности фальца Грэма Хаттона.

Проблема со всеми этими решениями для 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 может предотвратить много бесполезного производства и немедленного потребления элементов списка, а также может подвергнуть дальнейшую оптимизацию.

Простой подход:

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)