{-# 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