Внедрение zip с помощью foldr

Ответ 1

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

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

Ответ 2

Я нашел способ, использующий довольно похожий метод для вашего:

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a 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) ...)))

следовательно, 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

и др.

Ответ 4

Для нелокальных 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.

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

Ответ 5

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

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 Учебник по универсальности и выразительности складок.

Ответ 6

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

Ответ 7

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

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)