Stream 0.3.1 → 0.4.7.2
raw patch · 2 files changed
Files
- Data/Stream.hs +83/−26
- Stream.cabal +4/−5
Data/Stream.hs view
@@ -1,5 +1,13 @@ -- | Streams are infinite lists. Most operations on streams are -- completely analogous to the definition in Data.List.+--+-- The functions provided in this package are fairly+-- careful about totality, termination, and productivity.+-- None of the functions should diverge, provided you adhere to the+-- preconditions mentioned in the documentation.+--+-- Note: I get quite a lot of requests regarding a missing Traversable+-- instance for Streams. This has been left out by design. module Data.Stream (@@ -25,6 +33,7 @@ , repeat , cycle , unfold+ , prefix -- * Extracting sublists , take , drop@@ -48,6 +57,10 @@ , zip , zipWith , unzip+ , zip3+ , zipWith3+ , unzip3+ , distribute -- * Functions on streams of characters , words , unwords@@ -61,8 +74,9 @@ import Prelude hiding (head, tail, map, scanl, scanl1, iterate, take, drop, takeWhile,- dropWhile, repeat, cycle, filter, (!!), zip, unzip,- zipWith,words,unwords,lines,unlines, break, span, splitAt)+ dropWhile, repeat, cycle, filter, (!!), + zip, unzip, zipWith, zip3, unzip3, zipWith3,+ words,unwords,lines,unlines, break, span, splitAt) import Control.Applicative import Control.Monad (liftM2)@@ -81,7 +95,7 @@ infixr 5 `Cons` instance Functor Stream where- fmap f (Cons x xs) = Cons (f x) (fmap f xs)+ fmap f ~(Cons x xs) = Cons (f x) (fmap f xs) instance Applicative Stream where pure = repeat@@ -92,7 +106,7 @@ xs >>= f = join (fmap f xs) where join :: Stream (Stream a) -> Stream a- join (Cons xs xss) = Cons (head xs) (join (map tail xss))+ join ~(Cons xs xss) = Cons (head xs) (join (map tail xss)) instance Arbitrary a => Arbitrary (Stream a) where arbitrary = liftM2 Cons arbitrary arbitrary@@ -152,43 +166,43 @@ -- | Apply a function uniformly over all elements of a sequence. map :: (a -> b) -> Stream a -> Stream b-map f (Cons x xs) = Cons (f x) (map f xs)+map f ~(Cons x xs) = Cons (f x) (map f xs) -- | 'intersperse' @y@ @xs@ creates an alternating stream of -- elements from @xs@ and @y@. intersperse :: a -> Stream a -> Stream a-intersperse y (Cons x xs) = Cons x (Cons y (intersperse y xs))+intersperse y ~(Cons x xs) = Cons x (Cons y (intersperse y xs)) -- | Interleave two Streams @xs@ and @ys@, alternating elements -- from each list. -- -- > [x1,x2,...] `interleave` [y1,y2,...] == [x1,y1,x2,y2,...] interleave :: Stream a -> Stream a -> Stream a-interleave (Cons x xs) ys = Cons x (interleave ys xs)+interleave ~(Cons x xs) ys = Cons x (interleave ys xs) -- | '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 f z (Cons x xs) = z <:> scan f (f z x) xs+scan f z ~(Cons x xs) = z <:> scan f (f z x) xs -- | @scan'@ is a strict scan. scan' :: (a -> b -> a) -> a -> Stream b -> Stream a-scan' f z (Cons x xs) = z <:> (scan' f $! (f z x)) xs+scan' f z xs = z <:> (scan' f $! (f z (head xs))) (tail xs) -- | '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 f (Cons x xs) = scan f x xs+scan1 f ~(Cons x xs) = scan f x xs -- | @scan1'@ is a strict scan that has no starting value. scan1' :: (a -> a -> a) -> Stream a -> Stream a-scan1' f (Cons x xs) = scan' f x xs+scan1' f ~(Cons x xs) = scan' f x xs -- | 'transpose' computes the transposition of a stream of streams. transpose :: Stream (Stream a) -> Stream (Stream a)-transpose (Cons (Cons x xs) yss) =+transpose ~(Cons (Cons x xs) yss) = (x <:> map head yss) <:> transpose (xs <:> map tail yss) -- | 'iterate' @f@ @x@ function produces the infinite sequence@@ -198,6 +212,12 @@ iterate :: (a -> a) -> a -> Stream a iterate f x = Cons x (iterate f (f x)) +-- | 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.+prefix :: [a] -> Stream a -> Stream a+prefix xs ys = foldr Cons ys xs+ -- | 'repeat' @x@ returns a constant stream, where all elements are -- equal to @x@. repeat :: a -> Stream a@@ -221,7 +241,7 @@ -- /Beware/: passing a negative integer as the first argument will -- cause an error. take :: Int -> Stream a -> [a]-take n (Cons x xs)+take n ~(Cons x xs) | n == 0 = [] | n > 0 = x : (take (n - 1) xs) | otherwise = error "Stream.take: negative argument."@@ -263,12 +283,15 @@ -- /Beware/: this function may diverge if every element of @xs@ -- satisfies @p@, e.g. @dropWhile even (repeat 0)@ will loop. dropWhile :: (a -> Bool) -> Stream a -> Stream a-dropWhile p (Cons x xs)+dropWhile p ~(Cons x xs) | p x = dropWhile p xs | otherwise = Cons x xs -- | 'span' @p@ @xs@ returns the longest prefix of @xs@ that satisfies -- @p@, together with the remainder of the stream.+--+-- /Beware/: this function may diverge if every element of @xs@+-- satisfies @p@, e.g. @span even (repeat 0)@ will loop. span :: (a -> Bool) -> Stream a -> ([a], Stream a) span p (Cons x xs) | p x = let (trues, falses) = span p xs@@ -276,6 +299,8 @@ | otherwise = ([], Cons x xs) -- | The 'break' @p@ function is equivalent to 'span' @not . p@.+--+-- /Beware/: this function may diverge for the same reason as @span@. break :: (a -> Bool) -> Stream a -> ([a], Stream a) break p = span (not . p) @@ -284,7 +309,7 @@ -- /Beware/: this function may diverge if there is no element of -- @xs@ that satisfies @p@, e.g. @filter odd (repeat 0)@ will loop. filter :: (a -> Bool) -> Stream a -> Stream a-filter p (Cons x xs)+filter p ~(Cons x xs) | p x = Cons x (filter p xs) | otherwise = filter p xs @@ -297,7 +322,7 @@ -- example, @fst (partition even (repeat 0)) == repeat 0@; on the -- other hand @snd (partition even (repeat 0))@ is undefined. partition :: (a -> Bool) -> Stream a -> (Stream a, Stream a)-partition p (Cons x xs) =+partition p ~(Cons x xs) = let (trues,falses) = partition p xs in if p x then (Cons x trues, falses) else (trues, Cons x falses)@@ -309,7 +334,7 @@ -- -- > group $ cycle "Mississippi" = "M" ::: "i" ::: "ss" ::: "i" ::: "ss" ::: "i" ::: "pp" ::: "i" ::: "M" ::: "i" ::: ... group :: Eq a => Stream a -> Stream [a]-group (Cons x ys) = let (xs, zs) = span (\y -> x == y) ys+group ~(Cons x ys) = let (xs, zs) = span (\y -> x == y) ys in (x : xs) <:> group zs -- | The 'isPrefix' function returns @True@ if the first argument is@@ -373,22 +398,55 @@ let ixs = (indicesFrom $! (ix+1)) xs in if p x then Cons ix ixs else ixs --- | The 'zip' function takes two streams and returns a list of--- corresponding pairs.+-- | The 'zip' function takes two streams and returns the stream of+-- pairs obtained by pairing elements at the same position in both+-- argument streams. zip :: Stream a -> Stream b -> Stream (a,b)-zip (Cons x xs) (Cons y ys) = Cons (x,y) (zip xs ys)+zip ~(Cons x xs) ~(Cons y ys) = Cons (x,y) (zip xs ys) +-- | The 'zip3' function behaves as the 'zip' function, but works on+-- three streams.+zip3 :: Stream a -> Stream b -> Stream c -> Stream (a,b,c)+zip3 ~(Cons x xs) ~(Cons y ys) ~(Cons z zs) = Cons (x,y,z) (zip3 xs ys zs)+ -- | The 'zipWith' function generalizes 'zip'. Rather than tupling -- the functions, the elements are combined using the function -- passed as the first argument to 'zipWith'. zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c-zipWith f (Cons x xs) (Cons y ys) = Cons (f x y) (zipWith f xs ys)+zipWith f ~(Cons x xs) ~(Cons y ys) = Cons (f x y) (zipWith f xs ys) +-- | The 'zipWith3' behaves as 'zipWith' but takes three stream+-- arguments.+zipWith3 :: (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d+zipWith3 f ~(Cons x xs) ~(Cons y ys) (Cons z zs) = Cons (f x y z) (zipWith3 f xs ys zs)++-- | The 'distribute' function is similar to the 'sequenceA' function+-- defined in Data.Traversable. Since 'Streams' are not 'Foldable' in+-- general, there is no 'Traversable' instance for streams. They do+-- support a similar notion that only requires the outer type+-- constructor to be functorial.+distribute :: (Functor f) => f (Stream a) -> Stream (f a)+distribute t = Cons (fmap head t) (distribute (fmap tail t))+ -- | The 'unzip' function is the inverse of the 'zip' function. unzip :: Stream (a,b) -> (Stream a, Stream b)-unzip (Cons (x,y) xys) = (Cons x (fst (unzip xys)),+unzip ~(Cons (x,y) xys) = (Cons x (fst (unzip xys)), Cons y (snd (unzip xys))) +-- | The 'unzip3' function is the inverse of the 'zip' function.+unzip3 :: Stream (a,b,c) -> (Stream a, Stream b, Stream c)+unzip3 ~(Cons (x,y,z) xyzs) = ( Cons x (fst3 (unzip3 xyzs))+ , Cons y (snd3 (unzip3 xyzs))+ , Cons z (thd3 (unzip3 xyzs)))+ where+ fst3 :: (a,b,c) -> a+ fst3 (x,_,_) = x + snd3 :: (a,b,c) -> b+ snd3 (_,y,_) = y+ thd3 :: (a,b,c) -> c + thd3 (_,_,z) = z++ -- | The 'words' function breaks a stream of characters into a -- stream of words, which were delimited by white space. --@@ -401,7 +459,7 @@ -- | The 'unwords' function is an inverse operation to 'words'. It -- joins words with separating spaces. unwords :: Stream String -> Stream Char-unwords (Cons x xs) = foldr Cons (Cons ' ' (unwords xs)) x+unwords ~(Cons x xs) = foldr Cons (Cons ' ' (unwords xs)) x -- | The 'lines' function breaks a stream of characters into a list -- of strings at newline characters. The resulting strings do not@@ -416,7 +474,7 @@ -- | The 'unlines' function is an inverse operation to 'lines'. It -- joins lines, after appending a terminating newline to each. unlines :: Stream String -> Stream Char-unlines (Cons x xs) = foldr Cons (Cons '\n' (unlines xs)) x+unlines ~(Cons x xs) = foldr Cons (Cons '\n' (unlines xs)) x -- | The 'toList' converts a stream into an infinite list. toList :: Stream a -> [a]@@ -428,5 +486,4 @@ -- /Beware/: Passing a finite list, will cause an error. fromList :: [a] -> Stream a fromList (x:xs) = Cons x (fromList xs)-fromList [] = error "Stream.listToStream applied to finite list"-+fromList [] = error "Stream.fromList applied to finite list"
Stream.cabal view
@@ -1,12 +1,11 @@ Name: Stream-Version: 0.3.1+Version: 0.4.7.2 License: BSD3 License-file: LICENSE-Author: Wouter Swierstra <wss@cs.nott.ac.uk>,+Author: Wouter Swierstra <wouter.swierstra@gmail.com> Bas van Dijk <v.dijk.bas@gmail.com>-Maintainer: Wouter Swierstra <wss@cs.nott.ac.uk>+Maintainer: Wouter Swierstra <wouter.swierstra@gmail.com> Stability: experimental-Homepage: http://www.cs.nott.ac.uk/~wss/repos/Stream/dist/doc/html/ Synopsis: A library for manipulating infinite lists. Description: This package implements functions, analogous to those from Data.List, to create and manipulate@@ -17,7 +16,7 @@ nothing to do with the work on /Stream Fusion/ by Duncan Coutts, Roman Leshchinskiy, and Don Stewart. Category: Data-Build-Depends: base, QuickCheck >= 2.0, lazysmallcheck >= 0.3+Build-Depends: base < 5, QuickCheck >= 2.0, lazysmallcheck >= 0.3 Build-Type: Simple Exposed-modules: Data.Stream