Package frege.data.Stream

Compiled: Wed Dec 05 00:10:02 PST 2012 from source file: ./frege/data/Stream.fr

Package Documentation

Implementation of and functions for the Stream data type

Contributed by Daniel Gronau

Table of Content

Imports

Instances

instance Applicative Stream

Member Functions

*> :: Stream α -> Stream β -> Stream β

inherited from Applicative.*>

<* :: Stream α -> Stream β -> Stream α

inherited from Applicative.<*

<*> :: Stream (α->β) -> Stream α -> Stream β
return :: α -> Stream α
instance Eq Eq a => Stream a

Member Functions

!= :: Eq α => Stream α -> Stream α -> Bool

inherited from Eq.!=

/= :: Eq α => Stream α -> Stream α -> Bool

inherited from Eq./=

== :: Eq α => Stream α -> Stream α -> Bool

Function generated for derived istance.

hashCode :: Eq α => Stream α -> Int

Function generated for derived istance.

instance Functor Stream

Member Functions

fmap :: (α->β) -> Stream α -> Stream β
instance ListLike Stream

Member Functions

++ :: Stream α -> Stream α -> Stream α
empty :: Stream α
head :: Stream α -> α
length :: Stream α -> Int
null :: Stream α -> Bool
tail :: Stream α -> Stream α
instance ListSource Stream

toList converts a stream into an infinite list.

Member Functions

toList :: Stream α -> [α]
instance Monad Stream

Member Functions

>> :: Stream α -> Stream β -> Stream β

inherited from Monad.>>

>>= :: Stream α -> (α->Stream β) -> Stream β
join :: Stream (Stream α) -> Stream α
instance Monoid Monoid a => Stream a

Member Functions

mconcat :: Monoid α => [Stream α] -> Stream α

inherited from Monoid.Monoid.mconcat

mempty :: Monoid α => Stream α
mtimes :: Monoid α => Int -> Stream α -> Stream α

inherited from Monoid.Monoid.mtimes

instance Ord Ord a => Stream a

Member Functions

< :: Ord α => Stream α -> Stream α -> Bool

inherited from Ord.<

<= :: Ord α => Stream α -> Stream α -> Bool

inherited from Ord.<=

<=> :: Ord α => Stream α -> Stream α -> Ordering

Function generated for derived istance.

> :: Ord α => Stream α -> Stream α -> Bool

inherited from Ord.>

>= :: Ord α => Stream α -> Stream α -> Bool

inherited from Ord.>=

compare :: Ord α => Stream α -> Stream α -> Ordering

inherited from Ord.compare

max :: Ord α => Stream α -> Stream α -> Stream α

inherited from Ord.max

min :: Ord α => Stream α -> Stream α -> Stream α

inherited from Ord.min

instance Semigroup Semigroup a => Stream a

Member Functions

mappend :: Semigroup α => Stream α -> Stream α -> Stream α
sconcat :: Semigroup α => [Stream α] -> Stream α

inherited from Monoid.Semigroup.sconcat

stimes :: Semigroup α => Int -> Stream α -> Stream α

inherited from Monoid.Semigroup.stimes

instance Show Show a => Stream a

A Show instance for Streams. Note that Show.show returns an infinite String. Hence you can't use this function on old fashioned computers with finite memory.

Member Functions

display :: Show α => Stream α -> String

inherited from Show.display

show :: Show α => Stream α -> String
showList :: Show α => [Stream α] -> String -> String

inherited from Show.showList

showsPrec :: Show α => Int -> Stream α -> String -> String

inherited from Show.showsPrec

showsub :: Show α => Stream α -> String

inherited from Show.showsub

Data Types

data Stream a

Streams are infinite lists. Most operations on streams are completely analogous to the definitions for [].

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)

Functions and Values

!! :: 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.

<:> :: a -> Stream a -> Stream a

The <:> operator is a left strict infix version of the Stream.Cons constructor.

In this module, it will always be used when the head part of a Stream result is computed with some function passed as argument.

This way, the strictness of the passed function is indirectly taken in account.

For example, in the result of

 zipWith (,) stream1 stream2

the data of stream1 and stream2 are not evaluated, because the tuple constructor doesn't do it.

Hence

 let us = repeat undefined in length • take 10 • zipWith (,) us $ us

will be 10. Whereas

 let us = repeat undefined in length • take 10 • zipWith (+) us $ us

will be undefined.

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

The break p function is equivalent to span (not <~ p).

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 ...

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.

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.

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 Ord.==) 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.

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.

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.

fromList :: [a] -> Stream a

The fromList converts an infinite list to a stream.

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

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" ::: ...

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 frege.data.List.inits:

inits | = |

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,...]
intersperse :: a -> Stream a -> Stream a

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

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

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

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), ..]

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.

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

Apply a function uniformly over all elements of a sequence.

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.

repeat :: a -> Stream a

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

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.

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.

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.

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

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

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.

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

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

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

transpose computes the transposition of a stream of streams.

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.

unlines :: Stream String -> Stream Char

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

unwords :: Stream String -> Stream Char

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

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

The unzip function is the inverse of the zip function.

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.

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

The zip function takes two streams and returns a list of corresponding pairs.

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.

Functions and Values by Type

Stream String -> Stream Char

unlines, unwords

Stream Char -> Stream String

lines, words

(a->a->a) -> Stream a -> Stream a

scan1, scan1'

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

partition

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

break, span

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

findIndices

(a->Bool) -> Stream a -> Stream a

dropWhile, filter

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

takeWhile

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

findIndex

(a->a) -> a -> Stream a

iterate

Stream (Stream a) -> Stream (Stream a)

transpose

Stream (Stream α) -> Stream α

Monad_Stream.join

Stream a -> Stream a -> Stream a

interleave

Stream a -> Int -> a

!!

Stream a -> Stream (Stream a)

tails

Stream a -> Stream [a]

inits

Stream α -> Stream α -> Stream α

ListLike_Stream.++

Stream α -> Stream α

ListLike_Stream.tail

Stream α -> [α]

ListSource_Stream.toList

Stream α -> Bool

ListLike_Stream.null

Stream α -> Int

ListLike_Stream.length

Stream α -> α

ListLike_Stream.head

[a] -> Stream a

cycle, fromList

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

splitAt

Int -> Stream a -> Stream a

drop

Int -> Stream a -> [a]

take

a -> Stream a -> Stream a

<:>, intersperse, Stream.Cons

a -> Stream a

repeat

α -> Stream α

Applicative_Stream.return

Monoid α => [Stream α] -> Stream α

Monoid_Stream.mconcat

Monoid α => Int -> Stream α -> Stream α

Monoid_Stream.mtimes

Semigroup α => Stream α -> Stream α -> Stream α

Semigroup_Stream.mappend

Semigroup α => [Stream α] -> Stream α

Semigroup_Stream.sconcat

Semigroup α => Int -> Stream α -> Stream α

Semigroup_Stream.stimes

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

group

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

isPrefixOf

Eq a => a -> Stream a -> Stream Int

elemIndices

Eq a => a -> Stream a -> Int

elemIndex

Eq α => Stream α -> Stream α -> Bool

Eq_Stream./=, Eq_Stream.!=, Eq_Stream.==

Eq α => Stream α -> Int

Eq_Stream.hashCode

Ord α => Stream α -> Stream α -> Stream α

Ord_Stream.max, Ord_Stream.min

Ord α => Stream α -> Stream α -> Bool

Ord_Stream.>, Ord_Stream.<=, Ord_Stream.<, Ord_Stream.>=

Ord α => Stream α -> Stream α -> Ordering

Ord_Stream.<=>, Ord_Stream.compare

Show α => Stream α -> String

Show_Stream.show, Show_Stream.display, Show_Stream.showsub

Show α => [Stream α] -> String -> String

Show_Stream.showList

Show α => Int -> Stream α -> String -> String

Show_Stream.showsPrec

Stream α

ListLike_Stream.empty

Monoid α => Stream α

Monoid_Stream.mempty

(a->b->a) -> a -> Stream b -> Stream a

scan, scan'

(a->b) -> Stream a -> Stream b

map

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

unfold

(α->β) -> Stream α -> Stream β

Functor_Stream.fmap

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

unzip

Stream (α->β) -> Stream α -> Stream β

Applicative_Stream.<*>

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

zip

Stream α -> (α->Stream β) -> Stream β

Monad_Stream.>>=

Stream α -> Stream β -> Stream α

Applicative_Stream.<*

Stream α -> Stream β -> Stream β

Applicative_Stream.*>, Monad_Stream.>>

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

zipWith

Valid HTML 4.01 Strict