Tra Functional Applicativo e Monade

3

È possibile progettare un Functional applicativo con alcune funzioni extra di manipolazione dello stack push , pop e una funzione di branching specializzata ifA :: forall a. f Boolean -> f a -> f a -> f a , e ottenere un modello per il calcolo che sia uguale in potenza espressiva a una Monade ? (Può esprimere qualsiasi programma che un Monad può esprimere).

Un tale modello potrebbe essere utile per rappresentare il calcolo e mantenere un'analisi statica completa.

Potrebbe essere necessario digitare tipicamente un Functional Functional (Index Applicative Functor?) con un elenco eterogeneo. In modo che possa mantenere la sicurezza del tipo per push e pop .

Deve essere possibile in qualche modo. Perché un programma efficace può essere visto come un mono.

    
posta clinux 23.06.2016 - 02:35
fonte

1 risposta

2

tl; dr Credo statico ArrowChoice è ciò che stai cercando.

Per approfondire la tua domanda interessante: se vogliamo avere calcoli di ramificazione, dobbiamo essere in grado di passare gli output di un calcolo come input ai seguenti.

Per Applicative s gli effetti non possono dipendere dai risultati, possiamo immaginare che prima eseguiamo tutti gli effetti e quindi combiniamo tutti i risultati usando un puro calcolo. Pertanto possiamo rappresentare tale computazione con l'input i , l'output o e l'effetto m come m (i -> o) .

Gli effetti di Monad s possono dipendere completamente dagli input. Quindi possiamo rappresentare calcoli come i -> m o .

Se vogliamo ottenere una via di mezzo, dobbiamo parametrizzare i nostri calcoli sia in input che in output. Ed è così che arriviamo a Arrow s, che copre lo spazio tra Applicative se Monad s.

Proprio come ogni monade, ogni freccia a aumenta di un Applicative . Se fissiamo l'input, possiamo combinare due frecce a i o1 e a i o2 usando &&& (e quindi mappare la parte pura del risultato con >>> e arr ).

D'altra parte, da ogni% applicativo% co_de possiamo definire una freccia come f . Questo è il tipo più debole di una freccia: la sua potenza è equivalente solo a f (i -> o) . Tali frecce sono chiamate frecce statiche e possono essere riconosciute avendo un isomorfismo tra f e a i o (mentre abbiamo a () (i -> o) per qualsiasi freccia, esiste l'opposto solo per quelle statiche). In altre parole, l'effetto interno della freccia non dipende dal suo input.

All'altra estremità dello spettro abbiamo a () (i -> o) -> a i o frecce. Per qualsiasi monade possiamo costruire arrow Kleisli , il cui potere è equivalente alla monade.

La parte interessante è che possiamo avere frecce tra i -> m o e Monad . Un bell'esempio, che era la motivazione per inventare le frecce, è la combinazione di parser statici e dinamici ¸ Il parser ha una parte statica che determina l'insieme di caratteri che il parser è in grado di consumare successivamente, e questa parte statica è calcolata senza dover eseguire la freccia.

Immagino che la tua idea sia avere

ifA :: forall a. f Boolean -> f a -> f a -> f a

e per passare valori a calcoli ramificati usando le operazioni di stack. Direi che per le impostazioni funzionali è più naturale incorporare i valori nella ramificazione. Infatti, l'operazione più vicina in Applicative ( che descrive i calcoli che possono diramarsi) è

(|||) :: a b d -> a c d -> a (Either b c) d 

C'è un concetto ancora più generale - frecce generalizzate . Permette di rappresentare calcoli che non sono un superset di Haskell (in ArrowChoice possiamo incorporare qualsiasi funzione pura usando Arrow ), come i circuiti bidirezionali che possono essere usati sia per l'analisi che per la stampa carina.

    
risposta data 25.06.2016 - 21:11
fonte

Leggi altre domande sui tag