Data.Stream.Monadic

(Mostly mechanical) adaptation of the Data.Stream module from the stream-fusion package to a monadic Stream datatype similar to the one proposed by Michael Snoyman for the conduit package.

The intention here is to provide a high-level, Data.List-like interface to Database.LevelDB.Iterators with predictable space and time complexity (see Database.LevelDB.Streaming), and without introducing a dependency eg. on one of the streaming libraries (all relevant datatypes are fully exported, though, so it should be straightforward to write wrappers for your favourite streaming library).

Fusion and inlining rules and strictness annotations have been put in place faithfully, and may need further profiling. Also, some functions (from Data.List) have been omitted for various reasons. Missing functions may be added upon request.

Documentation

data Step a s

Constructors

Yield a !s

Skip !s

Done

data Stream m a

Constructors

forall s . Stream (s -> m (Step a s)) (m s)

Instances

Monad m => Functor (Stream m)

Conversion with lists

toList :: (Functor m, Monad m) => Stream m a -> m [a]

fromList :: Monad m => [a] -> Stream m a

Basic functions

append :: (Functor m, Monad m) => Stream m a -> Stream m a -> Stream m a

cons :: (Functor m, Monad m) => a -> Stream m a -> Stream m a

snoc :: (Functor m, Monad m) => Stream m a -> a -> Stream m a

head :: Monad m => Stream m a -> m (Maybe a)

Unlike head, this function does not diverge if the Stream is empty. Instead, Nothing is returned.

last :: Monad m => Stream m a -> m (Maybe a)

Unlike last, this function does not diverge if the Stream is empty. Instead, Nothing is returned.

tail :: (Functor m, Monad m) => Stream m a -> Stream m a

Unlike tail, this function does not diverge if the Stream is empty. Instead, it is the identity in this case.

init :: (Functor m, Monad m) => Stream m a -> Stream m a

Unlike init, this function does not diverge if the Stream is empty. Instead, it is the identity in this case.

null :: Monad m => Stream m a -> m Bool

length :: Monad m => Stream m a -> m Int

Transformations

map :: Monad m => (a -> b) -> Stream m a -> Stream m b

mapM :: (Functor m, Monad m) => (a -> m b) -> Stream m a -> Stream m b

mapM_ :: (Functor m, Monad m) => (a -> m b) -> Stream m a -> Stream m ()

reverse :: (Functor m, Monad m) => Stream m a -> m (Stream m a)

intersperse :: (Functor m, Monad m) => a -> Stream m a -> Stream m a

intercalate :: (Functor m, Monad m) => Stream m a -> Stream m [a] -> Stream m a

Folds

foldl :: Monad m => (b -> a -> b) -> b -> Stream m a -> m b

foldl' :: Monad m => (b -> a -> b) -> b -> Stream m a -> m b

foldr :: (Functor m, Monad m) => (a -> b -> b) -> b -> Stream m a -> m b

foldMap :: (Monoid m, Functor n, Monad n) => (a -> m) -> Stream n a -> n m

foldM :: Monad m => (b -> a -> m b) -> b -> Stream m a -> m b

foldM_ :: Monad m => (b -> a -> m b) -> b -> Stream m a -> m ()

Special folds

concat :: (Functor m, Monad m) => Stream m [a] -> Stream m a

concatMap :: (Functor m, Monad m) => (a -> Stream m b) -> Stream m a -> Stream m b

and :: (Functor m, Monad m) => Stream m Bool -> m Bool

or :: (Functor m, Monad m) => Stream m Bool -> m Bool

any :: Monad m => (a -> Bool) -> Stream m a -> m Bool

all :: Monad m => (a -> Bool) -> Stream m a -> m Bool

sum :: (Num a, Monad m) => Stream m a -> m a

product :: (Num a, Monad m) => Stream m a -> m a

Building streams

Scans

scanl :: (Functor m, Monad m) => (b -> a -> b) -> b -> Stream m a -> Stream m b

Infinite streams

iterate :: Monad m => (a -> a) -> a -> Stream m a

repeat :: Monad m => a -> Stream m a

replicate :: Monad m => Int -> a -> Stream m a

cycle :: (Functor m, Monad m) => Stream m a -> Stream m a

Unlike cycle, this function does not diverge if the Stream is empty. Instead, it is the identity in this case.

Unfolding

unfoldr :: Monad m => (b -> Maybe (a, b)) -> b -> Stream m a

unfoldrM :: (Functor m, Monad m) => (b -> Maybe (a, m b)) -> m b -> Stream m a

Build a stream from a monadic seed (or state function).

Substreams

Extracting substreams

take :: (Functor m, Monad m) => Int -> Stream m a -> Stream m a

drop :: (Functor m, Monad m) => Int -> Stream m a -> Stream m a

splitAt :: (Functor m, Monad m) => Int -> Stream m a -> (Stream m a, Stream m a)

splitAt n s = (take n s, drop n s)

Note that the resulting Streams share their state, so do not interleave traversals.

takeWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a

dropWhile :: (Functor m, Monad m) => (a -> Bool) -> Stream m a -> Stream m a

span :: (Functor m, Monad m) => (a -> Bool) -> Stream m a -> (Stream m a, Stream m a)

break :: (Functor m, Monad m) => (a -> Bool) -> Stream m a -> (Stream m a, Stream m a)

Predicates

isPrefixOf :: (Eq a, Monad m) => Stream m a -> Stream m a -> m Bool

isSuffixOf :: (Eq a, Functor m, Monad m) => Stream m a -> Stream m a -> m Bool

Note that this is:

isSuffixOf a b = reverse a `isPrefixOf` reverse b

It might be more efficient to construct the Streams in reverse order and use isPrefixOf directly, as reverse is O(n) and requires a finite stream argument.

Searching streams

Searching by equality

elem :: (Eq a, Monad m) => a -> Stream m a -> m Bool

notElem :: (Eq a, Monad m) => a -> Stream m a -> m Bool

lookup :: (Eq a, Monad m) => a -> Stream m (a, b) -> m (Maybe b)

Searching with a predicate

find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a)

filter :: Monad m => (a -> Bool) -> Stream m a -> Stream m a

Zipping and unzipping

zip :: (Functor m, Applicative m, Monad m) => Stream m a -> Stream m b -> Stream m (a, b)

zip3 :: (Functor m, Applicative m, Monad m) => Stream m a -> Stream m b -> Stream m c -> Stream m (a, b, c)

zip4 :: (Functor m, Applicative m, Monad m) => Stream m a -> Stream m b -> Stream m c -> Stream m d -> Stream m (a, b, c, d)

zipWith :: (Functor m, Applicative m, Monad m) => (a -> b -> c) -> Stream m a -> Stream m b -> Stream m c

zipWith3 :: (Functor m, Applicative m, Monad m) => (a -> b -> c -> d) -> Stream m a -> Stream m b -> Stream m c -> Stream m d

zipWith4 :: (Functor m, Applicative m, Monad m) => (a -> b -> c -> d -> e) -> Stream m a -> Stream m b -> Stream m c -> Stream m d -> Stream m e

unzip :: (Functor m, Monad m) => Stream m (a, b) -> m ([a], [b])

unzip3 :: (Functor m, Monad m) => Stream m (a, b, c) -> m ([a], [b], [c])

unzip4 :: (Functor m, Monad m) => Stream m (a, b, c, d) -> m ([a], [b], [c], [d])

Special streams

"Set" operations

delete :: (Eq a, Functor m, Monad m) => a -> Stream m a -> Stream m a

insert :: (Ord a, Functor m, Monad m) => a -> Stream m a -> Stream m a

Generalized functions

deleteBy :: (Functor m, Monad m) => (a -> a -> Bool) -> a -> Stream m a -> Stream m a

User-supplied comparison, replacing an Ord context

insertBy :: (Functor m, Monad m) => (a -> a -> Ordering) -> a -> Stream m a -> Stream m a

The "generic" operations

genericLength :: (Num i, Functor m, Monad m) => Stream m a -> m i

genericTake :: (Integral i, Functor m, Monad m) => i -> Stream m a -> Stream m a

genericDrop :: (Integral i, Functor m, Monad m) => i -> Stream m a -> Stream m a

genericSplitAt :: (Integral i, Functor m, Monad m) => i -> Stream m a -> (Stream m a, Stream m a)

genericReplicate :: (Integral i, Functor m, Monad m) => i -> a -> Stream m a

enumFromToInt :: Monad m => Int -> Int -> Stream m Int

Like fromList ([n..m] :: [Int]) but avoids allocating a list

enumFromToChar :: Monad m => Char -> Char -> Stream m Char

Like fromList ([n..m] :: [Char]) but avoids allocating a list

enumDeltaInteger :: Monad m => Integer -> Integer -> Stream m Integer

Like fromList ([n,n+d..] :: [Integer]) but avoids allocating a list