Costrutti di calcolo (Monade, Frecce, ecc.)

Question

Sono diventato piuttosto interessato a come il calcolo è modellato in Haskell. Diverse risorse hanno descritto le monadi come "computazione componibile" e le frecce come "viste astratte del calcolo". Non ho mai visto i monoidi, i funtori o i funtori applicativi descritti in questo modo. Sembra che manchino della struttura necessaria.

Trovo l'idea interessante e mi chiedo se ci sono altri costrutti che fanno qualcosa di simile. Se sì, quali sono alcune risorse che posso usare per familiarizzare con loro? Ci sono pacchetti su Hackage che potrebbero tornare utili?

Nota: Questa domanda è simile a Monads vs. Arrows e https://stackoverflow.com/questions/2395715/resources-for-learning-monads-functors-monoids-arrows-etc, ma cerco di costrutti di là funtors, funtori applicative, monadi, e frecce.

Modifica: Ammetto che i funtori applicativi dovrebbero essere considerati "costrutti computazionali", ma sono davvero alla ricerca di qualcosa che non ho ancora incontrato. Questo include i funtori applicativi, le monadi e le frecce.

Answer 1

Arrows sono generalizzati per Categorie, quindi dalla classe Category.

class Category f where 
    (.) :: f a b -> f b c -> f a c 
    id :: f a a 

La definizione typeclass Arrow ha Category come superclasse. Le categorie (nel senso haskell) generalizzano le funzioni (è possibile comporle ma non applicarle) e quindi sono decisamente un "modello di calcolo". Arrow fornisce uno Category con struttura aggiuntiva per lavorare con le tuple. Quindi, mentre Category rispecchia qualcosa sullo spazio delle funzioni di Haskell, Arrow lo estende a qualcosa sui tipi di prodotto.

Ogni Monad dà origine a qualcosa chiamato "Categoria Kleisli" e questa struttura fornisce istanze di ArrowApply. Puoi creare un Monad su qualsiasi ArrowApply in modo tale che il giro completo non cambi il tuo comportamento, quindi in alcuni aspetti profondi Monad e ArrowApply sono la stessa cosa.

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b } 

instance Monad m => Category (Kleisli m) where 
    id = Kleisli return 
    (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f) 

instance Monad m => Arrow (Kleisli m) where 
    arr f = Kleisli (return . f) 
    first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d)) 
    second (Kleisli f) = Kleisli (\ ~(d,b) -> f b >>= \c -> return (d,c)) 

realtà ogni Arrow può giustificare un Applicative (universalmente quantificata per ottenere i giusti tipi) oltre ai Category superclasse, e credo che la combinazione del competente Category e Applicative è sufficiente per ricostruire il Arrow.

Quindi, queste strutture sono profondamente connesse.

Avvertenza: posticipato in anticipo. Una differenza centrale tra la Functor/Applicative/Monad modo di pensare e il modo Category/Arrow di pensare è che, mentre Functor ed il suo ilk sono generalizzazioni al livello di oggetto (tipi a Haskell), Category/Arrow sono generelazation del nozione di morfismo (funzioni in Haskell). Credo che pensare al livello del morfismo generalizzato implichi un livello più alto di astrazione rispetto al pensare a livello di oggetti generalizzati . A volte è una buona cosa, altre volte no. D'altra parte, nonostante il fatto che lo Arrows abbia una base categorica, e nessuno in matematica pensa che Applicative sia interessante, sono convinto che lo Applicative sia generalmente compreso meglio di Arrow.

Fondamentalmente si può pensare di "Categoria < Freccia < ArrowApply" e "Functor < applicativo < Monade" tale che "Categoria ~ Functor", "Freccia ~ applicativo" e "ArrowApply ~ Monad".

Ulteriori cemento sottostante: Come per altre strutture per modello di calcolo: spesso si può invertire la direzione delle "frecce" (solo significato morphisms qui) nelle costruzioni categoriali per ottenere il "doppio" o "co-costruzione ". Così, se una monade è definito come

class Functor m => Monad m where 
    return :: a -> m a 
    join :: m (m a) -> m a 

(ok, lo so che non è come Haskell definisce le cose, ma ma >>= f = join $ fmap f ma e join x = x >>= id in modo altrettanto bene potrebbe essere) poi il comonad è

class Functor m => Comonad m where 
    extract :: m a -> a -- this is co-return 
    duplicate :: m a -> m (m a) -- this is co-join 

Questa cosa risulta essere abbastanza comune anche. Risulta che Comonad è la struttura di base di base degli automi cellulari . Per completezza, vorrei sottolineare che di Edward Kmett Control.Comonad mette duplicate in una classe tra il funtore e Comonad per "allungabili Funtori", perché si possono anche definire

extend :: (m a -> b) -> m a -> m b -- Looks familiar? this is just the dual of >>= 
    extend f = fmap f . duplicate 
    --this is enough 
    duplicate = extend id 

Si scopre che tutti i Monad s sono anche "allungabile"

monadDuplicate :: Monad m => m a -> m (m a) 
    monadDuplicate = return 

mentre tutti Comonads sono "assemblabili"

comonadJoin :: Comonad m => m (m a) -> m a 
    comonadJoin = extract 

così

queste strutture sono molto vicine tra loro.

Answer 2

Tutte le Monads sono Frecce (Monade isomorphic to ArrowApply). In un modo diverso, tutte le Monade sono istanze di Applicative, dove <*> è Control.Monad.ap e *> è >>. Applicativo è più debole perché non garantisce l'operazione >>=. Quindi Applicative acquisisce calcoli che non esaminano i risultati precedenti e si ramificano sui valori. In retrospettiva, molto codice monadico è in realtà applicato, e con una riscrittura pulita ciò accadrebbe.

Estendendo le monadi, con i recenti tipi di vincoli in GHC 7.4.1, ora è possibile creare modelli più belli per restricted monads. E ci sono anche persone che guardano allo parameterized monads e ovviamente includo un collegamento a qualcosa di Oleg.

Answer 3

Nelle librerie queste strutture danno origine a diversi tipi di calcoli.

Ad esempio, è possibile utilizzare i candidati per implementare effetti statici. Con ciò intendo effetti, che sono definiti in anticipo. Ad esempio quando si implementa una macchina a stati, rifiutando o accettando uno stato di input. Non possono essere usati per manipolare la loro struttura interna in termini di input.

Il tipo dice tutto:

<*> :: f (a -> b) -> f a -> f b 

È facile ragione, la struttura di f non può essere dipendere om all'ingresso di un. Perché non è possibile raggiungere f a livello di testo.

Le Monade possono essere utilizzate per effetti dinamici. Questo può anche essere motivato dalla firma del tipo:

>>= :: m a -> (a -> m b) -> m b 

Come si può vedere questo? Perché un è sullo stesso "livello" di m. Matematicamente è un processo a due fasi. Bind è una composizione di due funzioni: fmap e join. In primo luogo usiamo FMAP insieme con l'azione della monade per creare una nuova struttura incorporato in quello vecchio:

fmap :: (a -> b) -> m a -> m b 
f :: (a -> m b) 
m :: m a 
fmap f :: m a -> m (m b) 
fmap f m :: m (m b) 

FMAP può creare una nuova struttura, in base al valore di ingresso. Poi crolliamo struttura con join, così siamo in grado di manipolare la struttura all'interno della computazione monadic in un modo che dipende dall'input:

join :: m (m a) -> m a 
join (fmap f m) :: m b 

Molti monadi sono più facili da implementare con join:

(>>=) = join . fmap 

Ciò è possibile con monadi:

addCounter :: Int -> m Int() 

ma non con applicativi, ma applicativi (e qualsiasi monade) può fare cose come:

addOne :: m Int() 

Le frecce danno più controllo sull'input e sui tipi di output, ma per me si sentono davvero simili agli applicativi. Forse mi sbaglio di questo.