Comment prendre des éléments dans une liste enveloppée dans une monade

Question

J'ai un peu de puzzle Je me demandais si vous pouviez m'aider à clarifier.

Définissons une fonction qui retourne une liste:

let f = replicate 3 

Ce que nous voulons faire est la carte de cette fonction à une liste infinie, concaténer les résultats, et ne prendre que les choses qui correspondent à un prédicat.

takeWhile (< 3) $ concatMap f [1..] 

Très bien! Cela renvoie [1,1,1,2,2,2], ce qui est ce que je veux.

Maintenant, je veux faire quelque chose de similaire, mais la fonction f enveloppe maintenant ses résultats dans une Monade. Dans mon usecase, c'est la monade IO, mais cela fonctionne pour discuter de mon problème:

let f' x = Just $ replicate 3 x 

Recenser et concat, je peux utiliser:

fmap concat $ mapM f' [1..5] 

qui retourne: Just [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5]

Si Je veux utiliser takeWhile, cela fonctionne encore:

fmap (takeWhile (< 3) . concat) $ mapM f' [1..5] 

qui retourne: Juste [1,1,1,2,2,2]. Génial!

Mais, si je fais la liste sur laquelle j'Epinglez une liste infinie cela ne fait pas ce que je pensais:

fmap (takeWhile (< 3) . concat) $ mapM f' [1..] 

On dirait que le takeWhile est jamais le cas. D'une manière ou d'une autre, je n'obtiens pas le calcul paresseux auquel je m'attendais. Je suis un peu perdu.

Answer 1

Le problème n'est pas que fmap + takeWhile ne fonctionne pas avec les listes infinies enveloppées dans une monade. Le problème est que mapM ne peut pas produire une liste infinie (du moins pas dans la monade Maybe).

Pensez-y: Si f' retours Nothing pour tout élément de la liste, mapM doit retourner Nothing. Toutefois mapM ne peut pas savoir si cela se produira jusqu'à ce qu'il ait appelé f' sur tous les éléments de la liste. Il doit donc parcourir toute la liste avant de savoir si le résultat est Nothing ou Just. Évidemment, c'est un problème avec les listes infinies.

Answer 2

Vous ne pouvez pas mapper une liste infinie de Maybes. mapM est une carte suivie d'une séquence. Voici la définition de la séquence:

 
sequence ms = foldr k (return []) ms 
    where 
    k m m' = do { x <- m; xs <- m'; return (x:xs) } 

De cela nous voyons que la séquence évalue chaque valeur monadique dans la liste. Comme c'est une liste infinie, cette opération ne s'arrêtera pas.

EDIT:

Luqui et Carl font un bon point que cela ne généralise pas à une monade.Pour voir pourquoi il ne fonctionne pas Peut-être que nous devons examiner la mise en œuvre (>> =):

(>>=) m k = case m of 
    Just x -> k x 
    Nothing -> Nothing 

Le point important est que nous faisons une affaire sur m. Cela rend le m strict parce que nous devons l'évaluer pour comprendre comment continuer l'exécution. Notez que nous n'abordons pas X ici, donc il reste paresseux.

Answer 3

Cela devrait faire l'affaire: de

takeWhileM :: (Monad m) => (a -> Bool) -> [m a] -> m [a] 
takeWhileM p [] = return [] 
takeWhileM p (m:ms) = do 
    x <- m 
    if p x 
     then liftM (x:) (takeWhileM p ms) 
     else return [] 

Voir sepp2k réponse pour une explication des raisons pour lesquelles vous perdez la paresse. La monade d'identité ou la monade de liste nonempaint, par exemple, n'aurait pas ce problème.