-- --------------------------------------------------------------------------------- (c) The University of Glasgow 2012---- Monadic streams---- -----------------------------------------------------------------------------moduleStream(Stream (..),yield ,liftIO ,collect ,fromList ,Stream.map ,Stream.mapM ,Stream.mapAccumL )whereimportGhcPreludeimportControl.Monad-- |-- @Stream m a b@ is a computation in some Monad @m@ that delivers a sequence-- of elements of type @a@ followed by a result of type @b@.---- More concretely, a value of type @Stream m a b@ can be run using @runStream@-- in the Monad @m@, and it delivers either---- * the final result: @Left b@, or-- * @Right (a,str)@, where @a@ is the next element in the stream, and @str@-- is a computation to get the rest of the stream.---- Stream is itself a Monad, and provides an operation 'yield' that-- produces a new element of the stream. This makes it convenient to turn-- existing monadic computations into streams.---- The idea is that Stream is useful for making a monadic computation-- that produces values from time to time. This can be used for-- knitting together two complex monadic operations, so that the-- producer does not have to produce all its values before the-- consumer starts consuming them. We make the producer into a-- Stream, and the consumer pulls on the stream each time it wants a-- new value.--newtypeStream m a b =Stream {runStream ::m (Eitherb (a ,Stream m a b ))}instanceMonadf =>Functor(Stream f a )wherefmap =liftMinstanceMonadm =>Applicative(Stream m a )wherepure a =Stream (return(Lefta ))(<*> )=apinstanceMonadm =>Monad(Stream m a )whereStream m >>= k =Stream $dor <-m caser ofLeftb ->runStream(k b )Right(a ,str )->return(Right(a ,str >>=k ))yield::Monadm =>a ->Stream m a ()yield a =Stream (return(Right(a ,return())))liftIO::IOa ->Stream IOb a liftIO io =Stream $io >>=return.Left-- | Turn a Stream into an ordinary list, by demanding all the elements.collect::Monadm =>Stream m a ()->m [a ]collect str =go str []wherego str acc =dor <-runStreamstr caser ofLeft()->return(reverseacc )Right(a ,str' )->go str' (a :acc )-- | Turn a list into a 'Stream', by yielding each element in turn.fromList::Monadm =>[a ]->Stream m a ()fromList =mapM_yield -- | Apply a function to each element of a 'Stream', lazilymap::Monadm =>(a ->b )->Stream m a x ->Stream m b x map f str =Stream $dor <-runStreamstr caser ofLeftx ->return(Leftx )Right(a ,str' )->return(Right(f a ,Stream.map f str' ))-- | Apply a monadic operation to each element of a 'Stream', lazilymapM::Monadm =>(a ->m b )->Stream m a x ->Stream m b x mapM f str =Stream $dor <-runStreamstr caser ofLeftx ->return(Leftx )Right(a ,str' )->dob <-f a return(Right(b ,Stream.mapM f str' ))-- | analog of the list-based 'mapAccumL' on Streams. This is a simple-- way to map over a Stream while carrying some state around.mapAccumL::Monadm =>(c ->a ->m (c ,b ))->c ->Stream m a ()->Stream m b c mapAccumL f c str =Stream $dor <-runStreamstr caser ofLeft()->return(Leftc )Right(a ,str' )->do(c' ,b )<-f c a return(Right(b ,mapAccumL f c' str' ))