规范外连接 zip 函数

发布于 2025-01-03 12:45:33 字数 1420 浏览 5 评论 0原文

如果您将列表中每个元素的（隐式）索引视为它们的键，那么 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，或者如果长度为 则执行 length bs then zipWith f (as ++ Repeat a) bs else zipWith f as (bs ++ Repeat b)。

原文

If you consider the (implicit) indexes of each element of a list as their keys, then zipWith is sort of like a relational inner join. It only processes the keys for which both inputs have values:

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

Is there a canonical corresponding function corresponding to outer join? Something like:

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

or maybe

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

So I can do

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]

I find myself needing it from time to time, and I'd rather use a common idiom to make my code more writable (and easier to maintain) rather than implementing outerZipWith, or doing if length as < length bs then zipWith f (as ++ repeat a) bs else zipWith f as (bs ++ repeat b).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

っ左 2025-01-10 12:45:33

这种事情经常出现。这是的 cogroup 操作PACT 代数。在我工作的地方，我们利用类型类来区分这三个操作：

zip：结构交集。
align：结构联合。
liftA2：结构笛卡尔积。

Paul Chiusano 在他的博客上对此进行了讨论。

回复收藏 0 原文

舂唻埖巳落 2025-01-10 12:45:33

这看起来很尴尬，因为您试图跳到最后而不是处理原始操作。

首先，zipWith 在概念上是一个 zip 后跟 map (uncurry ($))。这是很重要的一点，因为（非）柯里化是 zipWith 成为可能的原因。给定类型为 [a] 和 [b] 的列表，应用函数 (a -> b -> c) 并获取[c] 类型的内容显然您需要每个输入之一。执行此操作的两种方法正是列表的两个 Applicative 实例，其中之一的 zipWith 是 liftA2 。（另一个实例是标准实例，它提供笛卡尔积——交叉连接，如果您愿意的话）。

您想要的语义不对应于任何明显的 Applicative 实例，这就是为什么它要困难得多。首先考虑一个 outerZip :: [a] -> [b]-> [？？ ab] 以及它的类型。结果列表的每个元素都可以是 a、b 或两者。这不仅不对应于任何标准数据类型，而且用它们来表达也很尴尬，因为您无法从表达式 (A + B + A*B) 中分解出任何有用的东西。

这样的数据类型有其自己的用途，这就是为什么我有我自己的包定义一个。我记得也有一个关于 hackage 的（我认为辅助功能比我的少），但我不记得它叫什么了。

坚持标准的东西，你最终需要一个合理的“默认值”，它大致翻译为拥有一个 Monoid 实例并使用标识值来填充列表。然而，使用 newtype 包装器等在适当的 Monoid 之间进行转换可能不会比当前的实现更简单。

顺便说一句，您关于列表索引作为键的评论实际上可以进一步发展；任何具有类似键概念的 Functor 都与 Reader monad 同构，也就是从键到值的显式函数。 Edward Kmett 一如既往地拥有一堆编码这些抽象概念的包，在本例中是从 <代码>可表示函子包。可能会有所帮助，如果您不介意编写十几个实例只是为了至少开始......

This seems awkward because you're trying to skip to the end rather than deal with the primitive operations.

First of all, zipWith is conceptually a zip followed by map (uncurry ($)). This is an important point, because (un)currying is why zipWith is possible at all. Given lists with types [a] and [b], to apply a function (a -> b -> c) and get something of type [c] you obviously need one of each input. The two ways to do this are precisely the two Applicative instances for lists, and zipWith is liftA2 for one of them. (The other instance is the standard one, which gives the cartesian product--a cross join, if you prefer).

The semantics you want don't correspond to any obvious Applicative instance, which is why it's much more difficult. Consider first an outerZip :: [a] -> [b] -> [?? a b] and what type it would have. The elements of the result list could each be an a, b, or both. This not only doesn't correspond to any standard data type, it's awkward to express in terms of them because you can't factor anything useful out of the expression (A + B + A*B).

Such a data type has its own uses, which is why I have my own package defining one. I recall there being one on hackage as well (with fewer auxiliary functions than mine, I think) but I can't remember what it was called.

Sticking to just standard stuff, you end up needing a sensible "default value" which roughly translates into having a Monoid instance and using the identity value to pad the lists out. Translating to and from an appropriate Monoid using newtype wrappers or such may not end up being any simpler than your current implementation, however.

As an aside, your remark about list indices as keys can actually be developed further; any Functor with a similar notion of a key is isomorphic to the Reader monad, a.k.a. an explicit function from keys to values. Edward Kmett has, as always, a bunch of packages encoding these abstract notions, in this case building from the representable-functors package. Might be helpful, if you don't mind writing a dozen instances just to get started at least...

回复收藏 0 原文

雾里花 2025-01-10 12:45:33

与其用常量填充较短的列表，为什么不提供一个值列表，直到到达较长列表的末尾为止？这也消除了对 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)

Instead of filling out the shorter list with a constant, why not provide a list of values to take until the end of the longer list is reached? This also eliminates the need for a Maybe since the list can be empty (or of finite length).

I couldn't find anything standard, but short of a complete re-implementation of zipWith along the lines you showed, I developed your length test version like this:

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)

回复收藏 0 原文

~没有更多了~