Czy są użyteczne aplikacje dla klasy typu Divisible?

Question

Ostatnio pracowałem nad API w Elm, gdzie jeden z głównych typów jest kontrowersyjny. Tak więc, zgłosiłem się dookoła, aby zobaczyć, co można zrobić z rodzajami przeciwwskazań i odkryłem, że the Contravariant package in Haskell defines the Divisible type class.

To jest zdefiniowany następująco:

class Contravariant f => Divisible f where 
    divide :: (a -> (b, c)) -> f b -> f c -> f a 
    conquer :: f a 

Okazuje się, że mój szczególny typ pasuje do definicji podzielna klasy typu. Podczas gdy Wiąz nie obsługuje klas typu, od czasu do czasu spoglądam na Haskella, by uzyskać jakąś inspirację.

Moje pytanie: Czy są jakieś praktyczne zastosowania dla tego typu lekcji? Czy są znane interfejsy API w Haskell (lub innych językach), które korzystają z tego wzoru podboju dzielenia? Czy są jakieś garsony, o których powinienem wiedzieć?

Dziękuję bardzo za pomoc.

Answer 1

Przyjrzę się przykładowi podstawowych typów danych w uogólnionych metodach sortowania radix Fritza Hengleina, zaimplementowanych przez Edwarda Kmetta w pakiecie discrimination.

Chociaż nie wiele się tam dzieje, to w dużej mierze koncentruje się wokół typu jak ten

data Group a = Group (forall b . [(a, b)] -> [[b]]) 

Jeśli masz wartość typu Group a ty zasadniczo musi mieć relację równoważności na a bo jeśli dam ci skojarzenie między a s i niektóre typu b całkowicie nieznany Ci następnie możesz dać mi "grupowania" b.

Możesz to zobaczyć jako typ rdzeniowy do pisania biblioteki narzędziowej grupowań. Na przykład, możemy chcieć wiedzieć, że jeśli możemy Group a i Group b, możemy Group (a, b) (więcej o tym w sekundę). Podstawową ideą Hengleina jest to, że jeśli zaczniesz od podstawowych liczb Group s na liczbach całkowitych - możemy pisać bardzo szybko implementacje przez sortowanie radiatryczne - a następnie użyć kombinatorów, aby rozszerzyć je na wszystkie typy, wtedy będziesz miał uogólnione sortowanie radix na algebraiczne typy danych.

---

Jak więc możemy zbudować naszą bibliotekę kombinatorów?

Cóż, f :: Group a -> Group b -> Group (a, b) jest bardzo ważne, ponieważ pozwala nam tworzyć grupy typów produktów. Zwykle otrzymamy to od Applicative i liftA2, ale zauważysz, że to , a nie Functor.

Zamiast więc używamy Divisible

divided :: Group a -> Group b -> Group (a, b) 

Zauważ, że wynika to w dziwny sposób z

divide :: (a -> (b, c)) -> Group b -> Group c -> Group a 

ponieważ ma typowy charakter „odwrócone strzałki” z kontrawariantny rzeczy. Możemy teraz zrozumieć takie rzeczy, jak divide i conquer pod względem ich interpretacji na Group.

Divide mówi, że jeśli chcę zbudować strategię zrównując a S przy zastosowaniu strategii zrównując b s i c s, mogę wykonać następujące czynności dla każdego typu x

1. Weź częściową zależność [(a, x)] i mapuj nad nim z funkcją f :: a -> (b, c) i małą manipulacją krotką, aby uzyskać nową relację [(b, (c, x))].

2. używać mojego Group b dyskryminować [(b, (c, x))] do [[(c, x)]]

3. Użyj mojego Group c dyskryminować każdy [(c, x)] do [[x]] podając mi [[[x]]]

4. spłaszczyć wewnętrznych warstw, aby uzyskać [[x]] jak musimy

   instance Divisible Group where 
       conquer = Group $ return . fmap snd 
       divide k (Group l) (Group r) = Group $ \xs -> 
       -- a bit more cleverly done here... 
       l [ (b, (c, d)) | (a,d) <- xs, let (b, c) = k a] >>= r 
   

Mamy również uzyskać interpretacje bardziej skomplikowane Decidable refinement of Divisible

class Divisible f => Decidable f where 
    lose :: (a -> Void) -> f a 
    choose :: (a -> Either b c) -> f b -> f c -> f a 

instance Decidable Group where 
    lose :: (a -> Void) -> Group a 
    choose :: (a -> Either b c) -> Group b -> Group c -> Group a 

one odczytywane jako powiedzenie, że dla każdego typu a którego możemy zagwarantować nie ma wartości (nie możemy produkować wartości Void za pomocą wszelkich środków, funkcja a -> Void jest sposobem wytwarzania Void podane a, więc nie musi być w stanie produkować wartości a wszelkimi środkami albo!), a następnie od razu uzyskać grupowanie wartości zerowe

lose _ = Group (\_ -> []) 

Możemy również przejść podobną grę jak do divide powyżej, z wyjątkiem tego, że zamiast sekwencjonowania naszego użycia dyskryminatorów wejściowych, wykonujemy naprzemiennie.

---

Korzystanie z tych technik budujemy bibliotekę „Group móc” rzeczy, a mianowicie Grouping

class Grouping a where 
    grouping :: Group a 

i zauważ, że nearly all the definitions arise od podstawowej definicji szczycie groupingNat który używa szybkich monadycznego manipuations wektorowej do osiągnięcia efektywny sortowanie radix.

Answer 2

Oto możliwy przypadek użycia.

W bibliotekach strumieniowania można tworzyć konstrukcje podobne do składanych, takie jak te z pakietu foldl, które są dostarczane z sekwencją wejść i zwracają wartość podsumowania po wyczerpaniu sekwencji.

Te fałdy są sprzeczne z ich danymi wejściowymi i mogą być wykonane jako Divisible. Oznacza to, że jeśli masz strumień elementów, w którym każdy element może zostać w jakiś sposób rozłożony na części b i c, a także ma się fałd, który zużywa b s, a także inny fałd zużywający s, to możesz zbudować fałd, który zużywa oryginalny strumień.

Rzeczywiste fałdy z foldl nie implementują Divisible, ale mogą, używając opakowania nowego typu. W moim pakiecie process-streaming mam fold-like type, który wykonuje implementację Divisible.

divide wymaga, aby zwracane wartości fałdów składowych były tego samego typu, a ten typ musi być instancją Monoid. Jeśli fałdy zwracają różne, niepowiązane monoidy, obejście polega na umieszczeniu każdej wartości zwracanej w oddzielnym polu krotki, pozostawiając drugie pole jako mempty. Działa to, ponieważ krotka kumulacja monoidów sama w sobie jest Monoid.

Answer 3

Jeden przykład:

aplikacyjnych jest przydatny do analizowania, ponieważ można włączyć aplikacyjnych parsery części do parsera w całości, potrzebując jedynie czystą funkcję łączenia części w całość.

Dzielność jest przydatna do serializacji (czy teraz możemy to teraz nazwać?), Ponieważ można przekształcić podzielne serializatory części w serializator całości, wymagając jedynie czystej funkcji do dzielenia całości na części.

Nie widziałem tak naprawdę projektu, który działałby w ten sposób, ale ja (powoli) pracuję nad implementacją Avro dla Haskella, która to robi.

Kiedy pierwszy raz natknąłem podzielna Chciałem go divide i nie miał pojęcia, co możliwe użycie conquer mogłyby być inne niż oszustwo (to f a znikąd, za każdym a?). Ale aby prawa Divisible były sprawdzane dla moich serializatorów, conquer stał się "serializatorem", który koduje wszystko do zera bajtów, co ma wiele sensu.