Fix haddocks
[darcs-mirrors/vector.git] / Data / Vector / Fusion / Stream / Monadic.hs
1 {-# LANGUAGE ExistentialQuantification #-}
2
3 -- |
4 -- Module : Data.Vector.Fusion.Stream.Monadic
5 -- Copyright : (c) Roman Leshchinskiy 2008
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- Monadic streams
13 --
14
15 #include "phases.h"
16
17 module Data.Vector.Fusion.Stream.Monadic (
18 Stream(..),
19
20 -- * Size hints
21 size, sized,
22
23 -- * Length
24 length, null,
25
26 -- * Construction
27 empty, singleton, cons, snoc, replicate, (++),
28
29 -- * Accessing elements
30 head, last, (!!),
31
32 -- * Substreams
33 extract, init, tail, take, drop,
34
35 -- * Mapping and zipping
36 map, mapM, mapM_, zipWith, zipWithM,
37
38 -- * Filtering
39 filter, filterM, takeWhile, takeWhileM, dropWhile, dropWhileM,
40
41 -- * Searching
42 elem, notElem, find, findM, findIndex, findIndexM,
43
44 -- * Folding
45 foldl, foldlM, foldM, foldl1, foldl1M,
46 foldl', foldlM', foldl1', foldl1M',
47 foldr, foldrM, foldr1, foldr1M,
48
49 -- * Unfolding
50 unfold, unfoldM,
51
52 -- * Scans
53 prescanl, prescanlM, prescanl', prescanlM',
54
55 toList, fromList
56 ) where
57
58 import Data.Vector.Fusion.Stream.Step
59 import Data.Vector.Fusion.Stream.Size
60
61 import Control.Monad ( liftM )
62 import Prelude hiding ( length, null,
63 replicate, (++),
64 head, last, (!!),
65 init, tail, take, drop,
66 map, mapM, mapM_, zipWith,
67 filter, takeWhile, dropWhile,
68 elem, notElem,
69 foldl, foldl1, foldr, foldr1 )
70 import qualified Prelude
71
72 data Stream m a = forall s. Stream (s -> m (Step s a)) s Size
73
74 -- | 'Size' hint of a 'Stream'
75 size :: Stream m a -> Size
76 {-# INLINE size #-}
77 size (Stream _ _ sz) = sz
78
79 -- | Attach a 'Size' hint to a 'Stream'
80 sized :: Stream m a -> Size -> Stream m a
81 {-# INLINE_STREAM sized #-}
82 sized (Stream step s _) sz = Stream step s sz
83
84 -- Length
85 -- ------
86
87 -- | Length of a 'Stream'
88 length :: Monad m => Stream m a -> m Int
89 {-# INLINE_STREAM length #-}
90 length s = foldl' (\n _ -> n+1) 0 s
91
92 -- | Check if a 'Stream' is empty
93 null :: Monad m => Stream m a -> m Bool
94 {-# INLINE_STREAM null #-}
95 null s = foldr (\_ _ -> False) True s
96
97
98 -- Construction
99 -- ------------
100
101 -- | Empty 'Stream'
102 empty :: Monad m => Stream m a
103 {-# INLINE_STREAM empty #-}
104 empty = Stream (const (return Done)) () (Exact 0)
105
106 -- | Singleton 'Stream'
107 singleton :: Monad m => a -> Stream m a
108 {-# INLINE_STREAM singleton #-}
109 singleton x = Stream (return . step) True (Exact 1)
110 where
111 {-# INLINE step #-}
112 step True = Yield x False
113 step False = Done
114
115 -- | Replicate a value to a given length
116 replicate :: Monad m => Int -> a -> Stream m a
117 {-# INLINE_STREAM replicate #-}
118 replicate n x = Stream (return . step) n (Exact (max n 0))
119 where
120 {-# INLINE step #-}
121 step i | i > 0 = Yield x (i-1)
122 | otherwise = Done
123
124 -- | Prepend an element
125 cons :: Monad m => a -> Stream m a -> Stream m a
126 {-# INLINE cons #-}
127 cons x s = singleton x ++ s
128
129 -- | Append an element
130 snoc :: Monad m => Stream m a -> a -> Stream m a
131 {-# INLINE snoc #-}
132 snoc s x = s ++ singleton x
133
134 infixr 5 ++
135 -- | Concatenate two 'Stream's
136 (++) :: Monad m => Stream m a -> Stream m a -> Stream m a
137 {-# INLINE_STREAM (++) #-}
138 Stream stepa sa na ++ Stream stepb sb nb = Stream step (Left sa) (na + nb)
139 where
140 step (Left sa) = do
141 r <- stepa sa
142 case r of
143 Yield x sa' -> return $ Yield x (Left sa')
144 Skip sa' -> return $ Skip (Left sa')
145 Done -> return $ Skip (Right sb)
146 step (Right sb) = do
147 r <- stepb sb
148 case r of
149 Yield x sb' -> return $ Yield x (Right sb')
150 Skip sb' -> return $ Skip (Right sb')
151 Done -> return $ Done
152
153 -- Accessing elements
154 -- ------------------
155
156 -- | First element of the 'Stream' or error if empty
157 head :: Monad m => Stream m a -> m a
158 {-# INLINE_STREAM head #-}
159 head (Stream step s _) = head_loop s
160 where
161 head_loop s = do
162 r <- step s
163 case r of
164 Yield x _ -> return x
165 Skip s' -> head_loop s'
166 Done -> errorEmptyStream "head"
167
168 -- | Last element of the 'Stream' or error if empty
169 last :: Monad m => Stream m a -> m a
170 {-# INLINE_STREAM last #-}
171 last (Stream step s _) = last_loop0 s
172 where
173 last_loop0 s = do
174 r <- step s
175 case r of
176 Yield x s' -> last_loop1 x s'
177 Skip s' -> last_loop0 s'
178 Done -> errorEmptyStream "last"
179
180 last_loop1 x s = do
181 r <- step s
182 case r of
183 Yield y s' -> last_loop1 y s'
184 Skip s' -> last_loop1 x s'
185 Done -> return x
186
187 -- | Element at the given position
188 (!!) :: Monad m => Stream m a -> Int -> m a
189 {-# INLINE (!!) #-}
190 s !! i = head (drop i s)
191
192 -- Substreams
193 -- ----------
194
195 -- | Extract a substream of the given length starting at the given position.
196 extract :: Monad m => Stream m a -> Int -- ^ starting index
197 -> Int -- ^ length
198 -> Stream m a
199 {-# INLINE extract #-}
200 extract s i n = take n (drop i s)
201
202 -- | All but the last element
203 init :: Monad m => Stream m a -> Stream m a
204 {-# INLINE_STREAM init #-}
205 init (Stream step s sz) = Stream step' (Nothing, s) (sz - 1)
206 where
207 {-# INLINE step' #-}
208 step' (Nothing, s) = liftM (\r ->
209 case r of
210 Yield x s' -> Skip (Just x, s')
211 Skip s' -> Skip (Nothing, s')
212 Done -> Done -- FIXME: should be an error
213 ) (step s)
214
215 step' (Just x, s) = liftM (\r ->
216 case r of
217 Yield y s' -> Yield x (Just y, s')
218 Skip s' -> Skip (Just x, s')
219 Done -> Done
220 ) (step s)
221
222 -- | All but the first element
223 tail :: Monad m => Stream m a -> Stream m a
224 {-# INLINE_STREAM tail #-}
225 tail (Stream step s sz) = Stream step' (Left s) (sz - 1)
226 where
227 {-# INLINE step' #-}
228 step' (Left s) = liftM (\r ->
229 case r of
230 Yield x s' -> Skip (Right s')
231 Skip s' -> Skip (Left s')
232 Done -> Done -- FIXME: should be error?
233 ) (step s)
234
235 step' (Right s) = liftM (\r ->
236 case r of
237 Yield x s' -> Yield x (Right s')
238 Skip s' -> Skip (Right s')
239 Done -> Done
240 ) (step s)
241
242 -- | The first @n@ elements
243 take :: Monad m => Int -> Stream m a -> Stream m a
244 {-# INLINE_STREAM take #-}
245 take n (Stream step s sz) = Stream step' (s, 0) (smaller (Exact n) sz)
246 where
247 {-# INLINE step' #-}
248 step' (s, i) | i < n = liftM (\r ->
249 case r of
250 Yield x s' -> Yield x (s', i+1)
251 Skip s' -> Skip (s', i)
252 Done -> Done
253 ) (step s)
254 step' (s, i) = return Done
255
256 -- | All but the first @n@ elements
257 drop :: Monad m => Int -> Stream m a -> Stream m a
258 {-# INLINE_STREAM drop #-}
259 drop n (Stream step s sz) = Stream step' (s, Just n) (sz - Exact n)
260 where
261 {-# INLINE step' #-}
262 step' (s, Just i) | i > 0 = liftM (\r ->
263 case r of
264 Yield x s' -> Skip (s', Just (i-1))
265 Skip s' -> Skip (s', Just i)
266 Done -> Done
267 ) (step s)
268 | otherwise = return $ Skip (s, Nothing)
269
270 step' (s, Nothing) = liftM (\r ->
271 case r of
272 Yield x s' -> Yield x (s', Nothing)
273 Skip s' -> Skip (s', Nothing)
274 Done -> Done
275 ) (step s)
276
277
278 -- Mapping/zipping
279 -- ---------------
280
281 instance Monad m => Functor (Stream m) where
282 {-# INLINE fmap #-}
283 fmap = map
284
285 -- | Map a function over a 'Stream'
286 map :: Monad m => (a -> b) -> Stream m a -> Stream m b
287 {-# INLINE map #-}
288 map f = mapM (return . f)
289
290 -- | Map a monadic function over a 'Stream'
291 mapM :: Monad m => (a -> m b) -> Stream m a -> Stream m b
292 {-# INLINE_STREAM mapM #-}
293 mapM f (Stream step s n) = Stream step' s n
294 where
295 {-# INLINE step' #-}
296 step' s = do
297 r <- step s
298 case r of
299 Yield x s' -> liftM (`Yield` s') (f x)
300 Skip s' -> return (Skip s')
301 Done -> return Done
302
303 -- | Execute a monadic action for each element of the 'Stream'
304 mapM_ :: Monad m => (a -> m b) -> Stream m a -> m ()
305 {-# INLINE_STREAM mapM_ #-}
306 mapM_ m (Stream step s _) = mapM_go s
307 where
308 mapM_go s = do
309 r <- step s
310 case r of
311 Yield x s' -> do { m x; mapM_go s' }
312 Skip s' -> mapM_go s'
313 Done -> return ()
314
315 -- | Zip two 'Stream's with the given function
316 zipWith :: Monad m => (a -> b -> c) -> Stream m a -> Stream m b -> Stream m c
317 {-# INLINE zipWith #-}
318 zipWith f = zipWithM (\a b -> return (f a b))
319
320 -- | Zip two 'Stream's with the given monadic function
321 zipWithM :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> Stream m c
322 {-# INLINE_STREAM zipWithM #-}
323 zipWithM f (Stream stepa sa na) (Stream stepb sb nb)
324 = Stream step (sa, sb, Nothing) (smaller na nb)
325 where
326 {-# INLINE step #-}
327 step (sa, sb, Nothing) = liftM (\r ->
328 case r of
329 Yield x sa' -> Skip (sa', sb, Just x)
330 Skip sa' -> Skip (sa', sb, Nothing)
331 Done -> Done
332 ) (stepa sa)
333
334 step (sa, sb, Just x) = do
335 r <- stepb sb
336 case r of
337 Yield y sb' ->
338 do
339 z <- f x y
340 return $ Yield z (sa, sb', Nothing)
341 Skip sb' -> return $ Skip (sa, sb', Just x)
342 Done -> return $ Done
343
344 -- Filtering
345 -- ---------
346
347 -- | Drop elements which do not satisfy the predicate
348 filter :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
349 {-# INLINE filter #-}
350 filter f = filterM (return . f)
351
352 -- | Drop elements which do not satisfy the monadic predicate
353 filterM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
354 {-# INLINE_STREAM filterM #-}
355 filterM f (Stream step s n) = Stream step' s (toMax n)
356 where
357 {-# INLINE step' #-}
358 step' s = do
359 r <- step s
360 case r of
361 Yield x s' -> do
362 b <- f x
363 return $ if b then Yield x s'
364 else Skip s'
365 Skip s' -> return $ Skip s'
366 Done -> return $ Done
367
368 -- | Longest prefix of elements that satisfy the predicate
369 takeWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
370 {-# INLINE takeWhile #-}
371 takeWhile f = takeWhileM (return . f)
372
373 -- | Longest prefix of elements that satisfy the monadic predicate
374 takeWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
375 {-# INLINE_STREAM takeWhileM #-}
376 takeWhileM f (Stream step s n) = Stream step' s (toMax n)
377 where
378 {-# INLINE step' #-}
379 step' s = do
380 r <- step s
381 case r of
382 Yield x s' -> do
383 b <- f x
384 return $ if b then Yield x s' else Done
385 Skip s' -> return $ Skip s'
386 Done -> return $ Done
387
388 -- | Drop the longest prefix of elements that satisfy the predicate
389 dropWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
390 {-# INLINE dropWhile #-}
391 dropWhile f = dropWhileM (return . f)
392
393 data DropWhile s a = DropWhile_Drop s | DropWhile_Yield a s | DropWhile_Next s
394
395 -- | Drop the longest prefix of elements that satisfy the monadic predicate
396 dropWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
397 {-# INLINE_STREAM dropWhileM #-}
398 dropWhileM f (Stream step s n) = Stream step' (DropWhile_Drop s) (toMax n)
399 where
400 -- NOTE: we jump through hoops here to have only one Yield; local data
401 -- declarations would be nice!
402
403 {-# INLINE step' #-}
404 step' (DropWhile_Drop s)
405 = do
406 r <- step s
407 case r of
408 Yield x s' -> do
409 b <- f x
410 return $ if b then Skip (DropWhile_Drop s')
411 else Skip (DropWhile_Yield x s')
412 Skip s' -> return $ Skip (DropWhile_Drop s')
413 Done -> return $ Done
414
415 step' (DropWhile_Yield x s) = return $ Yield x (DropWhile_Next s)
416
417 step' (DropWhile_Next s)
418 = liftM (\r ->
419 case r of
420 Yield x s' -> Skip (DropWhile_Yield x s')
421 Skip s' -> Skip (DropWhile_Next s')
422 Done -> Done
423 ) (step s)
424
425 -- Searching
426 -- ---------
427
428 infix 4 `elem`
429 -- | Check whether the 'Stream' contains an element
430 elem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
431 {-# INLINE_STREAM elem #-}
432 elem x (Stream step s _) = elem_loop s
433 where
434 elem_loop s = do
435 r <- step s
436 case r of
437 Yield y s' | x == y -> return True
438 | otherwise -> elem_loop s'
439 Skip s' -> elem_loop s'
440 Done -> return False
441
442 infix 4 `notElem`
443 -- | Inverse of `elem`
444 notElem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
445 {-# INLINE notElem #-}
446 notElem x s = liftM not (elem x s)
447
448 -- | Yield 'Just' the first element that satisfies the predicate or 'Nothing'
449 -- if no such element exists.
450 find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a)
451 {-# INLINE find #-}
452 find f = findM (return . f)
453
454 -- | Yield 'Just' the first element that satisfies the monadic predicate or
455 -- 'Nothing' if no such element exists.
456 findM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe a)
457 {-# INLINE_STREAM findM #-}
458 findM f (Stream step s _) = find_loop s
459 where
460 find_loop s = do
461 r <- step s
462 case r of
463 Yield x s' -> do
464 b <- f x
465 if b then return $ Just x
466 else find_loop s'
467 Skip s' -> find_loop s'
468 Done -> return Nothing
469
470 -- | Yield 'Just' the index of the first element that satisfies the predicate
471 -- or 'Nothing' if no such element exists.
472 findIndex :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe Int)
473 {-# INLINE_STREAM findIndex #-}
474 findIndex f = findIndexM (return . f)
475
476 -- | Yield 'Just' the index of the first element that satisfies the monadic
477 -- predicate or 'Nothing' if no such element exists.
478 findIndexM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe Int)
479 {-# INLINE_STREAM findIndexM #-}
480 findIndexM f (Stream step s _) = findIndex_loop s 0
481 where
482 findIndex_loop s i = do
483 r <- step s
484 case r of
485 Yield x s' -> do
486 b <- f x
487 if b then return $ Just i
488 else findIndex_loop s' (i+1)
489 Skip s' -> findIndex_loop s' i
490 Done -> return Nothing
491
492 -- Folding
493 -- -------
494
495 -- | Left fold
496 foldl :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
497 {-# INLINE foldl #-}
498 foldl f = foldlM (\a b -> return (f a b))
499
500 -- | Left fold with a monadic operator
501 foldlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
502 {-# INLINE_STREAM foldlM #-}
503 foldlM m z (Stream step s _) = foldlM_go z s
504 where
505 foldlM_go z s = do
506 r <- step s
507 case r of
508 Yield x s' -> do { z' <- m z x; foldlM_go z' s' }
509 Skip s' -> foldlM_go z s'
510 Done -> return z
511
512 -- | Same as 'foldlM'
513 foldM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
514 {-# INLINE foldM #-}
515 foldM = foldlM
516
517 -- | Left fold over a non-empty 'Stream'
518 foldl1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
519 {-# INLINE foldl1 #-}
520 foldl1 f = foldl1M (\a b -> return (f a b))
521
522 -- | Left fold over a non-empty 'Stream' with a monadic operator
523 foldl1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
524 {-# INLINE_STREAM foldl1M #-}
525 foldl1M f (Stream step s sz) = foldl1M_go s
526 where
527 foldl1M_go s = do
528 r <- step s
529 case r of
530 Yield x s' -> foldlM f x (Stream step s' (sz - 1))
531 Skip s' -> foldl1M_go s'
532 Done -> errorEmptyStream "foldl1M"
533
534 -- | Left fold with a strict accumulator
535 foldl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
536 {-# INLINE foldl' #-}
537 foldl' f = foldlM' (\a b -> return (f a b))
538
539 -- | Left fold with a strict accumulator and a monadic operator
540 foldlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
541 {-# INLINE_STREAM foldlM' #-}
542 foldlM' m z (Stream step s _) = foldlM'_go z s
543 where
544 foldlM'_go z s = z `seq`
545 do
546 r <- step s
547 case r of
548 Yield x s' -> do { z' <- m z x; foldlM'_go z' s' }
549 Skip s' -> foldlM'_go z s'
550 Done -> return z
551
552 -- | Left fold over a non-empty 'Stream' with a strict accumulator
553 foldl1' :: Monad m => (a -> a -> a) -> Stream m a -> m a
554 {-# INLINE foldl1' #-}
555 foldl1' f = foldl1M' (\a b -> return (f a b))
556
557 -- | Left fold over a non-empty 'Stream' with a strict accumulator and a
558 -- monadic operator
559 foldl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a
560 {-# INLINE_STREAM foldl1M' #-}
561 foldl1M' f (Stream step s sz) = foldl1M'_go s
562 where
563 foldl1M'_go s = do
564 r <- step s
565 case r of
566 Yield x s' -> foldlM' f x (Stream step s' (sz - 1))
567 Skip s' -> foldl1M'_go s'
568 Done -> errorEmptyStream "foldl1M'"
569
570 -- | Right fold
571 foldr :: Monad m => (a -> b -> b) -> b -> Stream m a -> m b
572 {-# INLINE foldr #-}
573 foldr f = foldrM (\a b -> return (f a b))
574
575 -- | Right fold with a monadic operator
576 foldrM :: Monad m => (a -> b -> m b) -> b -> Stream m a -> m b
577 {-# INLINE_STREAM foldrM #-}
578 foldrM f z (Stream step s _) = foldrM_go s
579 where
580 foldrM_go s = do
581 r <- step s
582 case r of
583 Yield x s' -> f x =<< foldrM_go s'
584 Skip s' -> foldrM_go s'
585 Done -> return z
586
587 -- | Right fold over a non-empty stream
588 foldr1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
589 {-# INLINE foldr1 #-}
590 foldr1 f = foldr1M (\a b -> return (f a b))
591
592 -- | Right fold over a non-empty stream with a monadic operator
593 foldr1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
594 {-# INLINE_STREAM foldr1M #-}
595 foldr1M f (Stream step s _) = foldr1M_go0 s
596 where
597 foldr1M_go0 s = do
598 r <- step s
599 case r of
600 Yield x s' -> foldr1M_go1 x s'
601 Skip s' -> foldr1M_go0 s'
602 Done -> errorEmptyStream "foldr1M"
603
604 foldr1M_go1 x s = do
605 r <- step s
606 case r of
607 Yield y s' -> f x =<< foldr1M_go1 y s'
608 Skip s' -> foldr1M_go1 x s'
609 Done -> return x
610
611 -- Unfolding
612 -- ---------
613
614 -- | Unfold
615 unfold :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
616 {-# INLINE_STREAM unfold #-}
617 unfold f = unfoldM (return . f)
618
619 -- | Unfold with a monadic function
620 unfoldM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
621 {-# INLINE_STREAM unfoldM #-}
622 unfoldM f s = Stream step s Unknown
623 where
624 {-# INLINE step #-}
625 step s = liftM (\r ->
626 case r of
627 Just (x, s') -> Yield x s'
628 Nothing -> Done
629 ) (f s)
630
631 -- Scans
632 -- -----
633
634 -- | Prefix scan
635 prescanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
636 {-# INLINE prescanl #-}
637 prescanl f = prescanlM (\a b -> return (f a b))
638
639 -- | Prefix scan with a monadic operator
640 prescanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
641 {-# INLINE_STREAM prescanlM #-}
642 prescanlM f z (Stream step s sz) = Stream step' (s,z) sz
643 where
644 {-# INLINE step' #-}
645 step' (s,x) = do
646 r <- step s
647 case r of
648 Yield y s' -> do
649 z <- f x y
650 return $ Yield x (s', z)
651 Skip s' -> return $ Skip (s', x)
652 Done -> return Done
653
654 -- | Prefix scan with strict accumulator
655 prescanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
656 {-# INLINE prescanl' #-}
657 prescanl' f = prescanlM' (\a b -> return (f a b))
658
659 -- | Prefix scan with strict accumulator and a monadic operator
660 prescanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
661 {-# INLINE_STREAM prescanlM' #-}
662 prescanlM' f z (Stream step s sz) = Stream step' (s,z) sz
663 where
664 {-# INLINE step' #-}
665 step' (s,x) = x `seq`
666 do
667 r <- step s
668 case r of
669 Yield y s' -> do
670 z <- f x y
671 return $ Yield x (s', z)
672 Skip s' -> return $ Skip (s', x)
673 Done -> return Done
674
675 -- Conversions
676 -- -----------
677
678 -- | Convert a 'Stream' to a list
679 toList :: Monad m => Stream m a -> m [a]
680 {-# INLINE toList #-}
681 toList = foldr (:) []
682
683 -- | Convert a list to a 'Stream'
684 fromList :: Monad m => [a] -> Stream m a
685 {-# INLINE_STREAM fromList #-}
686 fromList xs = Stream step xs Unknown
687 where
688 step (x:xs) = return (Yield x xs)
689 step [] = return Done
690
691
692 errorEmptyStream :: String -> a
693 errorEmptyStream s = error $ "Data.Vector.Fusion.Stream.Monadic."
694 Prelude.++ s Prelude.++ ": empty stream"
695