module Data.Stream
(
Stream(..)
, head
, tail
, map
, intersperse
, iterate
, repeat
, cycle
, unfold
, take
, drop
, splitAt
, takeWhile
, dropWhile
, span
, break
, filter
, partition
, isPrefixOf
, (!!)
, zip
, zipWith
, unzip
, words
, unwords
, lines
, unlines
, listToStream
, streamToList
)
where
import Prelude hiding (head, tail, map, iterate, take, drop, takeWhile,
dropWhile, repeat, cycle, filter, (!!), zip, unzip,
zipWith,words,unwords,lines,unlines, break, span, splitAt)
import Control.Applicative
import Data.Char (isSpace)
data Stream a = Cons a (Stream a) deriving (Show, Eq)
instance Functor Stream where
fmap f (Cons x xs) = Cons (f x) (fmap f xs)
instance Applicative Stream where
pure = repeat
(<*>) = zipWith ($)
instance Monad Stream where
return = repeat
(Cons x xs) >>= f = Cons (head (f x)) (tail (xs >>= f))
head :: Stream a -> a
head (Cons x _ ) = x
tail :: Stream a -> Stream a
tail (Cons _ xs) = xs
intersperse :: a -> Stream a -> Stream a
intersperse y (Cons x xs) = Cons x (Cons y (intersperse y xs))
map :: (a -> b) -> Stream a -> Stream b
map f (Cons x xs) = Cons (f x) (map f xs)
unfold :: (c -> (a,c)) -> c -> Stream a
unfold f c =
let (x,d) = f c
in Cons x (unfold f d)
iterate :: (a -> a) -> a -> Stream a
iterate f x = Cons x (iterate f (f x))
take :: Int -> Stream a -> [a]
take n (Cons x xs)
| n == 0 = []
| n > 0 = x : (take (n 1) xs)
| otherwise = error "Stream.take: negative argument."
drop n xs
| n == 0 = xs
| n > 0 = drop (n 1) (tail xs)
| otherwise = error "Stream.drop: negative argument."
takeWhile :: (a -> Bool) -> Stream a -> [a]
takeWhile p (Cons x xs)
| p x = x : takeWhile p xs
| otherwise = []
dropWhile :: (a -> Bool) -> Stream a -> Stream a
dropWhile p (Cons x xs)
| p x = dropWhile p xs
| otherwise = Cons x xs
repeat :: a -> Stream a
repeat x = Cons x (repeat x)
cycle :: [a] -> Stream a
cycle xs = foldr Cons (cycle xs) xs
filter :: (a -> Bool) -> Stream a -> Stream a
filter p (Cons x xs)
| p x = Cons x (filter p xs)
| otherwise = filter p xs
(!!) :: Int -> Stream a -> a
(!!) n (Cons x xs)
| n == 0 = x
| n > 0 = (!!) (n 1) xs
| otherwise = error "Stream.!! negative argument"
zip :: Stream a -> Stream b -> Stream (a,b)
zip (Cons x xs) (Cons y ys) = Cons (x,y) (zip xs ys)
unzip :: Stream (a,b) -> (Stream a, Stream b)
unzip (Cons (x,y) xys) = (Cons x (fst (unzip xys)),
Cons y (snd (unzip xys)))
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)
span :: (a -> Bool) -> Stream a -> ([a], Stream a)
span p (Cons x xs)
| p x = let (trues, falses) = span p xs
in (x : trues, falses)
| otherwise = ([], Cons x xs)
break :: (a -> Bool) -> Stream a -> ([a], Stream a)
break p = span (not . p)
words :: Stream Char -> Stream String
words xs = let (w, ys) = break isSpace xs
in Cons w (words ys)
unwords :: Stream String -> Stream Char
unwords (Cons x xs) = foldr Cons (Cons ' ' (unwords xs)) x
lines :: Stream Char -> Stream String
lines xs = let (l, ys) = break (== '\n') xs
in Cons l (lines (tail ys))
unlines :: Stream String -> Stream Char
unlines (Cons x xs) = foldr Cons (Cons '\n' (unlines xs)) x
isPrefixOf :: Eq a => [a] -> Stream a -> Bool
isPrefixOf [] _ = True
isPrefixOf (y:ys) (Cons x xs)
| y == x = isPrefixOf ys xs
| otherwise = False
partition :: (a -> Bool) -> Stream a -> (Stream a, Stream a)
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)
inits :: Stream a -> Stream ([a])
inits (Cons x xs) = Cons [] (fmap (x:) (inits xs))
tails :: Stream a -> Stream (Stream a)
tails xs = Cons xs (tails (tail xs))
splitAt :: Int -> Stream a -> ([a], Stream a)
splitAt n xs
| n == 0 = ([],xs)
| n > 0 = let (prefix,rest) = splitAt (n1) (tail xs)
in (head xs : prefix, rest)
| otherwise = error "Stream.splitAt negative argument."
streamToList :: Stream a -> [a]
streamToList (Cons x xs) = x : streamToList xs
listToStream :: [a] -> Stream a
listToStream (x:xs) = Cons x (listToStream xs)
listToStream [] = error "Stream.listToStream applied to finite list"