Portability | portable, requires cpp |
---|---|
Stability | experimental |
Maintainer | dons@cse.unsw.edu.au |
Tested with : GHC 6.6
Stream fusion for sequences. Described in:
- Stream Fusion: From Lists to Streams to Nothing at All, by Duncan Coutts, Roman Leshchinskiy and Don Stwwart, ICFP 2007. http://www.cse.unsw.edu.au/~dons/papers/CLS07.html
- Rewriting Haskell Strings, by Duncan Coutts, Don Stewart and Roman Leshchinskiy, Practical Aspects of Declarative Languages 8th International Symposium, PADL 2007, 2007. http://www.cse.unsw.edu.au/~dons/papers/CSL06.html
See the source for the complete story:
- data Stream a = forall s . Unlifted s => Stream !(s -> Step a s) !s
- data Step a s
- stream :: [a] -> Stream a
- unstream :: Stream a -> [a]
- data L a = L a
- append :: Stream a -> Stream a -> Stream a
- append1 :: Stream a -> [a] -> [a]
- cons :: a -> Stream a -> Stream a
- snoc :: Stream a -> a -> Stream a
- head :: Stream a -> a
- last :: Stream a -> a
- tail :: Stream a -> Stream a
- init :: Stream a -> Stream a
- null :: Stream a -> Bool
- length :: Stream a -> Int
- map :: (a -> b) -> Stream a -> Stream b
- intersperse :: a -> Stream a -> Stream a
- foldl :: (b -> a -> b) -> b -> Stream a -> b
- foldl' :: (b -> a -> b) -> b -> Stream a -> b
- foldl1 :: (a -> a -> a) -> Stream a -> a
- foldl1' :: (a -> a -> a) -> Stream a -> a
- foldr :: (a -> b -> b) -> b -> Stream a -> b
- foldr1 :: (a -> a -> a) -> Stream a -> a
- concat :: Stream [a] -> [a]
- concatMap :: (a -> Stream b) -> Stream a -> Stream b
- and :: Stream Bool -> Bool
- or :: Stream Bool -> Bool
- any :: (a -> Bool) -> Stream a -> Bool
- all :: (a -> Bool) -> Stream a -> Bool
- sum :: Num a => Stream a -> a
- product :: Num a => Stream a -> a
- maximum :: Ord a => Stream a -> a
- minimum :: Ord a => Stream a -> a
- strictMaximum :: Ord a => Stream a -> a
- strictMinimum :: Ord a => Stream a -> a
- scanl :: (b -> a -> b) -> b -> Stream a -> Stream b
- scanl1 :: (a -> a -> a) -> Stream a -> Stream a
- iterate :: (a -> a) -> a -> Stream a
- repeat :: a -> Stream a
- replicate :: Int -> a -> Stream a
- cycle :: Stream a -> Stream a
- unfoldr :: (b -> Maybe (a, b)) -> b -> Stream a
- take :: Int -> Stream a -> Stream a
- drop :: Int -> Stream a -> Stream a
- splitAt :: Int -> Stream a -> ([a], [a])
- takeWhile :: (a -> Bool) -> Stream a -> Stream a
- dropWhile :: (a -> Bool) -> Stream a -> Stream a
- isPrefixOf :: Eq a => Stream a -> Stream a -> Bool
- elem :: Eq a => a -> Stream a -> Bool
- lookup :: Eq a => a -> Stream (a, b) -> Maybe b
- find :: (a -> Bool) -> Stream a -> Maybe a
- filter :: (a -> Bool) -> Stream a -> Stream a
- index :: Stream a -> Int -> a
- findIndex :: (a -> Bool) -> Stream a -> Maybe Int
- elemIndex :: Eq a => a -> Stream a -> Maybe Int
- elemIndices :: Eq a => a -> Stream a -> Stream Int
- findIndices :: (a -> Bool) -> Stream a -> Stream Int
- zip :: Stream a -> Stream b -> Stream (a, b)
- zip3 :: Stream a -> Stream b -> Stream c -> Stream (a, b, c)
- zip4 :: Stream a -> Stream b -> Stream c -> Stream d -> Stream (a, b, c, d)
- zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
- zipWith3 :: (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d
- zipWith4 :: (a -> b -> c -> d -> e) -> Stream a -> Stream b -> Stream c -> Stream d -> Stream e
- unzip :: Stream (a, b) -> ([a], [b])
- insertBy :: (a -> a -> Ordering) -> a -> Stream a -> Stream a
- maximumBy :: (a -> a -> Ordering) -> Stream a -> a
- minimumBy :: (a -> a -> Ordering) -> Stream a -> a
- genericLength :: Num i => Stream b -> i
- genericTake :: Integral i => i -> Stream a -> Stream a
- genericDrop :: Integral i => i -> Stream a -> Stream a
- genericIndex :: Integral a => Stream b -> a -> b
- genericSplitAt :: Integral i => i -> Stream a -> ([a], [a])
- enumFromToInt :: Int -> Int -> Stream Int
- enumFromToChar :: Char -> Char -> Stream Char
- enumDeltaInteger :: Integer -> Integer -> Stream Integer
- foldM :: Monad m => (b -> a -> m b) -> b -> Stream a -> m b
- foldM_ :: Monad m => (b -> a -> m b) -> b -> Stream a -> m ()
- return :: a -> Stream a
- guard :: Bool -> Stream a -> Stream a
- bind :: (a -> Bool) -> (a -> Stream b) -> Stream a -> Stream b
- mapFilter :: (a -> Bool) -> (a -> b) -> Stream a -> Stream b
- declare :: (a -> Stream b) -> a -> Stream b
The stream data type
A stream.
It is important that we never construct a bottom stream, because the fusion rule is not true for bottom streams.
(replicate 1 True) ++ (tail undefined)
The suspicion is that under fusion the append will force the bottom.
A stream step.
A step either ends a stream, skips a value, or yields a value
Conversions with lists
Boxes for user's state. This is the gateway for user's types into unlifted stream states. The L is always safe since it's liftedlazy, exposingseqing it does nothing. S is unlifted and so is only suitable for users states that we know we can be strict in. This requires attention and auditing.
L a |
Unlifted (L a) |
Basic stream functions
Stream transformations
intersperse :: a -> Stream a -> Stream aSource
Reducing streams (folds)
Special folds
strictMaximum :: Ord a => Stream a -> aSource
strictMinimum :: Ord a => Stream a -> aSource
Building lists
Scans
Infinite streams
Unfolding
Substreams
Extracting substreams
Predicates
Searching streams
Searching by equality
Searching with a predicate
Indexing streams
Zipping and unzipping streams
zipWith4 :: (a -> b -> c -> d -> e) -> Stream a -> Stream b -> Stream c -> Stream d -> Stream eSource
Special streams
Functions on strings
User-supplied comparison (replacing an Ord context)
The "generic" operations
genericLength :: Num i => Stream b -> iSource
genericTake :: Integral i => i -> Stream a -> Stream aSource
genericDrop :: Integral i => i -> Stream a -> Stream aSource
genericIndex :: Integral a => Stream b -> a -> bSource
genericSplitAt :: Integral i => i -> Stream a -> ([a], [a])Source