Monade con Join () invece di Bind ()

Le Monadi vengono di solito spiegate in return di return e bind . Tuttavia, ritengo che sia ansible implementare il bind in termini di join (e fmap ?)

Nei linguaggi di programmazione che mancano funzioni di prima class, il bind è estremamente atroce da usare. join , d’altra parte, sembra abbastanza facile.

Non sono completamente sicuro di capire come funziona il join , comunque. Ovviamente, ha il tipo [Haskell]

 join :: Monad m => m (mx) -> mx

Per la lista monad, questo è banalmente e ovviamente concat . Ma per una monade generale, che cosa, in pratica, fa effettivamente questo metodo? Vedo cosa fa per le firme di tipo, ma sto cercando di capire come scrivere qualcosa di simile in, per esempio, Java o simile.

(In realtà, è facile: non lo farei, perché i farmaci generici sono infranti. 😉 Ma in linea di massima la domanda continua …)


    Ops. Sembra che questo sia stato chiesto prima:

    Funzione di join Monad

    Qualcuno potrebbe abbozzare alcune implementazioni di monadi comuni usando return , fmap e join ? (Cioè, non menzionando >>= affatto.) Penso che forse questo potrebbe aiutarlo ad affondare nel mio stupido cervello …

    Senza sondare le profondità della metafora, potrei suggerire di leggere un tipico monade come “strategia per produrre un”, quindi il m value tipo m value è una “strategia per produrre un valore” di prima class. Diverse nozioni di computazione o interazione esterna richiedono diversi tipi di strategia, ma la nozione generale richiede che una struttura regolare abbia senso:

    • se hai già un valore, allora hai una strategia per produrre un valore ( return :: v -> mv ) che consiste nient’altro che produrre il valore che hai;
    • se hai una funzione che trasforma un tipo di valore in un altro, puoi portarlo alle strategie ( fmap :: (v -> u) -> mv -> mu ) solo aspettando che la strategia fornisca il suo valore, quindi trasformi essa;
    • se hai una strategia per produrre una strategia per produrre un valore, allora puoi build una strategia per produrre un valore ( join :: m (mv) -> mv ) che segue la strategia esterna finché non produce la strategia interna, quindi segue quella strategia interiore fino ad un valore.

    Facciamo un esempio: alberi binari con etichette a foglia …

     data Tree v = Leaf v | Node (Tree v) (Tree v) 

    … rappresentano strategie per produrre cose lanciando una moneta. Se la strategia è Leaf v , c’è la tua v ; se la strategia è Node ht , lanci una moneta e prosegui con la strategia h se la moneta mostra “teste”, t se è “croce”.

     instance Monad Tree where return = Leaf 

    Una strategia che produce una strategia è un albero con foglie con l’albero: al posto di ciascuna di queste foglie, possiamo semplicemente innestare nell’albero che lo etichetta …

      join (Leaf tree) = tree join (Node ht) = Node (join h) (join t) 

    … e naturalmente abbiamo fmap che lascia solo relegazioni.

     instance Functor Tree where fmap f (Leaf x) = Leaf (fx) fmap f (Node ht) = Node (fmap fh) (fmap ft) 

    Ecco una strategia per produrre una strategia per produrre un Int .

    albero di alberi

    Lancia una moneta: se è “testa”, lancia un’altra moneta per decidere tra due strategie (producendo, rispettivamente, “lancia una moneta per produrre 0 o produrre 1” o “produrre 2”); se è “coda” ne produce un terzo (“lancia una moneta per produrre 3 o lanciare una moneta per 4 o 5”).

    Questo chiaramente si join a fare una strategia che produce un Int .

    inserisci la descrizione dell'immagine qui

    Quello a cui stiamo facendo riferimento è il fatto che una “strategia per produrre un valore” può essere vista come un valore. In Haskell, l’inserimento di strategie come valori è silenzioso, ma in inglese, uso le virgolette per distinguere usando una strategia semplicemente parlando di esso. L’operatore di join esprime la strategia “in qualche modo produce quindi segue una strategia” o “se ti viene detta una strategia, puoi usarla “.

    (Meta. Non sono sicuro che questo approccio alla “strategia” sia un modo abbastanza generico per pensare alle monadi e alla distinzione valore / calcolo, o se sia solo un’altra metafora scadente. Trovo che i tipi di albero simili a foglie siano utili fonte di intuizione, che forse non è una sorpresa in quanto sono le monadi libere , con la struttura sufficiente per essere monade, ma non di più.)

    PS Il tipo di “bind”

     (>>=) :: mv -> (v -> mw) -> mw 

    dice “se hai una strategia per produrre una v , e per ogni strategia di follow-on per produrre una w , allora hai una strategia per produrre una w “. Come possiamo catturarlo in termini di join ?

     mv >>= v2mw = join (fmap v2mw mv) 

    Possiamo rileggere la nostra strategia di produzione di v2mw , producendo invece di ogni valore v la strategia di w -producing che ne consegue: pronti per join !

     join = concat -- [] join f = \x -> fxx -- (e ->) join f = \s -> let (f', s') = fs in f' s' -- State join (Just (Just a)) = Just a; join _ = Nothing -- Maybe join (Identity (Identity a)) = Identity a -- Identity join (Right (Right a)) = Right a; join (Right (Left e)) = Left e; join (Left e) = Left e -- Either join ((a, m), m') = (a, m' `mappend` m) -- Writer join f = \k -> f (\f' -> f' k) -- Cont 

    OK, quindi non è una buona forma per rispondere alla tua domanda, ma prenderò nota del mio pensiero nel caso in cui illumini chiunque altro. (Ne dubito…)

    Se una monade può essere pensata come un “contenitore”, allora entrambi return e si join hanno semantica abbastanza ovvia. return genera un contenitore di 1 elemento e join trasforma un contenitore di contenitori in un singolo contenitore. Niente di difficile.

    Concentriamoci quindi sulle monadi che sono più naturalmente pensate come “azioni”. In tal caso, mx è una sorta di azione che produce un valore di tipo x quando lo “esegui”. return x non fa nulla di speciale, quindi restituisce x . fmap f esegue un’azione che produce una x costruisce un’azione che calcola x e quindi applica f ad essa e restituisce il risultato. Fin qui tutto bene.

    È abbastanza ovvio che se f genera di per sé un’azione, allora ciò che si finisce è m (mx) . Cioè, un’azione che calcola un’altra azione. In un certo senso, è forse ancora più semplice avvolgere la tua mente rispetto alla funzione >>= che prende un’azione e una “funzione che produce un’azione” e così via.

    Quindi, logicamente parlando, sembra che join possa eseguire la prima azione, prendere l’azione che produce e quindi eseguirla. (O meglio, join restituirebbe un’azione che fa quello che ho appena descritto, se vuoi dividere i capelli).

    Questa sembra essere l’idea centrale. Per implementare il join , devi eseguire un’azione, che ti dà quindi un’altra azione, e poi la esegui. (Qualunque cosa “corri” significhi per questa particolare monade).

    Data questa intuizione, posso provare a scrivere alcune implementazioni di join :

     join Nothing = Nothing join (Just mx) = mx 

    Se l’azione esterna è Nothing , restituisci Nothing , altrimenti restituisci l’azione interiore. Poi di nuovo, Maybe è più un contenitore che un’azione, quindi proviamo qualcos’altro …

     newtype Reader sx = Reader (s -> x) join (Reader f) = Reader (\ s -> let Reader g = fs in gs) 

    Quello era … indolore. Un Reader è in realtà solo una funzione che assume uno stato globale e restituisce solo il risultato. Quindi, per annullare l’operazione, si applica lo stato globale all’azione esterna, che restituisce un nuovo Reader . Quindi applichi lo stato anche a questa funzione interiore.

    In un certo senso, è forse più semplice del solito:

     Reader f >>= g = Reader (\ s -> let x = fs in gx) 

    Ora, quale è la funzione del lettore e quale è la funzione che calcola il prossimo lettore …?

    Ora proviamo la buona vecchia monade di State . Qui ogni funzione prende uno stato iniziale come input ma restituisce anche un nuovo stato insieme al suo output.

     data State sx = State (s -> (s, x)) join (State f) = State (\ s0 -> let (s1, State g) = f s0 in g s1) 

    Non era troppo difficile. È fondamentalmente eseguito seguito da run.

    Ho intenzione di smettere di digitare ora. Sentiti libero di indicare tutti i difetti e gli errori nei miei esempi …: – /

    Ho trovato molte spiegazioni di monadi che dicono “non devi sapere nulla sulla teoria delle categorie, in realtà, basti pensare alle monadi come burritos / tute spaziali / qualunque cosa”.

    In realtà, l’articolo che demistificava le monadi per me diceva solo quali categorie erano, descrivevano le monadi (compresi join e bind) in termini di categorie e non si preoccupavano di false metafore:

    Penso che l’articolo sia molto leggibile senza che sia richiesta molta conoscenza matematica.

    Chiamare fmap (f :: a -> mb) (x :: m a) produce valori (y :: m (mb)) quindi è molto naturale usare join per recuperare i valori (z :: mb) .

    Quindi il bind è definito semplicemente come bind ma f = join (fmap f ma) , ottenendo così la compositività Kleisly delle funzioni della varietà (:: a -> mb) , che è ciò a cui si riferisce in realtà:

     ma `bind` (f >=> g) = (ma `bind` f) `bind` g -- bind = (>>=) = (`bind` g) . (`bind` f) $ ma = join . fmap g . join . fmap f $ ma 

    E così, con flip bind = (=<<) , abbiamo

      ((g <=< f) =<<) = (g =<<) . (f =<<) = join . (g <$>) . join . (f <$>) 

    inserisci la descrizione dell'immagine qui

    Chiedere cosa sia una firma di tipo in Haskell è piuttosto come chiedere che cosa faccia un’interfaccia in Java.

    È, in un certo senso letterale, “non”. (Anche se, naturalmente, avrete in genere un qualche tipo di scopo associato, che è principalmente nella vostra mente, e per lo più non nell’implementazione.)

    In entrambi i casi si stanno dichiarando sequenze giuridiche di simboli nella lingua che verranno utilizzate nelle definizioni successive.

    Naturalmente, in Java, suppongo che si possa dire che un’interfaccia corrisponde a una firma di tipo che verrà implementata letteralmente nella VM. Puoi ottenere un po ‘di polimorfismo in questo modo: puoi definire un nome che accetta un’interfaccia e puoi fornire una definizione diversa per il nome che accetta un’interfaccia diversa. Qualcosa di simile accade in Haskell, dove puoi fornire una dichiarazione per un nome che accetta un tipo e poi un’altra dichiarazione per quel nome che tratta un tipo diverso.

    Questo è Monad spiegato in una foto. Le 2 funzioni nella categoria verde non sono componibili, quando vengono mappate alla categoria blu (in senso stretto, sono una categoria), diventano componibili. Monad tratta di trasformare una funzione di tipo T -> Monad in una funzione di Monad -> Monad .

    Monad ha spiegato in una foto.