Función de combinación de unión externa canónica

Question

Si considera los índices (implícitos) de cada elemento de una lista como sus claves, entonces zipWith es una especie de unión interna relacional. Solo procesa las claves para las cuales ambas entradas tienen valores:

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

¿Existe una función correspondiente canónica correspondiente a la unión externa? Algo así como:

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 

o tal vez

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 

Así que puedo hacer

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] 

me encuentro que necesitan de vez en cuando, y yo prefiero usar un lenguaje común a hacer que mi código sea más fácil de escribir (y más fácil de mantener) en lugar de implementar outerZipWith, o hacer if length as < length bs then zipWith f (as ++ repeat a) bs else zipWith f as (bs ++ repeat b).

Answer 1

Esto parece incómodo porque está tratando de saltear hasta el final en lugar de lidiar con las operaciones primitivas.

En primer lugar, zipWith es conceptualmente un zip seguido de map (uncurry ($)). Este es un punto importante, porque (des) currying es por qué zipWith es posible en absoluto. Las listas dadas con los tipos [a] y [b], para aplicar una función (a -> b -> c) y obtener algo del tipo [c], obviamente necesita una de cada entrada. Las dos formas de hacerlo son precisamente las dos instancias Applicative para las listas, y zipWith es liftA2 para una de ellas. (La otra instancia es la estándar, que otorga el producto cartesiano, una unión cruzada, si lo prefiere).

La semántica que desea no corresponde a ninguna instancia obvia de Applicative, por lo que es mucho más difícil. Considere primero un outerZip :: [a] -> [b] -> [?? a b] y qué tipo tendría. Los elementos de la lista de resultados podrían ser a, b, o ambos. Esto no solo no corresponde a ningún tipo de datos estándar, es incómodo expresarlo en términos de ellos porque no se puede factorizar nada útil de la expresión (A + B + A*B).

Este tipo de datos tiene sus propios usos, por lo que tengo my own package defining one. Recuerdo que también había uno en Hackage (con menos funciones auxiliares que las mías, creo) pero no recuerdo cómo se llamaba.

Si nos limitamos a las cosas estándar, terminas necesitando un "valor predeterminado" razonable que se traduce aproximadamente en tener una instancia de Monoid y usar el valor de identidad para rellenar las listas. Sin embargo, es posible que la traducción ay desde un Monoid apropiado usando contenedores newtype o similares no termine siendo más simple que su implementación actual.

---

Como comentario adicional, su comentario acerca de los índices de listas como claves puede desarrollarse aún más; cualquier Functor con una noción similar de una clave es isomorfa a la mónada Reader, a.k.a. una función explícita de las claves a los valores. Edward Kmett tiene, como siempre, un montón de paquetes que codifican estas nociones abstractas, en este caso construyendo desde the representable-functors package. Puede ser útil, si no te importa escribir una docena de instancias solo para empezar, al menos ...

Answer 2

En lugar de completar la lista más corta con una constante, ¿por qué no proporciona una lista de valores a tomar hasta que se alcanza el final de la lista más larga? Esto también elimina la necesidad de un Maybe ya que la lista puede estar vacía (o de longitud limitada).

no pude encontrar nada estándar, pero menos que una completa re-implementación de zipWith lo largo de las líneas que apareciste, he desarrollado la versión de prueba de length así:

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

Este tipo de cosas se acerca mucho. Es la operación cogroup del PACT algebra. Donde trabajo, hacemos uso de clases de tipos para diferenciar estas tres operaciones:

1. zip: intersección estructural.
2. align: Unión estructural.
3. liftA2: Producto cartesiano estructural.

Esto es discutido por Paul Chiusano on his blog.