Canonical outer join

Question

If you consider the (implicit) indices of each list item as your keys, then zipWith is a kind of relational inner join. It processes only 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 the outer join? Sort of:

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

or maybe

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

So what can i 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 need to need this from time to time, and I would 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) .

Answer 1

This seems inconvenient because you are trying to skip to the end rather than processing primitive operations.

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

The semantics you want do not match any obvious Applicative instance, so this is a lot more complicated. First, consider a outerZip :: [a] -> [b] -> [?? ab] outerZip :: [a] -> [b] -> [?? ab] and what type it will have. The items in the result list can be a , b or both. This not only does not correspond to standard data types, but it is inconvenient to express them in terms, because you cannot use anything useful from the expression (A + B + A*B) .

This type of data has its own applications, so I have my own package that defines one . I remember that there was also a hacker (with fewer auxiliary functions than mine, I think), but I can’t remember what it was called.

Adhering to standard material, you need a reasonable "default value" that roughly corresponds to having a Monoid instance and using an identifier value to populate the lists. However, wrapping using Monoid using newtype wrappers, etc. May not be simpler than your current implementation.

---

As an aside, your remark about list indexes in the form of keys can really be developed further; Any Functor with a similar key concept is isomorphic to the Reader monad, aka an explicit function from keys to values. Edward Kmett, as always, a bunch of packages encoding these abstract concepts, in this case builds a representable-functors . It may be useful if you do not mind writing a dozen copies to start at least ...

Answer 2

This kind of thing is a lot. This is the cogroup operation of the PACT algebra. Where I work, we use type classes to differentiate these three operations:

• zip : Structural intersection.
• align : Structural union.
• liftA2 : Structurally Cartesian product.

This is discussed by Paul Chiusano on his blog .

Answer 3

Instead of filling the shorter list with a constant, why not specify a list of values ​​that will be executed until the end of the longer list is reached? This also eliminates the need for Maybe , as the list may be empty (or of finite length).

I could not find anything standard, but without a complete re-implementation of zipWith along the lines you showed, I developed a test version of length as follows:

 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)