Utilisation de listes infinies avec des monades strictes

Question

J'ai une fonction f :: [a] -> b qui fonctionne sur des listes infinies (par exemple take 5, takeWhile (< 100) . scanl (+) 0 et ainsi de suite). Je veux alimenter cette fonction avec des valeurs générées par des actions monadiques strictes (par exemple randomIO).

De this question, je l'ai appris que le repeat et sequence approche astuce ne fonctionne pas pour monades strictes, comme l'exemple ci-dessous montrent: au lieu

import Control.Monad.Identity 

take 5 <$> sequence (repeat $ return 1) :: Identity [Int] 
-- returns `Identity [1,1,1,1,1]` 
-- works because Identity is non-strict 

take 5 <$> sequence (repeat $ return 1) :: IO [Int] 
-- returns `*** Exception: stack overflow` 
-- does not work because IO is strict 

Alors, je pensais à l'aide de la fonction « à l'intérieur "Le contexte monadique. Je me suis inspiré par ce circular programming example et essayé:

let loop = do 
     x <- return 1 
     (_, xs) <- loop 
     return (take 5 xs, x:xs) 
in fst loop :: Identity [Int] 
-- Overflows the stack 

et

import Control.Monad.Fix 

fst <$> mfix (\(_, xs) -> do 
    x <- return 1 
    return (take 5 xs, x:xs)) :: Identity [Int] 
-- Overflows the stack 

et même

{-# LANGUAGE RecursiveDo #-} 
import System.Random 

loop' = mdo 
    (xs', xs) <- loop xs 
    return xs' 
where loop xs = do 
     x <- randomIO 
     return (take 5 xs, x:xs) 

print $ loop' 
-- Returns a list of 5 identical values 

Mais aucune de ces œuvres. J'ai essayé aussi une approche Conduit qui ne fonctionne pas non plus, même dans le cas Identity:

import Conduit 

runConduitPure $ yieldMany [1..] .| sinkList >>= return . take 5 

Par conséquent, je voudrais savoir:

1. Pourquoi aucune des approches « circulaire » au-dessus de travail?

2. S'il existe une solution à cela qui n'implique pas unsafeInterleaveIO. (peut-être iteratee s, Arrow s?)

Answer 1

J'utilise randomIO ici juste pour la simplicité des exemples. Dans la pratique, je voudrais traiter les messages reçus via les prises

Ce est impossible sans unsafeInterleaveIO. Le problème à la fin de la journée est que les actions IO doivent être séquencées. Alors que l'ordre d'évaluation pour les valeurs référentiellement transparentes n'a pas d'importance, celui des actions IO peut l'être. Si vous voulez une liste infinie paresseuse de tous les messages reçus sur une socket, vous devez informer Haskell a priori où cela correspond dans la séquence des actions IO (sauf si vous utilisez unsafeInterleaveIO).

L'abstraction vous cherchez Arrow est appelé ArrowLoop, mais il a aussi un problème avec la loi de serrage droit pour monades strictes.

À première vue, il peut ressembler à (qui se manifeste par l'intermédiaire mdo ou mfix) est une solution aussi, mais creuser un peu plus profond shows that fixIO has problems, tout comme loop de ArrowLoop.

Cependant, parfois la restriction que les actions IO doivent être exécutées l'une après l'autre est un peu excessive et c'est ce que unsafeInterleaveIO est pour.Citant le docs

unsafeInterleaveIO permet le calcul IO à reporter paresseusement. Une fois transmise une valeur de type IO a, le IO ne sera exécuté que lorsque la valeur de a est demandée.

---

Maintenant, même si vous avez dit explicitement que vous ne l'avez pas voulez une solution unsafeInterleaveIO, comme je l'espère avoir réussi à vous convaincre qu'il est le chemin à parcourir, la voici:

interweavingRepeatM :: IO a -> IO [a] 
interweavingRepeatM action = unsafeInterleaveIO ((:) <$> action <*> interweavingRepeatM action) 

Et voici travaille pour les nombres aléatoires:

ghci> import System.Random 
ghci> sourceOfRandomness <- interweavingRepeatM randomIO :: IO [Integer] 
ghci> take 10 sourceOfRandomness 
[-2002742716261662204,7803971943047671004,-8395318556488893887,-7372674153585794391,5906750628663631621,6428130029392850107,6453903217221537923,-8966011929671667536,6419977320189968675,-1842456468700051776] 

Answer 2

Alec's answer couvre y notre question générale. Ce qui suit est spécifiquement sur conduit et les bibliothèques de diffusion similaires.

J'ai aussi essayé une approche Conduit qui ne fonctionne pas non plus, même dans le cas Identity:

import Conduit 

runConduitPure $ yieldMany [1..] .| sinkList >>= return . take 5 

Alors que les bibliothèques en streaming sont couramment utilisées pour éviter le genre de difficulté que vous mentionnez (cf. la remarques d'ouverture de Pipes.Tutorial), ils supposent que vous utiliserez leurs types de flux au lieu de listes. Prenons, par exemple, comment sinkList est décrit par la documentation Conduit:

Consommez toutes les valeurs du flux et de retour sous forme de liste. Notez que cela va tirer toutes les valeurs en mémoire.

Cela signifie que l'aide sinkMany immédiatement après yieldMany vous ramène à la case départ: amener toutes les valeurs en mémoire est précisément ce qui fait la combinaison de sequence, IO et listes infinies inutilisable. Ce que vous devez faire à la place est d'utiliser l'infrastructure de la bibliothèque de streaming pour construire les étapes de votre pipeline. Voici quelques exemples simples en utilisant la plupart du temps des choses toutes faites à partir conduit et conduit-combinators:

GHCi> import Conduit 
GHCi> runConduitPure $ yieldMany [1..] .| takeC 5 .| sinkList 
[1,2,3,4,5] 
GHCi> runConduit $ yieldMany [1..] .| takeC 5 .| printC -- try it without takeC 
1 
2 
3 
4 
5 
GHCi> runConduit $ yieldMany [1..] .| takeC 5 .| scanlC (+) 0 .| printC 
0 
1 
3 
6 
10 
15 
GHCi> :{ 
GHCi| runConduit $ yieldMany [1..] .| takeC 5 
GHCi|  .| awaitForever (\x -> liftIO (print (2*x)) >> yield x) 
GHCi|  .| printC 
GHCi| :} 
2 
1 
4 
2 
6 
3 
8 
4 
10 
5 
GHCi> runConduit $ (sourceRandom :: Producer IO Int) .| takeC 5 .| printC 
1652736016140975126 
5518223062916052424 
-1236337270682979278 
8079753510915129274 
-609160753105692151 

(Merci Michael pour me faire remarqué sourceRandom - au début, j'avais roulé ma propre avec repeatMC randomIO.