{-# OPTIONS_HADDOCK prune #-} ----------------------------------------------------------------------------- -- | -- Module : ForSyDe.Atom.Stream -- Copyright : (c) George Ungureanu, 2015-2016 -- License : BSD-style (see the file LICENSE) -- -- Maintainer : ugeorge@kth.se -- Stability : experimental -- Portability : portable -- -- This module defines the shallow-embedded 'Stream' data type and -- utility functions operating on it. In ForSyDe a signal is -- represented as a (partially or totally) /ordered/ sequence of -- events that enables processes to communicate and synchronize. In -- ForSyDe-Atom signals are the main operating type for the MoC -- layer. The 'Stream' type is only the base (potentially infinite) -- structure which can encapsulate events in order to describe -- signals. ----------------------------------------------------------------------------- module ForSyDe.Atom.MoC.Stream where infixr 3 :- -- | Defines a stream of events, encapsulating them in a structure -- isomorphic to an infinite list <ForSyDe-Atom.html#bird87 [Bird87]>, -- thus all properties of lists may also be applied to -- 'Stream's. While, in combination with lazy evaluation, it is -- possible to create and simulate infinite signals, we need to ensure -- that the first/previous event is always fully evaluated, which is -- equivalent to ensuring the the monotonicity property in dataflow -- systems. This translates in the following composition rule: -- -- [non-causal feedback is forbidden] also called "zero-delay" -- feedback loops, are caused by un-evaluated self-referential -- calls. In a feedback loop, there always has to be enough events to -- ensure the data flow. -- -- This rule imposes that the stream of data is uninterrupted in order -- to have an evaluatable kernel every time a new event is produced -- (i.e. to avoid deadlocks), which is ther equivalent to ensuring -- continuity in dataflow systems. This translates in the following -- rule: -- -- [cleaning of signals in a feedback is forbidden] in other words, -- whenever a feedback composition occurs, for each new input at any -- instant in time, a process must react with /at least/ one output -- event. data Stream e = NullS -- ^ terminates a signal | e :- Stream e -- ^ the default constructor appends an -- event to the head of the stream -- | allows for the mapping of an arbitrary function @(a -> b)@ upon -- all the events of a @('Stream' a)@. instance Functor Stream where fmap :: (a -> b) -> Stream a -> Stream b fmap _ NullS = Stream b forall e. Stream e NullS fmap f :: a -> b f (x :: a x:-xs :: Stream a xs) = a -> b f a x b -> Stream b -> Stream b forall e. e -> Stream e -> Stream e :- (a -> b) -> Stream a -> Stream b forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap a -> b f Stream a xs -- | enables the 'Stream' to behave like a 'Control.Applicative.ZipList' instance Applicative Stream where pure :: a -> Stream a pure x :: a x = a x a -> Stream a -> Stream a forall e. e -> Stream e -> Stream e :- Stream a forall e. Stream e NullS _ <*> :: Stream (a -> b) -> Stream a -> Stream b <*> NullS = Stream b forall e. Stream e NullS NullS <*> _ = Stream b forall e. Stream e NullS (f :: a -> b f:-fs :: Stream (a -> b) fs) <*> (x :: a x:-xs :: Stream a xs) = a -> b f a x b -> Stream b -> Stream b forall e. e -> Stream e -> Stream e :- Stream (a -> b) fs Stream (a -> b) -> Stream a -> Stream b forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b <*> Stream a xs -- | provides folding functions useful for implementing utilities, such as 'length'. instance Foldable Stream where foldr :: (a -> b -> b) -> b -> Stream a -> b foldr k :: a -> b -> b k z :: b z = Stream a -> b go where go :: Stream a -> b go NullS = b z go (y :: a y:-ys :: Stream a ys) = a y a -> b -> b `k` Stream a -> b go Stream a ys -- | signal @(1 :- 2 :- NullS)@ is represented as @{1,2}@. instance (Show a) => Show (Stream a) where showsPrec :: Int -> Stream a -> ShowS showsPrec p :: Int p = Bool -> ShowS -> ShowS showParen (Int pInt -> Int -> Bool forall a. Ord a => a -> a -> Bool >1) (ShowS -> ShowS) -> (Stream a -> ShowS) -> Stream a -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . Stream a -> ShowS forall a. Show a => Stream a -> ShowS showStream where showStream :: Stream a -> ShowS showStream (x :: a x :- xs :: Stream a xs) = Char -> ShowS showChar '{' ShowS -> ShowS -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> ShowS forall a. Show a => a -> ShowS showEvent a x ShowS -> ShowS -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . Stream a -> ShowS forall a. Show a => Stream a -> ShowS showStream' Stream a xs showStream (Stream a NullS) = Char -> ShowS showChar '{' ShowS -> ShowS -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . Char -> ShowS showChar '}' showStream' :: Stream a -> ShowS showStream' (x :: a x :- xs :: Stream a xs) = Char -> ShowS showChar ',' ShowS -> ShowS -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> ShowS forall a. Show a => a -> ShowS showEvent a x ShowS -> ShowS -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . Stream a -> ShowS showStream' Stream a xs showStream' (Stream a NullS) = Char -> ShowS showChar '}' showEvent :: a -> ShowS showEvent x :: a x = a -> ShowS forall a. Show a => a -> ShowS shows a x -- | signal @(1 :- 2 :- NullS)@ is read using the string @"{1,2}"@. instance (Read a) => Read (Stream a) where readsPrec :: Int -> ReadS (Stream a) readsPrec d :: Int d = Bool -> ReadS (Stream a) -> ReadS (Stream a) forall a. Bool -> ReadS a -> ReadS a readParen (Int dInt -> Int -> Bool forall a. Ord a => a -> a -> Bool >1) ReadS (Stream a) readStreamStart where readStreamStart :: ReadS (Stream a) readStreamStart = (\ a :: String a -> [(Stream a xs,String c) | ("{",b :: String b) <- ReadS String lex String a , (xs :: Stream a xs,c :: String c) <- ReadS (Stream a) forall e. Read e => String -> [(Stream e, String)] readStream (',' Char -> ShowS forall a. a -> [a] -> [a] : String b) [(Stream a, String)] -> [(Stream a, String)] -> [(Stream a, String)] forall a. [a] -> [a] -> [a] ++ ReadS (Stream a) forall e. String -> [(Stream e, String)] readNull String b]) readStream :: String -> [(Stream e, String)] readStream r :: String r = String -> [(Stream e, String)] readEvent String r [(Stream e, String)] -> [(Stream e, String)] -> [(Stream e, String)] forall a. [a] -> [a] -> [a] ++ String -> [(Stream e, String)] forall e. String -> [(Stream e, String)] readNull String r readEvent :: String -> [(Stream e, String)] readEvent a :: String a = [(e x e -> Stream e -> Stream e forall e. e -> Stream e -> Stream e :- Stream e xs,String d) | (",",b :: String b) <- ReadS String lex String a , (x :: e x,c :: String c) <- ReadS e forall a. Read a => ReadS a reads String b , (xs :: Stream e xs,d :: String d) <- String -> [(Stream e, String)] readStream String c] readNull :: String -> [(Stream e, String)] readNull a :: String a = [(Stream e forall e. Stream e NullS,String b) | ("}",b :: String b) <- ReadS String lex String a] -- | The function 'stream' converts a list into a stream. stream :: [a] -> Stream a stream :: [a] -> Stream a stream [] = Stream a forall e. Stream e NullS stream (x :: a x:xs :: [a] xs) = a x a -> Stream a -> Stream a forall e. e -> Stream e -> Stream e :- ([a] -> Stream a forall a. [a] -> Stream a stream [a] xs) -- | The function 'fromStream' converts a signal into a list. fromStream :: Stream a -> [a] fromStream :: Stream a -> [a] fromStream NullS = [] fromStream (x :: a x:-xs :: Stream a xs) = a x a -> [a] -> [a] forall a. a -> [a] -> [a] : Stream a -> [a] forall a. Stream a -> [a] fromStream Stream a xs -- | Returns the head of a signal. headS :: Stream a -> a headS :: Stream a -> a headS NullS = String -> a forall a. HasCallStack => String -> a error "Empty signal" headS (x :: a x :- _) = a x -- | Returns the tail of a signal tailS :: Stream e -> Stream e tailS NullS = Stream e forall e. Stream e NullS tailS (_ :- a :: Stream e a) = Stream e a -- | Returns the last event in a signal. lastS :: Stream p -> p lastS NullS = String -> p forall a. HasCallStack => String -> a error "Empty signal" lastS (x :: p x:-NullS) = p x lastS (_:- xs :: Stream p xs) = Stream p -> p lastS Stream p xs -- | Returns an infinite list containing the same repeated event. repeatS :: a -> Stream a repeatS :: a -> Stream a repeatS a :: a a = a a a -> Stream a -> Stream a forall e. e -> Stream e -> Stream e :- a -> Stream a forall a. a -> Stream a repeatS a a -- | Returns the first @n@ events in a signal. takeS :: t -> Stream e -> Stream e takeS 0 _ = Stream e forall e. Stream e NullS takeS _ NullS = Stream e forall e. Stream e NullS takeS n :: t n (x :: e x:-xs :: Stream e xs) | t n t -> t -> Bool forall a. Ord a => a -> a -> Bool <= 0 = Stream e forall e. Stream e NullS | Bool otherwise = e x e -> Stream e -> Stream e forall e. e -> Stream e -> Stream e :- t -> Stream e -> Stream e takeS (t nt -> t -> t forall a. Num a => a -> a -> a -1) Stream e xs -- | Drops the first @n@ events in a signal. dropS :: t -> Stream e -> Stream e dropS 0 NullS = Stream e forall e. Stream e NullS dropS _ NullS = Stream e forall e. Stream e NullS dropS n :: t n (x :: e x:-xs :: Stream e xs) | t n t -> t -> Bool forall a. Ord a => a -> a -> Bool <= 0 = e xe -> Stream e -> Stream e forall e. e -> Stream e -> Stream e :-Stream e xs | Bool otherwise = t -> Stream e -> Stream e dropS (t nt -> t -> t forall a. Num a => a -> a -> a -1) Stream e xs -- | Returns the first events of a signal which comply to a condition. takeWhileS :: (a -> Bool) -> Stream a -> Stream a takeWhileS :: (a -> Bool) -> Stream a -> Stream a takeWhileS _ NullS = Stream a forall e. Stream e NullS takeWhileS p :: a -> Bool p (x :: a x:-xs :: Stream a xs) | a -> Bool p a x = a x a -> Stream a -> Stream a forall e. e -> Stream e -> Stream e :- (a -> Bool) -> Stream a -> Stream a forall a. (a -> Bool) -> Stream a -> Stream a takeWhileS a -> Bool p Stream a xs | Bool otherwise = Stream a forall e. Stream e NullS -- | Concatenates two signals. +-+ :: Stream e -> Stream e -> Stream e (+-+) NullS ys :: Stream e ys = Stream e ys (+-+) (x :: e x:-xs :: Stream e xs) ys :: Stream e ys = e x e -> Stream e -> Stream e forall e. e -> Stream e -> Stream e :- (Stream e xs Stream e -> Stream e -> Stream e +-+ Stream e ys) (-$-) :: Functor e => (a -> b) -> Stream (e a) -> Stream (e b) -$- :: (a -> b) -> Stream (e a) -> Stream (e b) (-$-) = (e a -> e b) -> Stream (e a) -> Stream (e b) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap ((e a -> e b) -> Stream (e a) -> Stream (e b)) -> ((a -> b) -> e a -> e b) -> (a -> b) -> Stream (e a) -> Stream (e b) forall b c a. (b -> c) -> (a -> b) -> a -> c . (a -> b) -> e a -> e b forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap -- padS :: a -> Stream a -> Stream a -- padS y NullS = y :- padS y NullS -- padS y (x:-xs) = x :- (padS y xs) -- anyS :: (a -> Bool) -> Stream a -> Bool -- anyS _ NullS = False -- anyS c (x :- xs) = c x || anyS c xs