MonadParallel Instance for Rand

Question

Attualmente sto lavorando con i calcoli in ReaderT r (Rand StdGen) a che vorrei eseguire in parallelo. Mi sono imbattuto in Monad Parallel che sembra che farà quello che voglio.

C'è già un'istanza di MonadParallel per ReaderT ma ho dovuto creare il mio per Rand da monad-random. Tuttavia, non sono sicuro di averlo fatto bene. Non ho molta familiarità con la programmazione parallela in Haskell, ma credo che ci sia da aspettarsi che l'esecuzione di comparse in parallelo debba dare lo stesso valore di quando vengono eseguite normalmente. Poiché la mia istanza di bindM2 per Rand utilizza split (e quindi ottiene un diverso insieme di numeri casuali dallo stesso generatore iniziale), questo non è il caso della mia istanza.

instance P.MonadParallel (Rand StdGen) where 
    bindM2 f ma mb = do 
     split1 <- getSplit 
     split2 <- getSplit 
     let a = evalRand ma split1 
     let b = evalRand mb split2 
     a `par` b `pseq` f a b 

Mentre sento che c'è un caso per ignorare questo (i numeri sono ancora casuali, giusto?) Anche io non posso fare a meno di pensare che mi manca qualcosa. Va bene o c'è una soluzione migliore?

Answer 1

La mia preoccupazione principale è che questo viola la garanzia che:

A parte la possibile ordine di effetti collaterali, questa funzione è equivalente a \f ma mb-> do {a <- ma; b <- mb; f a b}

Questi avranno risultati diversi:

let g = mkStdGen 0 
    r = evalRand (do x <- getRandom 
        y <- getRandom 
        return (x, y)) g 

vs

let g = mkStdGen 0 
    r = evalRand (P.bindM2 (\x y -> return (x,y)) getRandom getRandom) g 

Questo solleva domande interessanti su split, numeri pseudocasuali e la natura dei numeri casuali in relazione alla purezza. È difficile per me immaginare un caso in cui la tua istanza avrebbe effetti negativi, ma la complessità dei sistemi software non ha mai smesso di sorprendermi. E a causa di ciò, non vorrei violare un'aspettativa su bindM2, anche se è con numeri casuali.

Answer 2

C'è un problema inerente allo bindM2 di MonadParallel. La sua documentazione dice:

Eseguire due calcoli monadici in parallelo; quando sono entrambi finiti, passa i risultati alla funzione. Oltre alla possibilità di ordinazione di effetti collaterali, questa funzione è equivalente a \f ma mb-> do {a <- ma; b <- mb; f a b}

Il problema è che nei calcoli monadici (a differenza functors applicative) valori possono dipendere da effetti, e sulla loro ordinamento troppo. Quindi questo requisito non ha molto senso. Si consideri

do 
    a <- getCurrentTime -- from Date.Time 
    b <- getCurrentTime 
    return (a <= b) 

Questa restituisce sempre True, ma se si riordinare gli effetti, si comincerà il ritorno False. Ovviamente parallelizzando i due calcoli, otterresti un risultato molto non deterministico.

Quindi è difficile interpretare l'intenzione di bindM2.Direi che potremmo dividere le istanze di MonadParallel in due categorie:

1. Coloro che sono veramente deterministico e per il quale bindM2 è sempre uguale a \f ma mb-> do {a <- ma; b <- mb; f a b}. Cioè, l'ordine degli effetti non cambia. Tali implementazioni vengono solitamente definite utilizzando par, che non modifica la semantica del programma, esegue solo alcune parti in parallelo.
2. Quelli che dipendono dall'ordinamento degli effetti, quindi bindM2 può essere arbitrariamente diverso da \f ma mb-> do {a <- ma; b <- mb; f a b}. Sembra che attualmente l'unica istanza di questo tipo sia IO, che utilizza forkIO per generare un nuovo thread per uno dei calcoli.

Quindi, se si accetta il tuo bindM2 come un'istanza valida o meno dipende da come si interpreta la documentazione. Se consideri (2) non valido, anche l'implementazione non è valida (e devi respingere anche IO). Se interpreti (2.) come valido, non devi preoccuparti.