Kanoniczna zewnętrzna funkcja zipowania

Question

Jeśli weźmiesz pod uwagę (niejawne) indeksy każdego elementu listy jako klucze, to zipWith jest czymś w rodzaju relacyjnego sprzężenia wewnętrznego. Przetwarza tylko klucze, w których oba wejścia mają wartości:

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

Czy istnieje kanoniczny odpowiednia funkcja odpowiadająca sprzężenie zewnętrzne? Coś jak:

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 

czy może

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 

Więc mogę zrobić

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] 

znajdę się potrzebuje od czasu do czasu, a wolałbym używać wspólnego idiomu do spraw, aby mój kod był bardziej zapisywalny (i łatwiejszy w utrzymaniu) niż implementacja outerZipWith, lub wykonanie if length as < length bs then zipWith f (as ++ repeat a) bs else zipWith f as (bs ++ repeat b).

Answer 1

Wydaje się to niezręczne, ponieważ próbujesz przejść do końca, zamiast zajmować się prymitywnymi operacjami.

Po pierwsze, zipWith jest koncepcyjnie zip, po którym następuje map (uncurry ($)). Jest to ważna kwestia, ponieważ (nie) currying jest możliwe, w ogóle, możliwe jest zipWith. Biorąc pod uwagę listy o typach [a] i [b], aby zastosować funkcję (a -> b -> c) i uzyskać coś typu [c], oczywiście potrzebujesz jednego z każdego wejścia. Dwa sposoby na to są dokładnie dwie instancje Applicative dla list, a zipWith jest dla jednego z nich . (Innym przykładem jest standardowy, który daje produkt kartezjański - połączenie krzyżowe, jeśli wolisz).

Wybrana semantyka nie odpowiada żadnej oczywistej instancji Applicative, dlatego jest znacznie trudniejsza. Zastanówmy się najpierw nad numerem outerZip :: [a] -> [b] -> [?? a b] i jego typem. Elementy listy wyników mogą być pojedynczo lub oba. To nie tylko nie odpowiada żadnemu standardowemu typowi danych, ale jest niewygodne w wyrażaniu ich, ponieważ nie można zliczyć niczego użytecznego z wyrażenia (A + B + A*B).

Taki typ danych ma swoje własne zastosowania, dlatego mam my own package defining one. Przypominam sobie, że jest też jeden na hackage (z mniejszą ilością funkcji pomocniczych niż moja, jak sądzę), ale nie pamiętam, jak to się nazywało.

Trzymając się tylko standardowych rzeczy, kończy się potrzeba rozsądnej "wartości domyślnej", co z grubsza oznacza, że ​​ma instancję Monoid i używa wartości identyfikatora do wypakowania list. Przetłumaczenie na i z odpowiedniego opakowania Monoid przy użyciu newtype może jednak nie być prostsze niż twoja obecna implementacja.

---

Na marginesie, twoja uwaga na temat indeksów listy, ponieważ klucze mogą być dalej rozwijane; dowolne Functor z podobnym pojęciem klucza jest izomorficzne z monadą Reader, a.k.a. jawną funkcją od kluczy do wartości. Edward Kmett ma, jak zawsze, paczkę pakietów kodujących te abstrakcyjne pojęcia, w tym przypadku budując od the representable-functors package. Może być pomocna, jeśli nie masz nic przeciwko napisaniu kilkunastu przykładów, aby zacząć ...

Answer 2

Zamiast wypełniać krótszą listę stałą, może podać listę wartości, które należy wprowadzić, aż do osiągnięcia końca dłuższej listy? Eliminuje to również konieczność stosowania Maybe, ponieważ lista może być pusta (lub o skończonej długości).

nie mogłem znaleźć nic standard, ale krótki pełnego ponownego wykonania zipWith wzdłuż linii pokazałeś, opracowałem swój length wersji testowej tak:

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

Tego rodzaju rzeczy podchodzi dużo. Jest to operacja cogroup z PACT algebra. Gdzie pracuję, możemy skorzystać z zajęć typu odróżnić te trzy operacje:

1. zip: skrzyżowanie konstrukcyjny.
2. align: Unia strukturalna.
3. liftA2: Strukturalny produkt kartezjański.

Zostało to omówione przez Paul Chiusano on his blog.