Esistono applicazioni utili per la Classe di tipo divisibile?

Question

Ultimamente ho lavorato a un'API in Elm, dove uno dei tipi principali è controverso. Quindi, ho cercato su google per vedere cosa si può fare con i tipi controvarianti e abbiamo trovato che the Contravariant package in Haskell defines the Divisible type class.

Esso è definito come segue:

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

Si scopre che il mio tipo particolare si addice la definizione della classe tipo divisibile. Mentre Elm non supporta le lezioni di tipo, di tanto in tanto guardo ad Haskell per qualche ispirazione.

La mia domanda: Ci sono usi pratici per questa classe di tipo? Ci sono API conosciute là fuori in Haskell (o in altre lingue) che traggono beneficio da questo modello di divisione-conquista? Ci sono dei trucchi di cui dovrei essere a conoscenza?

Grazie mille per il vostro aiuto.

Answer 1

Esaminerò l'esempio dei tipi di dati principali nelle tecniche di ordinamento radix generalizzato di Fritz Henglein implementate da Edward Kmett nel pacchetto discrimination.

Mentre c'è una grande quantità succedendo lì, si concentra in gran parte intorno a un tipo come questo

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

Se si dispone di un valore di tipo Group a voi essenzialmente necessario disporre di una relazione di equivalenza su a perché se ti do un'associazione tra a s e qualche tipo b completamente sconosciuto a voi quindi potete darmi "raggruppamenti" di b.

groupId :: Group a -> [a] -> [[a]] 
groupId (Group grouper) = grouper . map (\a -> (a, a)) 

Si può vedere questo come un tipo di base per scrivere una libreria di utilità di raggruppamenti. Per esempio, potremmo voler sapere che se siamo in grado di Group a e Group b allora possiamo Group (a, b) (di più su questo in un secondo). L'idea di base di Henglein è che se è possibile iniziare con alcuni numeri di base Group su interi - possiamo scrivere implementazioni di tipo Group Int32 molto veloci tramite ordinamento digitale - e quindi utilizzare i combinatori per estenderli a tutti i tipi, quindi ordinare i tipi di dati algebrico generalizzati.

---

Quindi, come possiamo creare la nostra libreria combinatore?

Beh, f :: Group a -> Group b -> Group (a, b) è piuttosto importante in quanto ci consente di creare gruppi di tipi simili a prodotti. Normalmente, otterremmo questo da Applicative e liftA2 ma Group, noterete, è , non uno Functor.

Così, invece usiamo Divisible

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

Si noti che questo si pone in uno strano modo da

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

in quanto ha il carattere tipico "freccia rovesciata" delle cose controvarianti. Ora possiamo capire cose come divide e conquer in termini di interpretazione su Group.

Divide dice che se voglio costruire una strategia per equiparare a s utilizzando strategie per equiparare b s e c s, posso effettuare le seguenti operazioni per ogni tipo x

1. prendere il vostro rapporto parziale [(a, x)] e mappare su di esso con una funzione f :: a -> (b, c) e una piccola manipolazione della tupla, per ottenere una nuova relazione [(b, (c, x))].

2. Usa mia Group b di discriminare [(b, (c, x))] in [[(c, x)]]

3. Usa il mio Group c di discriminare ogni [(c, x)] in [[x]] darmi [[[x]]]

4. appiattire lo strati interni per ottenere [[x]] come abbiamo bisogno

   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 
   

Abbiamo anche ottenere interpretazioni del più complicato 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 

Questi lette come dire che per qualsiasi tipo a di cui siamo in grado di garantire non ci sono valori (non siamo in grado di produrre valori di Void con qualsiasi mezzo, una funzione a -> Void è un mezzo per produrre Void dato a, quindi non dobbiamo essere in grado di produrre valori di a con qualsiasi mezzo o!), subito ci un raggruppamento di valori zero

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

Possiamo anche andare ad un gioco simile a quello divide eccetto che invece di sequenziare il nostro uso dei discriminatori di input, ci alterniamo.

---

Usando queste tecniche costruiamo una libreria di "Group capaci" le cose, vale a dire Grouping

class Grouping a where 
    grouping :: Group a 

e notiamo che nearly all the definitions arise dalla definizione di base in cima groupingNat che utilizza veloci manipuations vettore monadici per raggiungere un efficiente radix sort.

Answer 2

Ecco un possibile caso d'uso.

Nelle librerie di streaming, uno può avere costrutti simili a quelli del pacchetto foldl, che ricevono una sequenza di input e restituiscono un valore di riepilogo quando la sequenza è esaurita.

Queste pieghe sono controvarianti sui loro ingressi e possono essere effettuate Divisible. Ciò significa che se si dispone di un flusso di elementi in cui ogni elemento può essere in qualche modo scomposto in parti b e c e si verifica anche una piegatura che consuma b s e un'altra piega che consuma c s, quindi è possibile creare una piegatura che consuma il flusso originale.

Le pieghe attuali da foldl non implementano Divisible, ma potrebbero, utilizzando un wrapper newtype. Nel mio pacchetto process-streaming ho un fold-like type che implementa Divisible.

divide richiede che i valori di ritorno delle pieghe costitutive siano dello stesso tipo e che il tipo deve essere un'istanza di Monoid. Se le pieghe restituiscono diversi monoidi non correlati, una soluzione consiste nel mettere ciascun valore restituito in un campo separato di una tupla, lasciando l'altro campo come mempty. Funziona perché una tupla di monoidi è essa stessa un Monoid.

Answer 3

Un esempio:

applicativo è utile per l'analisi, perché è possibile trasformare parser applicativi di parti in un parser di interi, che necessitano solo una pura funzione per combinare le parti in un tutto.

Divisibile è utile per la serializzazione (dovremmo chiamare questo coprocesso ora?

In realtà non ho visto un progetto che funzionasse in questo modo, ma sto (lentamente) lavorando a un'implementazione Avro per Haskell.

Quando ho incontrato divisibile volevo per divide, e non aveva idea di cosa possibile uso conquer potrebbe essere altro che barare (un f a dal nulla, per qualsiasi a?). Ma per fare in modo che le leggi Divisibili si presentino ai miei serializzatori, conquer è diventato un "serializzatore" che codifica byte qualsiasi a zero, il che ha molto senso.