Каноническая внешняя функция zip

Question

Если вы рассматриваете (неявные) индексы каждого элемента списка как их ключи, то zipWith является своего рода реляционным внутренним соединением. Он обрабатывает только те ключи, для которых оба входа имеют значения:

zipWith (+) [1..5] [10..20] == zipWith (+) [1..11] [10..14] == [11,13,15,17,19] 

Существует ли каноническая соответствующая функция, соответствующая внешнему объединению? Что-то вроде:

outerZipWith :: (a -> b -> c) -> a -> b -> [a] -> [b] -> [c]
outerZipWith _ _ _ [] [] = []
outerZipWith f a' b' [] (b:bs) = f a' b : outerZipWith f a' b' [] bs
outerZipWith f a' b' (a:as) [] = f a b' : outerZipWith f a' b' as []
outerZipWith f a' b' (a:as) (b:bs) = f a b : outerZipWith f a' b' as bs

или, может быть

outerZipWith' :: (a -> b -> c) -> Maybe a -> Maybe b -> [a] -> [b] -> [c]
outerZipWith' _ _ _ [] [] = []
outerZipWith' _ Nothing _ [] _ = []
outerZipWith' _ _ Nothing _ [] = []
outerZipWith' f a' b' [] (b:bs) = f (fromJust a') b : outerZipWith f a' b' [] bs
outerZipWith' f a' b' (a:as) [] = f a (fromJust b') : outerZipWith f a' b' as []
outerZipWith' f a' b' (a:as) (b:bs) = f a b : outerZipWith f a' b' as bs

Так что я могу сделать

outerZipWith (+) 0 0 [1..5] [10..20]  == [11,13,15,17,19,15,16,17,18,19,20]
outerZipWith (+) 0 0 [1..11] [10..14] == [11,13,15,17,19,6,7,8,9,10,11]

Время от времени я нуждаюсь в этом, и я предпочел бы использовать общую идиому, чтобы сделать мой код более доступным для записи (и легче поддерживать), чем реализовывать outerZipWith или выполнять if length as < length bs then zipWith f (as ++ repeat a) bs else zipWith f as (bs ++ repeat b).

Answer 1

Подобные вещи часто возникают. Это операция cogroup алгебры PACT . Там, где я работаю, мы используем классы типов, чтобы различать эти три операции:

1. zip: пересечение структур.
2. align: Структурный союз.
3. liftA2: структурное декартово произведение.

Это обсуждается Полом Кьюзано в его блоге .

Answer 2

Это кажется неловким, потому что вы пытаетесь пропустить до конца, а не иметь дело с примитивными операциями.

Прежде всего, zipWith концептуально представляет собой zip, за которым следует map (uncurry ($)).Это важный момент, потому что (не) каррирование - это то, почему zipWith вообще возможно.Имея списки с типами [a] и [b], чтобы применить функцию (a -> b -> c) и получить что-то типа [c], вам, очевидно, нужен один из каждого ввода.Два способа сделать это - два экземпляра Applicative для списков, а zipWith для одного из них - liftA2.(Другой пример является стандартным, который дает декартово произведение - перекрестное соединение, если вы предпочитаете).

Семантика, которую вы хотите, не соответствует ни одному очевидному Applicative случаю, поэтомуэто намного сложнее.Сначала рассмотрим outerZip :: [a] -> [b] -> [?? a b] и какой у него тип.Элементы списка результатов могут быть a, b или оба.Это не только не соответствует ни одному стандартному типу данных, это неудобно выражать через них, потому что вы не можете выделить что-то полезное из выражения (A + B + A*B).

Такой тип данных имеет свои собственныеиспользует, поэтому у меня есть мой собственный пакет, определяющий один .Я вспоминаю, что был один на взломе (с меньшим количеством вспомогательных функций, чем у меня, я думаю), но я не могу вспомнить, как он назывался.значение по умолчанию ", что примерно означает наличие Monoid экземпляра и использование значения идентификатора для дополнения списков.Однако перевод в / из соответствующего Monoid с использованием newtype упаковщиков или тому подобного может оказаться не таким простым, как ваша текущая реализация.

---

Кстати, ваше замечание об индексах списков в качестве ключейдействительно может развиваться дальше;любой Functor с подобным понятием ключа изоморфен монаде Reader, то есть явной функции от ключей до значений.У Эдварда Кметта, как всегда, есть множество пакетов, кодирующих эти абстрактные понятия, в данном случае это сборка из representable-functors пакета .Может быть полезно, если вы не возражаете написать десятки экземпляров, чтобы хотя бы начать ...

Answer 3

Вместо того, чтобы заполнять более короткий список константой, почему бы не предоставить список значений, которые нужно принять, пока не будет достигнут конец более длинного списка? Это также устраняет необходимость в Maybe, поскольку список может быть пустым (или конечной длины).

Я не смог найти ничего стандартного, но, если не считать полного повторного внедрения zipWith, как вы показали, я разработал вашу length тестовую версию следующим образом:

outerZipWith :: (a -> b -> c) -> [a] -> [b] -> [a] -> [b] -> [c]
outerZipWith f as bs as' bs' = take n $ zipWith f (as ++ as') (bs ++ bs')
  where n = max (length as) (length bs)