Canonical外部连接zip功能 [英] Canonical outer join zip function
问题描述
如果将列表中每个元素的（隐式）索引作为它们的键，那么 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
outerZipW a f b'（a：as）[] = fa b'：outerZipW a f'b'as []
outerZipWith f a'b'（a：as）（b：bs ）= fab：outerZip以f a'b'为bs
或者可能
outerZipWith'::（a - > b - > c） - >也许是 - >也许b - > [a] - > [b] - > [c]
outerZipWith'_ _ _ [] [] = []
outerZipWith'_ Nothing _ [] _ = []
outerZipWith'_ _ Nothing _ [] = []
outerZipWith'f a'b'[]（b：bs）= f（fromJust a'）b：outerZipWa'b'[] bs
outerZipWith'f a'b'（a：as （a：as）（b：bs）= fab：outerZip With f a'b'）[] = fa（fromJust b'）：outerZipWith f a'b'as []
outerZipWith' as bs
所以我可以做
pre> 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 ，或者如果长度<< c $ c> （bs ++重复b）。
首先，<$ c> $ c> zipWith 在概念上是一个 zip ，然后是 map（uncurry（$）） 。这是一个重要的观点，因为（un）currying是为什么 zipWith 是完全可能的。给定一个带有 [a] 和 [b] 类型的列表来应用函数（a - > b - > c）并获得 [c] 类型的东西，您显然需要每个输入中的一个。执行此操作的两种方法恰恰是列表的两个 Applicative 实例，而 zipWith 是 liftA2 为其中之一。 （另一个实例是标准实例，如果您愿意，它可以提供笛卡尔产品 - 交叉连接）。
您想要的语义与任何显然 Applicative 实例，这就是为什么它更困难。首先考虑 outerZip :: [a] - > [b] - > [??一个b] 和它会有什么类型。结果列表中的元素可以各自为 a ， b 或两者。这不仅不符合任何标准数据类型，用它们表达它们是很尴尬的，因为你不能从表达式（A + B + A * B） code>。
这种数据类型有它自己的用途，这就是为什么我有我自己的软件包定义了一个。我记得还有一个关于hackage的问题（我认为辅助函数比我的要少），但我不记得它是什么。
坚持标准东西，你最终需要一个明智的默认值，它大致转化为具有 Monoid 实例并使用标识值填充列表。使用 newtype 包装器等来自适当的 Monoid 的转换可能不会比目前的实现更简单，但是。
除此之外，您对列表索引作为键的评论实际上可以进一步发展;任何具有类似键概念的 Functor 同构于 Reader monad，也可以是从键到值的显式函数。 Edward Kmett一如既往地一堆编码这些抽象概念的包，在这种情况下，可以从 表示函子包。可能会有帮助，如果你不介意写十几个实例，至少要开始......
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).
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...
这篇关于Canonical外部连接zip功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
