Функция канонического внешнего соединения 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

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

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

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

Такой тип данных имеет свои собственные применения, поэтому у меня есть my own package defining one. Я помню, что там тоже был хакер (с меньшим количеством вспомогательных функций, чем у меня, я думаю), но я не могу вспомнить, как это называется.

Придерживаясь стандартного материала, вы нуждаетесь в разумном «значении по умолчанию», которое в переводе означает, что оно имеет экземпляр Monoid и использует значение идентификатора для заполнения списков. Тем не менее, перевод с подходящего Monoid с использованием оберток newtype или, возможно, не будет таким простым, как ваша текущая реализация.

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

Answer 2

Вместо того, чтобы заполнять более короткий список с константой, почему бы не указать список значений, которые нужно принять до тех пор, пока не будет достигнут конец более длинного списка? Это также устраняет необходимость в 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) 

Answer 3

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

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

Это обсуждается Paul Chiusano on his blog.