La mappa di Haskell non è pigra?

AGGIORNAMENTO: Va bene questa domanda diventa potenzialmente molto semplice.

q <- mapM return [1..] 

Perché questo non torna mai?


MapM non si occupa pigramente di liste infinite?

Il codice qui sotto si blocca. Tuttavia, se sostituisco la riga A con la linea B, non si blocca più. In alternativa, se precedo la riga A da un “splitRandom $”, anche questo non si blocca.

Q1 è: mapM non è pigro? Altrimenti, perché sostituire la riga A con la riga B “aggiusta questo codice”?

    Q2 è: Perché la riga A precedente con splitRandom “risolve” il problema?

     import Control.Monad.Random import Control.Applicative f :: (RandomGen g) => Rand g (Double, [Double]) f = do b <- splitRandom $ sequence $ repeat $ getRandom c <- mapM return b -- A -- let c = map id b -- B a  Rand ga -> Rand ga splitRandom code = evalRand code  getSplit t0 = do (a, b) <- evalRand f  newStdGen print a print (take 3 b) 

    Il codice genera una lista infinita di numeri casuali pigramente. Quindi genera un singolo numero casuale. Usando splitRandom, posso valutare quest’ultimo numero casuale prima della lista infinita. Questo può essere dimostrato se restituisco b invece di c nella funzione.

    Tuttavia, se applico la mapM all’elenco, il programma si blocca ora. Per evitare che questo si blocchi, devo applicare nuovamente SplitRandom prima della mappaM. Avevo l’impressione che mapM potesse pigramente

    Beh, c’è un pigro, e poi c’è il pigro . mapM è davvero pigro in quanto non fa più lavoro di quello che deve fare. Tuttavia, guarda la firma del tipo:

     mapM :: (Monad m) => (a -> mb) -> [a] -> m [b] 

    Pensa a cosa significa: gli dai una funzione a -> mb e un mucchio di s. Una map regolare può trasformarli in un gruppo di mb s, ma non in m [b] . L’unico modo per combinare i b in un singolo [b] senza che la monade si intrometta è usare >>= per sequenziare i mb s insieme per build l’elenco .

    In effetti, mapM è esattamente equivalente alla sequence . map sequence . map

    In generale, per qualsiasi espressione monadica, se il valore viene utilizzato, l’intera catena di >>= s che conduce all’espressione deve essere forzata, quindi non è ansible terminare la sequence in un elenco infinito.

    Se vuoi lavorare con una sequenza monadica illimitata, avrai bisogno di un controllo esplicito del stream – ad esempio, una condizione di terminazione del ciclo inserita nella catena dei bind in qualche modo, che le semplici funzioni ricorsive come mapM e la sequence non forniscono – o una sequenza passo-passo, qualcosa del genere:

     data Stream ma = Nil | Stream a (m (Stream ma)) 

    … in modo da forzare solo il numero di layer Monad necessario.

    Modifica :: Riguardo a splitRandom , quello che sta succedendo è che stai passando a un calcolo di Rand , valutando quello con il seme splitRandom ottiene, quindi return il risultato. Senza lo splitRandom , il seme utilizzato dal singolo getRandom deve provenire dal risultato finale del sequenziamento della lista infinita, quindi si blocca. Con lo splitRandom aggiuntivo, il seed utilizzato deve solo eseguire il thread delle due chiamate splitRandom , quindi funziona. L’elenco finale di numeri casuali funziona perché hai lasciato la monade Rand in quel punto e nulla dipende dal suo stato finale.

    Ecco un tentativo di dimostrare che mapM return [1..] non termina. Supponiamo per ora che siamo nella monade Identity (l’argomento si applicherà anche a qualsiasi altra monade):

     mapM return [1..] -- initial expression sequence (map return [1 ..]) -- unfold mapM let kmm' = m >>= \x -> m' >>= \xs -> return (x : xs) in foldr k (return []) (map return [1..]) -- unfold sequence 

    Fin qui tutto bene…

     -- unfold foldr let kmm' = m >>= \x -> m' >>= \xs -> return (x : xs) go [] = return [] go (y:ys) = ky (go ys) in go (map return [1..]) -- unfold map so we have enough of a list to pattern-match go: go (return 1 : map return [2..]) -- unfold go: k (return 1) (go (map return [2..]) -- unfold k: (return 1) >>= \x -> go (map return [2..]) >>= \xs -> return (x:xs) 

    Ricorda che return a = Identity a nella monade Id quadro, e (Identity a) >>= f = fa nella monade Identity framework. continuando:

     -- unfold >>= : (\x -> go (map return [2..]) >>= \xs -> return (x:xs)) 1 -- apply 1 to \x -> ... : go (map return [2..]) >>= \xs -> return (1:xs) -- unfold >>= : (\xs -> return (1:xs)) (go (map return [2..])) 

    Nota che a questo punto ci piacerebbe applicare a \xs , ma non possiamo ancora! Dobbiamo invece continuare a svolgersi fino a quando non abbiamo un valore da applicare:

     -- unfold map for go: (\xs -> return (1:xs)) (go (return 2 : map return [3..])) -- unfold go: (\xs -> return (1:xs)) (k (return 2) (go (map return [3..]))) -- unfold k: (\xs -> return (1:xs)) ((return 2) >>= \x2 -> (go (map return [3..])) >>= \xs2 -> return (x2:xs2)) -- unfold >>= : (\xs -> return (1:xs)) ((\x2 -> (go (map return [3...])) >>= \xs2 -> return (x2:xs2)) 2) 

    A questo punto, non possiamo ancora applicare a \xs , ma possiamo applicare a \x2 . continuando:

     -- apply 2 to \x2 : (\xs -> return (1:xs)) ((go (map return [3...])) >>= \xs2 -> return (2:xs2)) -- unfold >>= : (\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go (map return [3..])) 

    Ora siamo arrivati ​​a un punto in cui né \xs \xs2 possono essere ridotti ancora! La nostra unica scelta è:

     -- unfold map for go, and so on... (\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go ((return 3) : (map return [4..]))) 

    Quindi puoi vedere che, a causa di foldr , stiamo costruendo una serie di funzioni da applicare, a partire dalla fine della lista e lavorando al nostro ritorno. Perché ad ogni passo la lista di input è infinita, questo dispiegamento non finirà mai e non otterremo mai una risposta.

    Questo ha senso se si guarda a questo esempio (preso in prestito da un altro thread StackOverflow, non riesco a trovare quale al momento). Nel seguente elenco di monadi:

     mebs = [Just 3, Just 4, Nothing] 

    ci aspetteremmo che la sequence catturasse il Nothing e restituisse un fallimento per tutto il resto:

     sequence mebs = Nothing 

    Tuttavia, per questo elenco:

     mebs2 = [Just 3, Just 4] 

    ci aspetteremmo che la sequenza ci desse:

     sequence mebs = Just [3, 4] 

    In altre parole, la sequence deve vedere l’intera lista di calcoli monadici, unirli insieme ed eseguirli tutti per ottenere la risposta giusta. Non c’è modo che la sequence possa dare una risposta senza vedere l’intera lista.

    Nota: la versione precedente di questa risposta ha affermato che foldr calcola a partire dal retro della lista e non funzionerebbe affatto su liste infinite, ma non è corretto! Se l’operatore che passi a foldr è pigro sul suo secondo argomento e produce output con un costruttore di dati lazy come una lista, foldr lavorerà felicemente con una lista infinita. Vedi foldr (\x xs -> (replicate xx) ++ xs) [] [1...] per un esempio. Ma questo non è il caso con il nostro operatore k .

    Va bene questa domanda diventa potenzialmente molto semplice.

    q <- MapM return [1 ..]

    Perché questo non torna mai?

    Non è necessariamente vero. Dipende dalla monade in cui ti trovi.

    Ad esempio, con la monade id quadro, è ansible utilizzare il risultato pigramente e termina bene:

     newtype Identity a = Identity a instance Monad Identity where Identity x >>= k = kx return = Identity -- "foo" is the infinite list of all the positive integers foo :: [Integer] Identity foo = do q <- mapM return [1..] return q main :: IO () main = print $ take 20 foo -- [1 .. 20] 

    Questa domanda sta mostrando molto bene la differenza tra la Monade IO e le altre Monadi. In background mapM crea un’espressione con un’operazione di bind (>> =) tra tutti gli elementi dell’elenco per trasformare l’elenco di espressioni monadiche in un’espressione monadica di una lista. Ora, ciò che è diverso nella monade IO è che il modello di esecuzione di Haskell sta eseguendo espressioni durante il binding nella IO Monade. Questo è esattamente ciò che finalmente costringe (in un mondo puramente pigro) a qualcosa da eseguire.

    Quindi IO Monad è speciale in un certo senso, sta usando il paradigma della sequenza di bind per applicare effettivamente l’esecuzione di ogni passaggio e questo è ciò che il nostro programma fa per eseguire qualsiasi cosa alla fine. Altre Monadi sono diverse. Hanno altri significati dell’operatore legatore, a seconda della Monade. IO è in realtà il solo Monad che esegue le cose nel binding e questo è il motivo per cui i tipi di IO sono “azioni”.

    L’esempio seguente mostra che altri Monad non impongono l’esecuzione, ad esempio la monade Maybe. Infine questo porta al risultato che una mappaM nell’IO Monad restituisce un’espressione che, una volta eseguita, esegue ogni singolo elemento prima di restituire il valore finale.

    Ci sono bei documenti su questo, inizia da qui o cerca semantica denotazionale e Monade: Affrontare la squadra scomoda: http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/mark.pdf

    Esempio con Forse Monad:

    modulo Principale dove

    fstMaybe :: [Int] -> Forse [Int] fstMaybe = mapM (\ x -> se x == 3 then Nothing else Solo x)

    main = do let r = fstMaybe [1 ..] return r

    Parliamo di questo in un contesto più generico.

    Come hanno detto le altre risposte, la mapM è solo una combinazione di sequence e map . Quindi il problema è perché la sequence è severa in certe Monad . Tuttavia, questo non è limitato alle Monads ma anche Applicative poiché abbiamo la sequenceA che condivide la stessa implementazione di sequence nella maggior parte dei casi.

    Ora guarda la firma del tipo (specializzato per gli elenchi) della sequenceA :

     sequenceA :: Applicative f => [fa] -> f [a] 

    come lo faresti? Ti è stata data una lista, quindi ti piacerebbe usare foldr in questo elenco.

     sequenceA = foldr fb where ... --f :: fa -> f [a] -> f [a] --b :: f [a] 

    Dato che f è un Applicative , sai cosa può essere b coule – pure [] . Ma che cos’è? Ovviamente è una versione sollevata di (:) :

     (:) :: a -> [a] -> [a] 

    Così ora sappiamo come funziona sequenceA :

     sequenceA = foldr fb where fab = (:) <$> a <*> b b = pure [] 

    o

     sequenceA = foldr ((<*>) . fmap (:)) (pure []) 

    Supponi di aver ricevuto una lista pigra (x:_|_) . La precedente definizione di sequenceA

     sequenceA (x:_|_) === (:) <$> x <*> foldr ((<*>) . fmap (:)) (pure []) _|_ === (:) <$> x <*> _|_ 

    Così ora vediamo che il problema è stato ridotto a considerare il tempo f <*> _|_ è _|_ oppure no. Ovviamente se f è severo questo è _|_ , ma se f non è severo, per consentire un arresto della valutazione, è necessario che <*> stesso non sia severo.

    Quindi i criteri per un funtore applicativo per avere una sequenceA che si ferma saranno l’operatore <*> non severi. Un semplice test sarebbe

     const a <$> _|_ === _|_ ====> strict sequenceA -- remember f <$> a === pure f <*> a 

    Se stiamo parlando di Moand s, il criterio è

     _|_ >> const a === _|_ ===> strict sequence