1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
-- -----------------------------------------------------------------------------
--
-- (c) The University of Glasgow 2012
--
-- Monadic streams
--
-- -----------------------------------------------------------------------------
module Stream (
Stream(..), yield, liftIO,
collect, fromList,
Stream.map, Stream.mapM, Stream.mapAccumL
) where
import Control.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.
--
newtype Stream m a b = Stream { runStream :: m (Either b (a, Stream m a b)) }
instance Monad f => Functor (Stream f a) where
fmap = liftM
instance Monad m => Applicative (Stream m a) where
pure a = Stream (return (Left a))
(<*>) = ap
instance Monad m => Monad (Stream m a) where
Stream m >>= k = Stream $ do
r <- m
case r of
Left b -> runStream (k b)
Right (a,str) -> return (Right (a, str >>= k))
yield :: Monad m => a -> Stream m a ()
yield a = Stream (return (Right (a, return ())))
liftIO :: IO a -> Stream IO b a
liftIO io = Stream $ io >>= return . Left
-- | Turn a Stream into an ordinary list, by demanding all the elements.
collect :: Monad m => Stream m a () -> m [a]
collect str = go str []
where
go str acc = do
r <- runStream str
case r of
Left () -> return (reverse acc)
Right (a, str') -> go str' (a:acc)
-- | Turn a list into a 'Stream', by yielding each element in turn.
fromList :: Monad m => [a] -> Stream m a ()
fromList = mapM_ yield
-- | Apply a function to each element of a 'Stream', lazily
map :: Monad m => (a -> b) -> Stream m a x -> Stream m b x
map f str = Stream $ do
r <- runStream str
case r of
Left x -> return (Left x)
Right (a, str') -> return (Right (f a, Stream.map f str'))
-- | Apply a monadic operation to each element of a 'Stream', lazily
mapM :: Monad m => (a -> m b) -> Stream m a x -> Stream m b x
mapM f str = Stream $ do
r <- runStream str
case r of
Left x -> return (Left x)
Right (a, str') -> do
b <- 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 :: Monad m => (c -> a -> m (c,b)) -> c -> Stream m a ()
-> Stream m b c
mapAccumL f c str = Stream $ do
r <- runStream str
case r of
Left () -> return (Left c)
Right (a, str') -> do
(c',b) <- f c a
return (Right (b, mapAccumL f c' str'))
|
