Data.Stream

Streams are infinite lists. Most operations on streams are completely analogous to the definition in Data.List.

The type of streams

data Stream a

An infinite sequence.

Beware: If you use any function from the Eq or Ord class to compare two equal streams, these functions will diverge.

Constructors

Cons a (Stream a)

Instances

Monad Stream

Functor Stream

Applicative Stream

Eq a => Eq (Stream a)

Ord a => Ord (Stream a)

Show a => Show (Stream a)

A Show instance for Streams that takes the right associativity into account and so doesn't put parenthesis around the tail of the Stream. Note that show returns an infinite String.

Arbitrary a => Arbitrary (Stream a)

CoArbitrary a => CoArbitrary (Stream a)

Serial a => Serial (Stream a)

Basic functions

(<:>) :: a -> Stream a -> Stream a

The <:> operator is an infix version of the Cons constructor.

head :: Stream a -> a

Extract the first element of the sequence.

tail :: Stream a -> Stream a

Extract the sequence following the head of the stream.

inits :: Stream a -> Stream [a]

The inits function takes a stream xs and returns all the finite prefixes of xs.

Note that this inits is lazier then Data.List.inits:

 inits _|_ = [] ::: _|_

while for Data.List.inits:

 inits _|_ = _|_

tails :: Stream a -> Stream (Stream a)

The tails function takes a stream xs and returns all the suffixes of xs.

Stream transformations

map :: (a -> b) -> Stream a -> Stream b

Apply a function uniformly over all elements of a sequence.

intersperse :: a -> Stream a -> Stream a

intersperse y xs creates an alternating stream of elements from xs and y.

interleave :: Stream a -> Stream a -> Stream a

Interleave two Streams xs and ys, alternating elements from each list.

 [x1,x2,...] `interleave` [y1,y2,...] == [x1,y1,x2,y2,...]

scan :: (a -> b -> a) -> a -> Stream b -> Stream a

scan yields a stream of successive reduced values from:

 scan f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]

scan' :: (a -> b -> a) -> a -> Stream b -> Stream a

scan' is a strict scan.

scan1 :: (a -> a -> a) -> Stream a -> Stream a

scan1 is a variant of scan that has no starting value argument:

 scan1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

scan1' :: (a -> a -> a) -> Stream a -> Stream a

scan1' is a strict scan that has no starting value.

transpose :: Stream (Stream a) -> Stream (Stream a)

transpose computes the transposition of a stream of streams.

Building streams

iterate :: (a -> a) -> a -> Stream a

iterate f x function produces the infinite sequence of repeated applications of f to x.

 iterate f x = [x, f x, f (f x), ..]

repeat :: a -> Stream a

repeat x returns a constant stream, where all elements are equal to x.

cycle :: [a] -> Stream a

cycle xs returns the infinite repetition of xs:

 cycle [1,2,3] = Cons 1 (Cons 2 (Cons 3 (Cons 1 (Cons 2 ...

unfold :: (c -> (a, c)) -> c -> Stream a

The unfold function is similar to the unfold for lists. Note there is no base case: all streams must be infinite.

prefix :: [a] -> Stream a -> Stream a

The prefix function adds a list as a prefix to an existing stream. If the list is infinite, it is converted to a Stream and the second argument is ignored.

Extracting sublists

take :: Int -> Stream a -> [a]

take n xs returns the first n elements of xs.

Beware: passing a negative integer as the first argument will cause an error.

drop :: Int -> Stream a -> Stream a

drop n xs drops the first n elements off the front of the sequence xs.

Beware: passing a negative integer as the first argument will cause an error.

splitAt :: Int -> Stream a -> ([a], Stream a)

The splitAt function takes an integer n and a stream xs and returns a pair consisting of the prefix of xs of length n and the remaining stream immediately following this prefix.

Beware: passing a negative integer as the first argument will cause an error.

takeWhile :: (a -> Bool) -> Stream a -> [a]

takeWhile p xs returns the longest prefix of the stream xs for which the predicate p holds.

dropWhile :: (a -> Bool) -> Stream a -> Stream a

dropWhile p xs returns the suffix remaining after takeWhile p xs.

Beware: this function may diverge if every element of xs satisfies p, e.g. dropWhile even (repeat 0) will loop.

span :: (a -> Bool) -> Stream a -> ([a], Stream a)

span p xs returns the longest prefix of xs that satisfies p, together with the remainder of the stream.

break :: (a -> Bool) -> Stream a -> ([a], Stream a)

The break p function is equivalent to span not . p.

filter :: (a -> Bool) -> Stream a -> Stream a

filter p xs, removes any elements from xs that do not satisfy p.

Beware: this function may diverge if there is no element of xs that satisfies p, e.g. filter odd (repeat 0) will loop.

partition :: (a -> Bool) -> Stream a -> (Stream a, Stream a)

The partition function takes a predicate p and a stream xs, and returns a pair of streams. The first stream corresponds to the elements of xs for which p holds; the second stream corresponds to the elements of xs for which p does not hold.

Beware: One of the elements of the tuple may be undefined. For example, fst (partition even (repeat 0)) == repeat 0; on the other hand snd (partition even (repeat 0)) is undefined.

group :: Eq a => Stream a -> Stream [a]

The group function takes a stream and returns a stream of lists such that flattening the resulting stream is equal to the argument. Moreover, each sublist in the resulting stream contains only equal elements. For example,

 group $ cycle "Mississippi" = "M" ::: "i" ::: "ss" ::: "i" ::: "ss" ::: "i" ::: "pp" ::: "i" ::: "M" ::: "i" ::: ...

Sublist predicates

isPrefixOf :: Eq a => [a] -> Stream a -> Bool

The isPrefix function returns True if the first argument is a prefix of the second.

Indexing streams

(!!) :: Stream a -> Int -> a

xs !! n returns the element of the stream xs at index n. Note that the head of the stream has index 0.

Beware: passing a negative integer as the first argument will cause an error.

elemIndex :: Eq a => a -> Stream a -> Int

The elemIndex function returns the index of the first element in the given stream which is equal (by ==) to the query element,

Beware: elemIndex x xs will diverge if none of the elements of xs equal x.

elemIndices :: Eq a => a -> Stream a -> Stream Int

The elemIndices function extends elemIndex, by returning the indices of all elements equal to the query element, in ascending order.

Beware: elemIndices x xs will diverge if any suffix of xs does not contain x.

findIndex :: (a -> Bool) -> Stream a -> Int

The findIndex function takes a predicate and a stream and returns the index of the first element in the stream that satisfies the predicate,

Beware: findIndex p xs will diverge if none of the elements of xs satisfy p.

findIndices :: (a -> Bool) -> Stream a -> Stream Int

The findIndices function extends findIndex, by returning the indices of all elements satisfying the predicate, in ascending order.

Beware: findIndices p xs will diverge if all the elements of any suffix of xs fails to satisfy p.

Zipping and unzipping streams

zip :: Stream a -> Stream b -> Stream (a, b)

The zip function takes two streams and returns the stream of pairs obtained by pairing elements at the same position in both argument streams.

zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c

The zipWith function generalizes zip. Rather than tupling the functions, the elements are combined using the function passed as the first argument to zipWith.

unzip :: Stream (a, b) -> (Stream a, Stream b)

The unzip function is the inverse of the zip function.

zip3 :: Stream a -> Stream b -> Stream c -> Stream (a, b, c)

The zip3 function behaves as the zip function, but works on three streams.

zipWith3 :: (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d

The zipWith3 behaves as zipWith but takes three stream arguments.

unzip3 :: Stream (a, b, c) -> (Stream a, Stream b, Stream c)

The unzip3 function is the inverse of the zip function.

Functions on streams of characters

words :: Stream Char -> Stream String

The words function breaks a stream of characters into a stream of words, which were delimited by white space.

Beware: if the stream of characters xs does not contain white space, accessing the tail of words xs will loop.

unwords :: Stream String -> Stream Char

The unwords function is an inverse operation to words. It joins words with separating spaces.

lines :: Stream Char -> Stream String

The lines function breaks a stream of characters into a list of strings at newline characters. The resulting strings do not contain newlines.

Beware: if the stream of characters xs does not contain newline characters, accessing the tail of lines xs will loop.

unlines :: Stream String -> Stream Char

The unlines function is an inverse operation to lines. It joins lines, after appending a terminating newline to each.

Converting to and from an infinite list

toList :: Stream a -> [a]

The toList converts a stream into an infinite list.

fromList :: [a] -> Stream a

The fromList converts an infinite list to a stream.

Beware: Passing a finite list, will cause an error.