Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Bluefin.Algae.Coroutine
Description
Coroutines: yield as an algebraic effect
Iterators
A simple use case of coroutines is as an expressive way of defining iterators.
An iterator is just a program which yields values. The following example yields the integers 1, 2, 3, 4.
range1to4 :: z :> zz => Handler (Coroutine Int ()) z -> Eff zz () range1to4 h = doyield
h 1yield
h 2yield
h 3yield
h 4
The forCoroutine
handler is a "for" loop over an iterator,
running the loop body for every yielded element.
Here we collect the even values into a list stored in mutable State
.
filterEven :: z :> zz => Handler (State [Int]) z -> Eff zz ()
filterEven h =
forCoroutine
range1to4 \n ->
if n `mod` 2 == 0
then modify h (n :)
else pure ()
filterEvenResult :: [Int]
filterEvenResult = runPureEff $ execState [] filterEven
-- 1 and 3 are filtered out, 2 and 4 are pushed into the queue
in that order, so they appear in reverse order.
-- filterEvenResult == [4,2]
Cooperative concurrency
Coroutines are "cooperative threads", passing control to other coroutines
with explicit yield
calls.
In the following example, two threads yield a string back and forth, appending a suffix every time.
pingpong :: Eff ss String pingpong =withCoroutine
coThread mainThread where coThread z0 h = do z1 <-yield
h (z0 ++ "pong") z2 <-yield
h (z1 ++ "dong")yield
h (z2 ++ "bong") mainThread h = do s1 <-yield
h "ping" s2 <-yield
h (s1 ++ "ding") s3 <-yield
h (s2 ++ "bing") pure s3 -- runPureEff pingpong == "pingpongdingdongbingbong"
More than two coroutines may be interleaved. In the snippet below, four users pass a string to each other, extending it with breadcrumbs each time.
For example, userLL
sends a string to userLR
(identified using the
Left (Right _)
constructors in the yield
argument). When userLL
receives a second string s'
(from anywhere, in this case it will come from
userRR
), it forwards it to userRL
.
echo :: Eff ss String echo =loopCoPipe
((userLL |+ userLR) |+ (userRL |+ userRR)) (Left (Left "S")) where userLL =toCoPipe
\s h -> do s' <-yield
h (Left (Right (s ++ "-LL"))) -- send to userLRyield
h (Right (Left (s' ++ "-LL"))) -- send to userRL userLR =toCoPipe
\s h -> do s' <-yield
h (Right (Left (s ++ "-LR"))) -- send to userRLyield
h (Right (Right (s' ++ "-LR"))) -- send to userRR userRL =toCoPipe
\s h -> do s' <-yield
h (Right (Right (s ++ "-RL"))) -- send to userRRyield
h (Left (Right (s' ++ "-RL"))) -- send to userLR userRR =toCoPipe
\s h -> do s' <-yield
h (Left (Left (s ++ "-RR"))) -- send to userLL pure (s' ++ "-RR") -- terminate (|+) =eitherCoPipe
id -- runPureEff echo == "S-LL-LR-RL-RR-LL-RL-LR-RR"
References
Coroutines are also known as generators in Javascript and Python.
- Coroutine and Generator on Wikipedia
- Generators in Javascript
- Generators in Python
Synopsis
- data Coroutine o i :: AEffect where
- yield :: z :> zz => Handler (Coroutine o i) z -> o -> Eff zz i
- withCoroutine :: forall o i a zz. (i -> ScopedEff (Coroutine o i) zz a) -> ScopedEff (Coroutine i o) zz a -> Eff zz a
- forCoroutine :: forall o i a zz. ScopedEff (Coroutine o i) zz a -> (o -> Eff zz i) -> Eff zz a
- type (:->) = Coroutine
- apply :: z :> zz => Handler (a :-> b) z -> a -> Eff zz b
- withFunction :: forall a b r zz. (a -> Eff zz b) -> ScopedEff (a :-> b) zz r -> Eff zz r
- newtype Pipe i o m a = MkPipe (m (PipeEvent i o m a))
- data PipeEvent i o m a
- newtype CoPipe i o m a = MkCoPipe (i -> Pipe i o m a)
- stepPipe :: Pipe i o m a -> m (PipeEvent i o m a)
- applyCoPipe :: CoPipe i o m a -> i -> Pipe i o m a
- next :: Functor m => CoPipe i o m Void -> i -> m (o, CoPipe i o m Void)
- simpleCoPipe :: Functor m => (i -> m o) -> CoPipe i o m void
- voidCoPipe :: CoPipe Void o m a
- nothingPipe :: Applicative m => Pipe i (Maybe o) m void
- nothingCoPipe :: Applicative m => CoPipe i (Maybe o) m void
- mapPipe :: Functor m => (i' -> i) -> (o -> o') -> (a -> a') -> Pipe i o m a -> Pipe i' o' m a'
- mapCoPipe :: Functor m => (i' -> i) -> (o -> o') -> (a -> a') -> CoPipe i o m a -> CoPipe i' o' m a'
- eitherPipe :: Monad m => (i -> Either i1 i2) -> CoPipe i1 o m a -> Pipe i2 o m a -> Pipe i o m a
- eitherCoPipe :: Functor m => (i -> Either i1 i2) -> CoPipe i1 o m a -> CoPipe i2 o m a -> CoPipe i o m a
- openPipe :: Applicative m => Pipe i o m () -> Pipe i (Maybe o) m void
- openCoPipe :: Applicative m => CoPipe i o m () -> CoPipe i (Maybe o) m void
- runPipe :: Monad m => CoPipe i o m Void -> Pipe o i m a -> m a
- runCoPipe :: Monad m => CoPipe i o m Void -> CoPipe o i m a -> o -> m a
- forPipe :: Monad m => Pipe i o m a -> (o -> m i) -> m a
- forCoPipe :: Monad m => CoPipe i o m a -> (o -> m i) -> i -> m a
- loopPipe :: Monad m => Pipe o o m a -> m a
- loopCoPipe :: Monad m => CoPipe o o m a -> o -> m a
- feedPipe :: Monad m => [i] -> Pipe i o m a -> m [o]
- feedCoPipe :: Monad m => [i] -> CoPipe i o m a -> m [o]
- type CoPipeSEff i o zz a = i -> ScopedEff (Coroutine o i) zz a
- toCoPipe :: forall o i a zz. CoPipeSEff i o zz a -> CoPipe i o (Eff zz) a
- type PipeSEff i o zz a = ScopedEff (Coroutine o i) zz a
- toPipe :: forall o i a zz. PipeSEff i o zz a -> Pipe i o (Eff zz) a
- withCoPipe :: forall o i a zz. CoPipe i o (Eff zz) a -> ScopedEff (Coroutine i o) zz a -> Eff zz a
- type CoPipeEff i o zz a = forall z. z :> zz => i -> Handler (Coroutine o i) z -> Eff zz a
- fromCoPipe :: CoPipe i o (Eff zz) a -> CoPipeEff i o zz a
- type PipeEff i o zz a = forall z. z :> zz => Handler (Coroutine o i) z -> Eff zz a
- fromPipe :: Pipe i o (Eff zz) a -> PipeEff i o zz a
Coroutines
Operations
Handlers
Arguments
:: forall o i a zz. (i -> ScopedEff (Coroutine o i) zz a) | |
-> ScopedEff (Coroutine i o) zz a | Starting coroutine |
-> Eff zz a |
Interleave the execution of two coroutines, feeding each one's output to the other's input. Return the result of the first thread to terminate (the other is discarded)
Arguments
:: forall o i a zz. ScopedEff (Coroutine o i) zz a | Iterator |
-> (o -> Eff zz i) | Loop body |
-> Eff zz a |
Iterate through a coroutine:
execute the loop body o -> Eff zz i
for every call to Yield
in the coroutine.
Functions
withFunction :: forall a b r zz. (a -> Eff zz b) -> ScopedEff (a :-> b) zz r -> Eff zz r Source #
Interpret (
with a function.:->
)
Pipes
Definition
Output-first coroutine.
A Pipe
represents a coroutine as a state machine:
a Pipe
yields an output o
and waits for an input i
, or terminates with
a result a
.
+--------------+ +----------------+ |Pipe
i o m a | (Yielding
o)---> |CoPipe
i o m a | | | <------(input i) | | +--------------+ +----------------+ v (Done
) +---+ | a | +---+
Unwrap
Constructors
simpleCoPipe :: Functor m => (i -> m o) -> CoPipe i o m void Source #
A CoPipe
which runs the same function on every input.
nothingPipe :: Applicative m => Pipe i (Maybe o) m void Source #
Yield Nothing
forever.
nothingCoPipe :: Applicative m => CoPipe i (Maybe o) m void Source #
Yield Nothing
forever.
Pipe combinators
mapPipe :: Functor m => (i' -> i) -> (o -> o') -> (a -> a') -> Pipe i o m a -> Pipe i' o' m a' Source #
Transform inputs and outputs of a Pipe
.
mapCoPipe :: Functor m => (i' -> i) -> (o -> o') -> (a -> a') -> CoPipe i o m a -> CoPipe i' o' m a' Source #
Transform the input and output of a CoPipe
.
Arguments
:: Monad m | |
=> (i -> Either i1 i2) | Dispatch input |
-> CoPipe i1 o m a | Left copipe |
-> Pipe i2 o m a | Right pipe |
-> Pipe i o m a |
Sum a copipe and a pipe with the same output type, branching on the input type.
Arguments
:: Functor m | |
=> (i -> Either i1 i2) | Dispatch input |
-> CoPipe i1 o m a | Left copipe |
-> CoPipe i2 o m a | Right copipe |
-> CoPipe i o m a |
Sum two copipes with the same output type, branching on the input type.
openCoPipe :: Applicative m => CoPipe i o m () -> CoPipe i (Maybe o) m void Source #
Destructors
loopCoPipe :: Monad m => CoPipe o o m a -> o -> m a Source #
Forward the output of a CoPipe
to its input.
feedPipe :: Monad m => [i] -> Pipe i o m a -> m [o] Source #
Run a Pipe
with a fixed number of inputs.
feedCoPipe :: Monad m => [i] -> CoPipe i o m a -> m [o] Source #
Run a CoPipe
with a fixed number of inputs.
Handlers involving pipes
Using the handlers toCoPipe
and toPipe
as primitives,
we can define the other handlers.
withCoroutine
g f =runPipe
(toCoPipe
g) (toPipe
f)forCoroutine
g f =runPipe
(simpleCoPipe
g) (toPipe
f)withCoPipe
g f =runPipe
g (toPipe
f)
type CoPipeSEff i o zz a = i -> ScopedEff (Coroutine o i) zz a Source #
toCoPipe :: forall o i a zz. CoPipeSEff i o zz a -> CoPipe i o (Eff zz) a Source #
Convert a coroutine that doesn't return into a CoPipe
.
toPipe :: forall o i a zz. PipeSEff i o zz a -> Pipe i o (Eff zz) a Source #
Evaluate a coroutine into a Pipe
.
Arguments
:: forall o i a zz. CoPipe i o (Eff zz) a | |
-> ScopedEff (Coroutine i o) zz a | Starting coroutine |
-> Eff zz a |
Interleave the execution of a copipe and a coroutine.
Interpreting pipes as coroutines
fromCoPipe :: CoPipe i o (Eff zz) a -> CoPipeEff i o zz a Source #
Convert a CoPipe
into a coroutine.