Функция канонического внешнего соединения zip

Если вы считаете (неявные) индексы каждого элемента списка их ключами, то 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).


zip outer-join haskell
person rampion    schedule 08.02.2012    source источник

Ответы (3)


arrow_upward
5
arrow_downward

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

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

person C. A. McCann    schedule 08.02.2012
comment
Не outerZip :: a -> b -> [a] -> [b] -> [(a,b)]? - person pat; 08.02.2012
comment
Больше похоже на outerZip :: (a -> c) -> (b -> d) -> c -> d -> [a] -> [b] -> [(c, d)] - person Apocalisp; 08.02.2012
comment
Включающий или тип (например, ваш These) может быть необходимым первым шагом. По крайней мере, это хорошее место для начала. - person rampion; 08.02.2012
comment
outerZip f a b as bs = map (f . fromThese a b) $ zipThese as bs очень чисто. Мне это нравится. - person rampion; 08.02.2012
comment
Кроме того, с точки зрения факторинга, учитывая These, теперь у нас есть два представления для a + b + a*b + 1: Maybe (These a b), (Maybe a, Maybe b). - person rampion; 08.02.2012
comment
@pat: не обязательно. Это может быть, в зависимости от вашего выбора того, как обрабатывать прошлые случаи конца одного списка. Вам необходимо выразить выходные данные как явно включающие или для полной общности, или предоставить эквивалентные функции внедрения/проекции, которые служат той же цели. - person C. A. McCann; 08.02.2012
comment
@rampion: Только последнее на самом деле является факторизацией в том смысле, что у каждого аргумента типа есть уникальный слот. These просто дает имя конкретному, довольно простому выражению, которое не учитывается. - person C. A. McCann; 08.02.2012
comment
@Apocalisp: эта подпись типа, возможно, все еще слишком всеобъемлющая, поскольку она явно не исключает создание дополнительных пар с использованием аргументов c и d. С zip тип ясно показывает, что единственными представленными результатами будут пары, составленные из элементов, найденных во входных данных. - person C. A. McCann; 08.02.2012
comment
@rampion: О, также - поскольку сбор подобных входных данных в качестве промежуточного шага является очевидным использованием для такого типа, как These, я попытался быть очень полным с проекциями, функциями анализа случаев и предикатами для These, в частности, для поддержки четкого определения такие вещи, как ваш outerZip. :] - person C. A. McCann; 08.02.2012

arrow_upward
8
arrow_downward

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

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

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

person Apocalisp    schedule 08.02.2012
comment
Эта запись в блоге Пола Кьюзано проста и проницательна. Спасибо, что связали это. - person Luis Casillas; 09.02.2012

arrow_upward
3
arrow_downward

Вместо того, чтобы заполнять более короткий список константой, почему бы не предоставить список значений, которые будут приниматься до тех пор, пока не будет достигнут конец более длинного списка? Это также устраняет необходимость в 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)
person pat    schedule 08.02.2012
comment
Это не компилируется (по крайней мере, для меня). - person Andy Hayden; 22.10.2012