utils: detabify/dewhitespace GraphPpr
[ghc.git] / compiler / utils / Stream.hs
1 -- -----------------------------------------------------------------------------
2 --
3 -- (c) The University of Glasgow 2012
4 --
5 -- Monadic streams
6 --
7 -- -----------------------------------------------------------------------------
8
9 module Stream (
10 Stream(..), yield, liftIO,
11 collect, fromList,
12 Stream.map, Stream.mapM, Stream.mapAccumL
13 ) where
14 import Control.Monad
15 import Control.Applicative
16
17 -- |
18 -- @Stream m a b@ is a computation in some Monad @m@ that delivers a sequence
19 -- of elements of type @a@ followed by a result of type @b@.
20 --
21 -- More concretely, a value of type @Stream m a b@ can be run using @runStream@
22 -- in the Monad @m@, and it delivers either
23 --
24 -- * the final result: @Left b@, or
25 -- * @Right (a,str)@, where @a@ is the next element in the stream, and @str@
26 -- is a computation to get the rest of the stream.
27 --
28 -- Stream is itself a Monad, and provides an operation 'yield' that
29 -- produces a new element of the stream. This makes it convenient to turn
30 -- existing monadic computations into streams.
31 --
32 -- The idea is that Stream is useful for making a monadic computation
33 -- that produces values from time to time. This can be used for
34 -- knitting together two complex monadic operations, so that the
35 -- producer does not have to produce all its values before the
36 -- consumer starts consuming them. We make the producer into a
37 -- Stream, and the consumer pulls on the stream each time it wants a
38 -- new value.
39 --
40 newtype Stream m a b = Stream { runStream :: m (Either b (a, Stream m a b)) }
41
42 instance Monad f => Functor (Stream f a) where
43 fmap = liftM
44
45 instance Monad m => Applicative (Stream m a) where
46 pure = return
47 (<*>) = ap
48
49 instance Monad m => Monad (Stream m a) where
50 return a = Stream (return (Left a))
51
52 Stream m >>= k = Stream $ do
53 r <- m
54 case r of
55 Left b -> runStream (k b)
56 Right (a,str) -> return (Right (a, str >>= k))
57
58 yield :: Monad m => a -> Stream m a ()
59 yield a = Stream (return (Right (a, return ())))
60
61 liftIO :: IO a -> Stream IO b a
62 liftIO io = Stream $ io >>= return . Left
63
64 -- | Turn a Stream into an ordinary list, by demanding all the elements.
65 collect :: Monad m => Stream m a () -> m [a]
66 collect str = go str []
67 where
68 go str acc = do
69 r <- runStream str
70 case r of
71 Left () -> return (reverse acc)
72 Right (a, str') -> go str' (a:acc)
73
74 -- | Turn a list into a 'Stream', by yielding each element in turn.
75 fromList :: Monad m => [a] -> Stream m a ()
76 fromList = mapM_ yield
77
78 -- | Apply a function to each element of a 'Stream', lazily
79 map :: Monad m => (a -> b) -> Stream m a x -> Stream m b x
80 map f str = Stream $ do
81 r <- runStream str
82 case r of
83 Left x -> return (Left x)
84 Right (a, str') -> return (Right (f a, Stream.map f str'))
85
86 -- | Apply a monadic operation to each element of a 'Stream', lazily
87 mapM :: Monad m => (a -> m b) -> Stream m a x -> Stream m b x
88 mapM f str = Stream $ do
89 r <- runStream str
90 case r of
91 Left x -> return (Left x)
92 Right (a, str') -> do
93 b <- f a
94 return (Right (b, Stream.mapM f str'))
95
96 -- | analog of the list-based 'mapAccumL' on Streams. This is a simple
97 -- way to map over a Stream while carrying some state around.
98 mapAccumL :: Monad m => (c -> a -> m (c,b)) -> c -> Stream m a ()
99 -> Stream m b c
100 mapAccumL f c str = Stream $ do
101 r <- runStream str
102 case r of
103 Left () -> return (Left c)
104 Right (a, str') -> do
105 (c',b) <- f c a
106 return (Right (b, mapAccumL f c' str'))