Funzione zip dell'unione canonica esterna

Question

Se si considerano gli indici (impliciti) di ciascun elemento di un elenco come chiavi, allora zipWith è un po 'come un join interno relazionale. Elabora solo le chiavi per cui entrambi gli input hanno valori:

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

Esiste una funzione corrispondente canonica corrispondente all'unione esterna? Qualcosa di simile:

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 forse

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 

Così posso fare

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] 

mi trovo a dover di volta in volta, e io preferisco usare un idioma comune a rendere il mio codice più scrivibile (e più facile da mantenere) piuttosto che implementare outerZipWith o fare if length as < length bs then zipWith f (as ++ repeat a) bs else zipWith f as (bs ++ repeat b).

Answer 1

Questo sembra strano perché stai cercando di saltare alla fine piuttosto che affrontare le operazioni primitive.

Prima di tutto, zipWith è concettualmente uno zip seguito da map (uncurry ($)). Questo è un punto importante, perché (un) currying è il motivo per cui lo zipWith è possibile. Dati gli elenchi con i tipi [a] e [b], per applicare una funzione (a -> b -> c) e ottenere qualcosa di tipo [c] è ovviamente necessario uno di ciascun input. I due modi per farlo sono precisamente le due istanze Applicative per gli elenchi e zipWith è liftA2 per uno di essi. (L'altra istanza è quella standard, che dà il prodotto cartesiano - un cross join, se preferisci).

La semantica desiderata non corrisponde a nessuna istanza ovvia Applicative, motivo per cui è molto più difficile. Considerare prima un outerZip :: [a] -> [b] -> [?? a b] e quale tipo avrebbe. Gli elementi dell'elenco dei risultati possono essere ciascuno a, b o entrambi. Questo non solo non corrisponde a nessun tipo di dati standard, è imbarazzante da esprimere in termini di questi perché non è possibile calcolare nulla di utile dall'espressione (A + B + A*B).

Un tipo di dati di questo tipo ha i propri usi, motivo per cui ho my own package defining one. Ricordo che ce n'è uno anche in hackage (con meno funzioni ausiliarie del mio, penso) ma non riesco a ricordare come si chiamava.

Attaccando solo a cose standard, si finisce per avere bisogno di un "valore di default" ragionevole che si traduca approssimativamente in un'istanza Monoid e che utilizzi il valore di identità per riempire gli elenchi. La traduzione da e verso l'appropriato Monoid utilizzando i wrapper newtype o simili potrebbe non risultare più semplice dell'implementazione corrente, tuttavia.

---

Per inciso, il tuo commento sugli indici di elenco come chiavi può effettivamente essere ulteriormente sviluppato; qualsiasi Functor con una nozione simile di chiave è isomorfo alla monade Reader, a.k.a. una funzione esplicita dalle chiavi ai valori. Edward Kmett ha, come sempre, un sacco di pacchetti che codificano queste nozioni astratte, in questo caso costruendo da the representable-functors package. Potrebbe essere utile, se non ti dispiace scrivere una dozzina di casi solo per iniziare almeno ...

Answer 2

Invece di compilare la lista più breve con una costante, perché non fornire un elenco di valori da prendere fino al termine della lista più lunga? Ciò elimina anche la necessità di un Maybe poiché l'elenco può essere vuoto (o di lunghezza finita).

non ho trovato nulla di serie, ma a corto di un completo re-implementazione di zipWith lungo le linee che ha mostrato, ho sviluppato la versione di prova length come questo:

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

Questo genere di cose viene in su Un sacco. È l'operazione cogroup di PACT algebra. Dove lavoro, facciamo uso di classi di tipi per differenziare queste tre operazioni:

1. zip: intersezione strutturale.
2. align: unione strutturale.
3. liftA2: prodotto cartesiano strutturale.

Questo è discusso da Paul Chiusano on his blog.