Come posso spingere il polimorfismo in una struttura dati?

Un recent question mi ha portato a chiedersi come convertire unCome posso spingere il polimorfismo in una struttura dati?

forall f . Functor f => [LensLike f s t a b]

in un

[ReifiedLens s t a b]

C'è un modo semplice per farlo molto lentamente, indicizzando nella lista con !!, ma è abbastanza incredibilmente inefficiente. Sembra che ci dovrebbe essere abbastanza parametrricità per tirare un trucco simile a quello utilizzato in reflection, ma non riesco a capire nulla. È possibile farlo in modo efficiente?

fonte

2015-10-12 dfeuer

Non penso che sia nemmeno possibile. Dovremmo andare (operativamente) da 'Functor f -> [LensLike f s t a b]' a '[Functor f -> LensLike f s t a b]'. Dobbiamo passare in un 'Functor f' per estrarre una lista per cominciare, e non ce n'è una in giro. –

@ AndrásKovács Forse possiamo usare un argomento parametrico per convincerci che le funzioni di tipo 'Functor f -> [LensLike f s t a b]' devono scegliere la lunghezza della loro lista di risultati senza esaminare l'argomento 'Functor f' in modo significativo. Quindi è facile ottenere il resto della strada da lì. (Naturalmente questa affermazione chiaramente non è vera per le funzioni di tipo 'Functor F -> [LensLike F s t a b]' per alcuni particolari 'F'.) –

@ AndrásKovacs, questa era la mia paura. Avremmo bisogno di una sorta di dizionario "superfunzionatore" che potremmo trasmettere e che sarebbe magicamente in grado di assumere l'identità di qualsiasi altro dizionario di 'Functor'. – dfeuer

testare la mia idea nei commenti, si può infatti scrivere questo direttamente passando attraverso ALens:

convert :: (forall f. Functor f => [LensLike f s t a b]) -> [ReifiedLens s t a b] 
convert ls = [Lens (cloneLens l) | l <- ls]

ALens si basa sul Pretext funtore:

type ALens s t a b = LensLike (Pretext (->) a b) s t a b 

newtype Pretext p a b t = Pretext { runPretext :: forall f. Functor f => p a (f b) -> f t }

Questo permette di utilizzare un singolo Functor per rappresentarli tutti, almeno per l'utilizzo della lente.

Mi chiedo ancora se esiste un metodo che funziona in generale e non solo per gli obiettivi.

fonte

2015-10-12 22:51:42

Trovo ancora sconcertante il "pretesto". Come applicato a '(->)', posso vederlo come una lente parzialmente applicata, ma la sua utilità e generalità mi confondono ancora. – dfeuer

Come posso spingere il polimorfismo in una struttura dati?

risposta

Problemi correlati