pipes 1.0.2 → 2.0.0

raw patch · 5 files changed

+1243/−431 lines, 5 filesdep +transformersdep −mtlPVP ok

version bump matches the API change (PVP)

Dependencies added: transformers

Dependencies removed: mtl

API changes (from Hackage documentation)

Files

• Control/Monad/Trans/Free.hs +77/−0
• Control/Pipe.hs +516/−230
• Control/Pipe/Common.hs +214/−181
• Control/Pipe/Final.hs +424/−0
• pipes.cabal +12/−20

@@ -0,0 +1,77 @@+{-| Every functor @f@ gives rise to a corresponding free monad: @Free f@.++    A free monad over a functor resembles a \"list\" of that functor:++    * 'pure' behaves like @[]@ by not using the functor at all++    * 'wrap' behaves like @(:)@ by prepending another layer of the functor+-}+module Control.Monad.Trans.Free (+    -- * The Free monad+    FreeF(..),+    Free(..),+    wrap,+    runFree,+    -- * The FreeT monad transformer+    FreeT(..),+    ) where++import Control.Applicative+import Control.Monad+import Control.Monad.Trans.Class+import Data.Functor.Identity++data FreeF f r x = Pure r | Wrap (f x)++{-|+    The 'Free' type is isomorphic to:++> data Free f r = Pure r | Wrap (f (Free f r))++    ... except that if you want to pattern match against those constructors, you+    must first use 'runFree' to unwrap the value first.++    Similarly, you don't use the raw constructors to build a value of type+    'Free'.  You instead use the smart constructors 'pure' (from+    @Control.Applicative@) and 'wrap'.+-}+type Free f = FreeT f Identity++wrap :: (Monad m) => f (FreeT f m r) -> FreeT f m r+wrap = FreeT . return . Wrap++runFree :: Free f r -> FreeF f r (Free f r)+runFree = runIdentity . runFreeT++{-|+    A free monad transformer alternates nesting the base functor @f@ and the+    base monad @m@.++    * @f@ - The functor that generates the free monad++    * @m@ - The base monad++    * @r@ - The type of the return value++    This type commonly arises in coroutine/iteratee libraries under various+    names.+-}+data FreeT f m r = FreeT { runFreeT :: m (FreeF f r (FreeT f m r)) }++instance (Functor f, Monad m) => Monad (FreeT f m) where+    return = FreeT . return . Pure+    m >>= f = FreeT $ do+        x <- runFreeT m+        runFreeT $ case x of+            Pure r -> f r+            Wrap a -> wrap $ fmap (>>= f) a++instance (Functor f, Monad m) => Functor (FreeT f m) where+    fmap = liftM++instance (Functor f, Monad m) => Applicative (FreeT f m) where+    pure = return+    (<*>) = ap++instance MonadTrans (FreeT f) where+    lift = FreeT . liftM Pure

@@ -1,10 +1,58 @@-{-|-    This library only provides a single data type: 'Pipe'.+module Control.Pipe (+    -- * Types+    -- $type +    -- * Composition+    -- $compose++    -- * Modularity+    -- $modular++    -- * Vertical Concatenation+    -- $vertical++    -- * Return Values+    -- $return++    -- * Termination+    -- $terminate++    -- * Resource Management+    -- $resource++    -- * Frames+    -- $frame++    -- * Frame Composition+    -- $framecompose++    -- * Frame vs. Ensure+    -- $frameensure++    -- * Folds+    -- $fold++    -- * Strictness+    -- $strict++    module Control.Pipe.Common,+    module Control.Pipe.Final+    ) where++import Control.Category+import Control.Monad.Trans.Class+import Control.Pipe.Common+import Control.Pipe.Final+import Data.Void++{- $type+    This library represents streaming computations using a single data type:+    'Pipe'.+     'Pipe' is a monad transformer that extends the base monad with the ability-    to 'await' input from or 'yield' output to other 'Pipe's.  'Pipe's resemble+    to 'await' input from or 'yield' output to other pipes.  Pipes resemble     enumeratees in other libraries because they receive an input stream and-    transform it into a new stream.+    transform it into a new output stream.      I'll introduce our first 'Pipe', which is a verbose version of the Prelude's     'take' function:@@ -16,113 +64,100 @@ >         yield x >     lift $ putStrLn "You shall not pass!" -    This 'Pipe' allows the first @n@ values it receives to pass through-    undisturbed, then it outputs a cute message and shuts down.  Shutdown is-    automatic when you reach the end of the monad.  You don't need to send a-    special signal to connected 'Pipe's to let them know you are done handling-    input or generating output.+    This pipe forwards the first @n@ values it receives undisturbed, then it+    outputs a cute message. -    Let's dissect the above 'Pipe''s type to learn a bit about how 'Pipe's work:+    Let's dissect the above pipe's type to learn a bit about how pipes work:  >      | Input Type | Output Type | Base monad | Return value > Pipe   a            a             IO           () -    So @take'@ 'await's input of type @a@ from upstream 'Pipe's and 'yield's-    output of type @a@ to downstream 'Pipe's.  @take'@ uses 'IO' as its base-    monad because it invokes the 'putStrLn' function.  If we remove the call to-    'putStrLn' the compiler infers the following type instead, which is-    polymorphic in the base monad:+    So @take'@ 'await's input values of type @a@ from upstream pipes and+    'yield's output values of type @a@ to downstream pipes.  @take'@ uses 'IO'+    as its base monad because it invokes the 'putStrLn' function.  If we were to+    remove the call to 'putStrLn', the compiler would infer the following type+    instead, which is polymorphic in the base monad:  > take' :: (Monad m) => Int -> Pipe a a m () -    'Pipe's use the base monad conservatively.  In fact, you can only invoke the-    base monad by using the 'lift' function from 'Pipe''s 'MonadTrans' instance.    If you never use 'lift', your 'Pipe' will translate into pure code.--    Now let's create a function that converts a list into a 'Pipe' by-    'yield'ing each element of the list:+    Now let's create a function that converts a list into a pipe by 'yield'ing+    each element of the list: -> fromList :: (Monad m) => [a] -> Pipe () a m ()+> fromList :: (Monad m) => [b] -> Pipe a b m () > fromList = mapM_ yield -    Note that @fromList xs@ has an input type of @()@.  Ideally, we would like-    to guarantee at a type level that @fromList@ will not call 'await', however-    this is impossible.  No choice of an input type forbids a 'Pipe' from-    calling 'await'.  However, we can set the input type to @()@ so that we can-    trivially satisfy any await request by feeding it a @()@.+    Note that @fromList xs@ is polymorphic in its input.  This is because it+    does not 'await' any input.  If we wanted, we could type-restrict it to: -    By setting a Pipe's input to @()@, we block it from receiving any (useful)-    input.  Such a pipe can only deliver output, which makes it suitable for the-    first stage in a 'Pipeline'.  I provide a type synonym for this common case:+> fromList :: (Monad m) => [b] -> Pipe () b m () -> type Producer b m r = Pipe () b m r+    There is no type that forbids a pipe from 'await'ing, but you can guarantee+    that if it does 'await', the request is trivially satisfiable by supplying+    it with @()@. -    'Producer's resemble enumerators in other libraries because they are a-    data source.  You can then use the 'Producer' type synonym to rewrite the-    type signature for @fromList@ as:+    A pipe that doesn't 'await' (any useful input) can serve as the first stage+    in a 'Pipeline'.  I provide a type synonym for this common case: -> fromList :: (Monad m) => [a] -> Producer a m ()+> type Producer b m r = Pipe () b m r -    Note that you don't have to block the input end with the @()@ type.  If-    you let the compiler infer the type, you would get:+    'Producer's resemble enumerators in other libraries because they function as+    data sources. -> fromList :: (Monad m) => [a] -> Pipe t a m ()+    You can then use the 'Producer' type synonym to rewrite the type signature+    for @fromList@ as: -    The compiler correctly infers that the input could be anything since it is-    never used.  This more polymorphic type signature is suitable, but you can-    set the input to @()@ to ensure that you do not inadvertently attach a-    useful pipe upstream.+> fromList :: (Monad m) => [b] -> Producer b m () -    Now let's create a 'Pipe' that prints every value delivered to it and never-    terminates:+    Now let's create a pipe that prints every value delivered to it: -> printer :: (Show a) => Pipe a Void IO r+> printer :: (Show b) => Pipe b c IO r > printer = forever $ do >     x <- await >     lift $ print x -    The 'Void' in @printer@'s type signature indicates that it never delivers-    output downstream, so it represents the final stage in a 'Pipeline'.  Again,+    Here, @printer@ is polymorphic in its output.  We could type-restrict it to+    guarantee it will never 'yield' by setting the output to 'Void', from+    @Data.Void@:++> printer :: (Show a) => Pipe b Void IO r++    A pipe that never yields can be the final stage in a 'Pipeline'.  Again,     I provide a type synonym for this common case: -> type Consumer a m r = Pipe a Void m r+> type Consumer b m r = Pipe b Void m r      So we could instead write @printer@'s type as: -> printer :: (Show a) => Consumer a IO r--    'Consumer's resemble iteratees in other libraries because they are a data-    sink.  'Consumer's never use 'yield' statements.+> printer :: (Show b) => Consumer b IO r -    What distinguishes 'Pipe's from every other iteratee implementation is that-    they form a 'Category'.  Because of this, you can literally compose 'Pipe's-    into 'Pipeline's.  'Pipe's actually possess two 'Category' instances:+    'Consumer's resemble iteratees in other libraries because they function as+    data sinks.+-} -> newtype Lazy   m r a b = Lazy   { unLazy   :: Pipe a b m r }-> newtype Strict m r a b = Strict { unStrict :: Pipe a b m r }-> instance Category (Lazy   m r) where ...-> instance Category (Strict m r) where ...+{- $compose+    What distinguishes pipes from every other iteratee implementation is that+    they form a true 'Category'.  Because of this, you can literally compose+    pipes into 'Pipeline's using ordinary composition: -    The first category composes pipes with 'Lazy' semantics and the second one-    composes 'Pipe's with 'Strict' semantics.  I'll begin by demonstrating-    'Lazy' semantics.+> newtype Lazy m r a b = Lazy { unLazy :: Pipe a b m r }+> instance Category (Lazy m r) where ... -    For example, you can compose the above 'Pipe's with:+    For example, you can compose the above pipes with:  > pipeline :: Pipe () Void IO () > pipeline = unLazy $ Lazy printer . Lazy (take' 3) . Lazy (fromList [1..]) -    The compiler deduces that the final 'Pipe' must be blocked at both ends,+    The compiler deduces that the final pipe must be blocked at both ends,     meaning it will never 'await' useful input and it will never 'yield' any     output.  This represents a self-contained 'Pipeline' and I provide a type     synonym for this common case:  > type Pipeline m r = Pipe () Void m r -    Also, I provide convenience operators for composing 'Pipe's without the-    burden of wrapping and unwrapping newtypes.  For example, to compose 'Pipe's-    using 'Lazy' semantics, just use the '<+<' operator:+    Also, I provide '<+<' as a convenience operator for composing pipes without+    the burden of wrapping and unwrapping newtypes: -> p1 <+< p2 = unLazy $ Lazy p1 <<< Lazy p2 -- (<<<) is the same as (.)+> p1 <+< p2 = unLazy $ Lazy p1 . Lazy p2      So you can rewrite @pipeline@ as: @@ -135,8 +170,10 @@  > runPipe :: (Monad m) => Pipeline m r -> m r -    'runPipe' only works on self-contained 'Pipeline's.  You don't need to worry    about explicitly giving it blocked 'Pipe's because self-contained pipelines-    will automatically have polymorphic input and output ends.+    'runPipe' only works on self-contained 'Pipeline's, but you don't need to+    worry about explicitly type-restricting any of your pipes.  Self-contained+    pipelines will automatically have polymorphic input and output ends and they+    will type-check when you provide them to 'runPipe'.      Let's try using 'runPipe': @@ -146,41 +183,103 @@ 3 You shall not pass! -    Fascinating!  Our 'Pipe' terminated even though @printer@ never terminates+    Fascinating!  Our pipe terminates even though @printer@ never terminates     and @fromList@ never terminates when given an infinite list.  To illustrate-    why our 'Pipe' terminated, let's outline the 'Pipe' flow control rules for-    'Lazy' composition:+    why our pipe terminates, let's outline the pipe flow control rules for+    composition: -    * Execution begins at the most downstream 'Pipe' (@printer@ in our example).+    * Pipes are lazy, so execution begins at the most downstream pipe+      (@printer@ in our example). -    * If a 'Pipe' 'await's input, it blocks and transfers control to the next-      'Pipe' upstream until that 'Pipe' 'yield's back a value.+    * Upstream pipes only run if input is requested from them and they only run+      as long as necessary to 'yield' back a value. -    * If a 'Pipe' 'yield's output, it restores control to the original-      downstream 'Pipe' that was 'await'ing its input and binds its result to-      the return value of the 'await' command.+    * If a pipe terminates, it terminates every other pipe composed with it. -    * If a 'Pipe' terminates, it terminates every other 'Pipe' composed with it.+    Another way to think of this is like a stack where each pipe is a frame on+    that stack: -    The last rule follows from laziness.  If a 'Pipe' terminates then every-    downstream 'Pipe' depending on its output cannot proceed, and upstream-    'Pipe's are never evaluated because the terminated 'Pipe' will not request-    values from them any longer.+    * If a pipe 'await's input, it blocks and pushes the next pipe upstream onto+      the stack until that pipe 'yield's back a value. +    * If a pipe 'yield's output, it pops itself off the stack and restores+      control to the original downstream pipe that was 'await'ing its input.+      This binds its result to the return value of the pending 'await' command.++    All of these flow control rules uniquely follow from the 'Category' laws.++    It might surprise you that termination brings down the entire pipeline until+    you realize that:++    * Downstream pipes depending on the terminated pipe cannot proceed++    * Upstream pipes won't be further evaluated because the terminated pipe will+      not request any further input from them+     So in our previous example, the 'Pipeline' terminated because @take' 3@     terminated and brought down the entire 'Pipeline' with it. -    'Pipe's promote loose coupling, allowing you to mix and match them-    transparently using composition.  For example, we can define a new-    'Producer' pipe that indefinitely prompts the user for integers:+    Actually, these flow control rules will mislead you into thinking that+    composed pipes behave as a collection of sub-pipes with some sort of message    passing architecture between them, but nothing could be further from the+    truth! When you compose pipes, they automatically fuse into a single pipe+    that corresponds to how you would have written the control flow by hand. +    For example, if you compose @printer@ and @fromList@:++> printer <+< fromList [1..]++    The result is indistinguishable from:++> lift (mapM_ print [1..])++    ... which is what we would have written by hand if we had not used pipes at+    all!  All 'runPipe' does is just remove the 'lift'!+-}++{- $modular+    Given a loop like:++> loop :: IO r+> loop = forever $ do+>     x <- dataSource+>     y <- processData x+>     dataSink y++    We could decompose it into three separate parts:++> stage1 :: Producer a IO r+> stage1 = forever $ do+>     x <- dataSource+>     yield x+>+> stage2 :: Pipe a b IO r+> stage2 = forever $ do+>     x <- await+>     y <- processData x+>     yield y+>+>+> stage3 :: Consumer b IO r+> stage3 = forever $ do+>     y <- await+>     dataSink+>+> stage3 <+< stage2 <+< stage1 == lift loop++    In other words, pipes let you decompose loops into modular components, which+    promotes loose coupling and allows you to freely mix and match those+    components.++    To demonstrate this, let's define a new data source that indefinitely+    prompts the user for integers:+ > prompt :: Producer Int IO a > prompt = forever $ do >     lift $ putStrLn "Enter a number: " >     n <- read <$> lift getLine >     yield n -    Now we can compose it with any of our previous 'Pipe's:+    Now we can use it as a drop-in replacement for @fromList@:  >>> runPipe $ printer <+< take' 3 <+< prompt Enter a number:@@ -194,7 +293,10 @@ 3 You shall not pass! -    You can easily \"vertically\" concatenate 'Pipe's, 'Producer's, and+-}++{- $vertical+    You can easily \"vertically\" concatenate pipes, 'Producer's, and     'Consumer's, all using simple monad sequencing: ('>>').  For example, here     is how you concatenate 'Producer's: @@ -221,7 +323,7 @@ You shall not pass!     ... but the above example is gratuitous because we could have just-   concatenated the intermediate @take'@ 'Pipe':+   concatenated the intermediate @take'@ pipe:  >>> runPipe $ printer <+< (take' 3 >> take' 4) <+< fromList [1..] 1@@ -234,8 +336,11 @@ 7 You shall not pass! -    Pipe composition imposes an important limitation: You can only compose-    'Pipe's that have the same return type.  For example, I could write the+-}++{- $return+    Pipe composition imposes an important requirement: You can only compose+    pipes that have the same return type.  For example, I could write the     following function:  > deliver :: (Monad m) => Int -> Consumer a m [a]@@ -246,13 +351,11 @@ >>> runPipe $ deliver 3 <+< fromList [1..10] -- wrong!      ... but this wouldn't type-check, because @fromList@ has a return type of-    @()@ and @deliver@ has a return type of @[Int]@.  'Lazy' composition-    requires that every 'Pipe' has a return value ready in case it terminates-    first.  This was not a conscious design choice, but rather a requirement of-    the 'Category' instance.+    @()@ and @deliver@ has a return type of @[Int]@.  Composition requires that+    every pipe has a return value ready in case it terminates first.      Fortunately, we don't have to rewrite the @fromList@ function because we can-    add a return value using vertical concatenation:+    just add a return value using vertical concatenation:  >>> runPipe $ deliver 3 <+< (fromList [1..10] >> return []) [1,2,3]@@ -264,24 +367,27 @@      This forces you to cover all code paths by thinking about what return value     you would provide if something were to go wrong.  For example, let's say I-    make a mistake and request more input than @fromList@ can deliver:+    were to make a mistake and request more input than @fromList@ can deliver:  >>> runPipe $ (Just <$> deliver 99) <+< (fromList [1..10] *> pure Nothing) Nothing -    The type system saved me by forcing me to handle all possible ways my-    program could terminate.+    The type system saved me by forcing me to cover all corner cases and handle+    every way my program could terminate.+-} -    Now what if you want to write a 'Pipe' that only reads from its input end+{- $terminate++    Now what if you wanted to write a pipe that only reads from its input end     (i.e. a 'Consumer') and returns a list of every value delivered to it when-    its input 'Pipe' terminates?+    its input pipe terminates?  > toList :: (Monad m) => Consumer a m [a] > toList = ??? -    You can't write such a 'Pipe' because if its input terminates then it brings-    down @toList@ with it!  This is a good thing because @toList@ as defined-    is not compositional.+    You can't write such a pipe because if its input terminates then it brings+    down @toList@ with it!  This is correct because @toList@ as defined is not+    compositional (yet!).      To see why, let's say you somehow got @toList@ to work and the following     imaginary code sample worked:@@ -289,16 +395,16 @@ >>> runPipe $ toList <+< (fromList [1..5] >> return []) [1,2,3,4,5] -    @toList@ is defined to return its value when the 'Pipe' immediately upstream+    @toList@ is defined to return its value when the pipe immediately upstream     (@fromList@ in this case) terminates.  This behavior immediately leads to a-    problem.  What if I were to insert an \"identity\" 'Pipe' between-    @toList@ and @fromList@:+    problem.  What if I were to insert an \"identity\" pipe between @toList@ and+    @fromList@:  > identity = forever $ await >>= yield-> -- This is how id in both categories is actually implemented+> -- This is how id is actually implemented! -    This 'Pipe' forwards every valued untouched, so we would expect it to not-    have any affect if we were to insert it in the middle:+    This pipe forwards every valued untouched, so we would expect it to not have+    any affect if we were to insert it in the middle:  >>> runPipe $ toList <+< identity <+< (fromList [1..5] >> return []) ??? -- Oops! Something other than [1,2,3,4,5], perhaps even non-termination@@ -307,172 +413,352 @@     @identity@ instead of @fromList@ and since @identity@ never terminates     @toList@ never terminates.  This is what I mean when I say that @toList@'s     specified behavior is non-compositional.  It only works if it is coupled-    directly to the desired 'Pipe' and breaks when you introduce intermediate+    directly to the desired pipe and breaks when you introduce intermediate     stages. -    This fortunate limitation was not an intentional design choice, but rather-    an inadvertent consequence of enforcing the 'Category' laws when I was-    implementing 'Pipe''s 'Category' instance.  Satisfying the 'Category' laws-    forces code to be compositional.+    This was not an intentional design choice, but rather a direct consequence+    of enforcing the 'Category' laws when I was implementing 'Pipe''s 'Category'+    instance.  Satisfying the 'Category' laws forces code to be compositional. -    Note that a terminated 'Pipe' only brings down 'Pipe's composed with it.  To+    Note that a terminated pipe only brings down pipes composed with it.  To     illustrate this, let's use the following example:  > p = do a <+< b >        c -    @a@, @b@, and @c@ are 'Pipe's, and @c@ shares the same input and output as-    @a <+< b@, otherwise we cannot combine them within the same monad.  In the-    above example, either @a@ or @b@ could terminate and bring down the other-    one since they are composed, but @c@ is guaranteed to continue after-    @a <+< b@ terminates because it is not composed with them.  Conceptually,-    we can think of this as @c@ automatically taking over the 'Pipe''s-    channeling responsibilities when @a <+< b@ can no longer continue.  There-    is no need to \"restart\" the input or output manually as in some other-    iteratee libraries.+    @a@, @b@, and @c@ are pipes, and @c@ shares the same input and output as+    the composite pipe @a <+< b@, otherwise we cannot combine them within the+    same monad.  In the above example, either @a@ or @b@ could terminate and+    bring down the other one since they are composed, but @c@ is guaranteed to+    continue after @a <+< b@ terminates because it is not composed with them.+    Conceptually, we can think of this as @c@ automatically taking over the+    pipe's channeling responsibilities when @a <+< b@ can no longer continue.+    There is no need to \"restart\" the input or output manually as in some+    other iteratee libraries.      The @pipes@ library, unlike other iteratee libraries, grounds its vertical-    and horizontal concatenation in mathematics by deriving horizontal-    concatenation ('.') from 'Category' instance and vertical concatenation+    and horizontal concatenation in category theory by deriving horizontal+    concatenation ('.') from its 'Category' instance and vertical concatenation     ('>>') from its 'Monad' instance.  This makes it easier to reason about-    'Pipe's because you can leverage your intuition about 'Category's and-    'Monad's to understand their behavior.  The only 'Pipe'-specific primitives-    are the 'await' and 'yield' functions.+    pipes because you can leverage your intuition about 'Category's and 'Monad's+    to understand their behavior.  The only 'Pipe'-specific primitives are+    'await' and 'yield'.+-} -    'Lazy' composition has one important defect: resource finalization.  Let's-    say we have the file \"test.txt\" with the following contents:+{- $resource+    Here's another problem with 'Pipe' composition: resource finalization.+    Let's say we have the file \"test.txt\" with the following contents: -> This is a test.-> Don't panic!-> Calm down, please!+> Line 1+> Line 2+> Line 3 -  .. and we wish to lazily read a line at a time from it:+  .. and we wish to lazily read one line at a time from it:  > readFile' :: Handle -> Producer Text IO () > readFile' h = do >     eof <- lift $ hIsEOF h->     if eof->       then return ()->       else do->           s <- lift $ hGetLine h->           yield s->           readFile' h+>     when (not eof) $ do+>         s <- lift $ hGetLine h+>         yield s+>         readFile' h -    We can use our 'Monad' and 'Category' instances to generate a-    resource-efficient version that only reads as many lines as we request:+    We could then try to be slick and write a lazy version that only reads as+    many lines as we request: -> read' n = do->         lift $ putStrLn "Opening file ..."->         h <- lift $ openFile "test.txt"->         take' n <+< readFile' h->         lift $ putStrLn "Closing file ..."->         lift $ hClose h+> read' :: FilePath -> Producer Text IO ()+> read' = do+>     lift $ putStrLn "Opening file ..."+>     h <- lift $ openFile file ReadMode+>     readFile' h+>     lift $ putStrLn "Closing file ..."+>     lift $ hClose h      Now compose! ->>> runPipe $ printer <+< read' 2-Opening file ...-"This is a test."-"Don't panic!"-Closing file ...-->>> runPipe $ printer <+< read' 99+>>> runPipe $ printer <+< read' "test.xt" Opening file ...-"This is a test."-"Don't panic!"-"Calm down, please!"+"Line 1"+"Line 2"+"Line 3" Closing file ... -    In the first example, @take' n <+< readFile' h@ terminates because-    @take'@ only requested 2 lines.  In the second example, it terminates-    because @readFile'@ ran out of input.  However, in both cases the 'Pipe'-    never reads more lines than we request frees \"test.txt\" immediately when-    it was no longer needed.--    Even more importantly, the @file@ is never opened if we replace @printer@-    with a 'Pipe' that never demands input:+    So far, so good.  Equally important, the file is never opened if we replace+    @printer@ with a pipe that never demands input: ->>> runPipe $ (lift $ putStrLn "I don't need input") <+< read' 2+>>> runPipe $ (lift $ putStrLn "I don't need input") <+< read' "test.txt" I don't need input      There is still one problem, though. What if we wrote: ->>> runPipe $ printer <+< take' 1 <+< read' 3+>>> runPipe $ printer <+< take' 2 <+< read' "test.txt" Opening file ...-"This is a test."+"Line 1"+"Line 2"+You shall not pass! -    Oh no!  Our 'Pipe' didn't properly close our file!  @take' 1@ terminated-    before @read' 3@, preventing @read' 3@ from properly closing \"test.txt\".-    We can force the @read' 3@ 'Pipe' to close the file by using the 'discard'-    function:+    Oh no!  While it was lazy and only read two lines from the file, it was also+    too lazy to properly close our file!  @take' 2@ terminated before @read'@,+    preventing @read'@ from properly closing \"test.txt\".  This is why 'Pipe'+    composition fails to guarantee deterministic finalization.+-} -> discard :: (Monad m) => Pipe a b m r-> discard = forever await+{- $frame+    So how could we implement finalization, then?  The answer is to build a+    higher-order type on top of 'Pipe' and define a new composition that permits+    prompt, deterministic finalization. -    If we append 'discard' to @take' 1@, we will drive @read' 3@ to completion-    by continuing to pull values from it:+    To do this, we import "Control.Pipe.Final", which exports the 'Frame' type,+    analogous to the 'Pipe' type, except more powerful.  To demonstrate it in+    action, let's rewrite our @take'@ function to be a 'Frame' instead. ->>> runPipe $ printer <+< (take' 1 >> discard) <+< read' 3+> take' :: Int -> Frame a a IO ()+> take' n+>   | n < 1 = Frame $ close $ lift $ putStrLn "You shall not pass!"+>   | otherwise = Frame $ do+>         replicateM_ (n - 1) $ do+>             x <- awaitF+>             yieldF x+>         x <- awaitF+>         close $ do+>             lift $ putStrLn "You shall not pass!"+>             yieldF x++    The type signature looks the same, except 'Pipe' has been replaced with+    'Frame'.  Also, now we have 'awaitF' instead of 'await' and 'yieldF' instead+    of 'yield'.  However, you'll notice two new things: 'close' and 'Frame'.++    'close' signals when we no longer need input from upstream.  If you try to+    request input other than @()@ after the 'close', you will get a type error.+    Whenever you 'close' a frame, composition finalizes every upstream frame and+    removes them from the pipeline.  The type error reflects the fact that if+    you 'awaitF' past that point there is no longer anything upstream to request+    input from.++    'Frame' is a newtype constructor that I use to give clearer type errors and+    abstract away the underlying implementation.  The reason is that if you were+    to expand out the full type that 'Frame' wraps you would get:++> Frame a b m r ~ Pipe (Maybe a) (m (), b) m (Pipe (Maybe ()) (m (), b) m r)+> -- Yuck!++    Really, the only reason the type is that complicated is because I avoid+    using language extensions to implement 'Frame's, otherwise it would look+    more like:++> Pipe (Maybe a) (m (), b) m r++    ... which isn't so bad.  In fact, it's not hard to understand what that+    type is doing.  The 'Maybe' is used to supply a 'Nothing' to 'await's when+    upstream terminates before 'yield'ing a value.  The @m ()@ is the most+    recent finalizer which is yielded alongside every value so that downstream+    pipes can finalize you if they terminate before requesting another value.+    The finalization machinery uses these tricks behind the scene to guarantee+    that your finalizers get called.  I provide a type synonym for this:++> type Ensure a b m r = Pipe (Maybe a) (m (), b) m r++    In other words, an 'Ensure'd pipe can intercept upstream termination and+    register finalizers for downstream to call in the event of premature+    termination.  A good way to think about the distinction between 'Ensure'+    and 'Frame' is that 'Ensure' is the 'Monad' and 'Frame' is the 'Category',+    unlike 'Pipe', which is both at the same time.++    Using this type synonym, we can rewrite the type that 'Frame' wraps:++> Frame a b m r ~ Ensure a b m (Ensure () b m r)++    The first half of the type is the part of the pipe before you call 'close',+    the second half of the type is the part of the pipe after you call 'close'.+    Notice how the second half has a blocked input end.++    However, I haven't yet shown you how to register finalizers.  That's easy,+    though, since you just use 'catchP' or 'finallyP', which are identical to+    their exception-handling counterparts, except they catch 'Frame'+    terminations in either direction.  Let's rewrite our @read'@ function using+    finalizers:++> readFile' :: Handle -> Ensure () Text IO ()+> readFile' h = do+>     eof <- lift $ hIsEOF h+>     when (not eof) $ do+>         s <- lift $ hGetLine h+>         yieldF s+>         readFile' h+>+> read' :: FilePath -> Frame () Text IO ()+> read' = Frame $ close $ do+>     lift $ putStrLn "Opening file ..."+>     h <- lift $ openFile file ReadMode+>     finallyP (putStrLn "Closing file ..." >> hClose h)+>              (readFile' h)++    Notice how @read'@ closes its input end immediately because it never+    requires input.  Also, the 'finallyP' ensures that the finalizer is called+    both if @read'@ terminates normally or is interrupted by another 'Frame'+    terminating first.++    Now, all we need to do is rewrite @printer@ to be a 'Frame':++> printer :: (Show b) => Frame b Void IO r+> printer = Frame $ forever $ do+>     x <- awaitF+>     lift $ print x++    This time we don't even need a 'close' statement because @printer@ never+    stops needing input.  Any non-terminating 'Frame' with a polymorphic return+    type can skip calling 'close' altogether, and it will type-check.+-}++{- $framecompose++    Just like with 'Pipe's, we can compose 'Frame's, except now we use ('<-<'):++> stack :: Frame Void () IO ()+> stack = printer <-< take' 1 <-< read' "test.txt"++    I call a complete set of 'Frame's a 'Stack', to reflect the fact that+    'Frame' composition uses the exact same tricks stack-based programming uses+    to guarantee deterministic finalization.  When a 'Frame' terminates it+    finalizes upstream 'Frame's as if they were a heap and it propagates an+    exceptional value ('Nothing' in this case) for downstream 'Frame's to+    intercept.  I provide a type synonym to reflect this:++> type Stack m r = Frame Void () IO r++    So we can rewrite the type of @stack@ to be:++> stack :: Stack IO ()++    To run a 'Stack', we use 'runFrame', which is the 'Frame'-based analog to+    'runPipe':++>>> runFrame stack Opening file ...-"This is a test."+"Line 1" Closing file ...+"Line 2"+You shall not pass! -   This allows @read' 3@ to complete so it can properly finalize itself.  I-   include a convenience operator for this behavior:+    Not only did it correctly finalize the file this time, but it did so as+    promptly as possible!  I programmed @take'@ so that it knew it would not+    need @read'@ any longer before it 'yield'ed the second value, so it+    finalized the file before 'yield'ing the second value for @printer@.+    @take'@ did this without knowing anything about the 'Frame' upstream of it.+    One of the big advantages of 'Frame's is that you can reason about the+    finalization behavior of each 'Frame' in complete isolation from other+    'Frame's, allowing you to completely decouple their finalization+    behavior.+-} -> p1 <-< p2 = (p1 >> discard) <+< p2+{- $frameensure+    Unfortunately, in the absence of extensions I have to split the 'Monad' and+    'Category' into two separate types.  'Ensure' is the 'Monad', 'Frame' is the+    'Category'. -   Interestingly, '<-<' forms a 'Category', too, namely the 'Strict' category.-   This 'Category' draws down all input by default (as the name suggests).  I-   call it the 'Strict' 'Category' because 'discard' resembles 'seq'.  'discard'-   drives its input to continue until one upstream 'Pipe' terminates and this-   behavior resembles forcing its input to weak head normal form.  If every-   'Pipe' drives its input to weak head normal form, you get 'Strict'-   composition.+    However, you can achieve the best of both worlds by programming all your+    pipes in the 'Ensure' monad, and then only adding 'close' at the last minute    when you are building your 'Stack'.  For example, if we wanted to read from+    multiple files, it would be much better to just remove the 'close' function+    from the @read'@ implementation, so it operates in the 'Ensure' monad: -   'Strict' composition works terribly on infinite inputs, as you would expect:+> read' :: FilePath -> Ensure () Text IO () ->>> runPipe $ printer <-< take' 3 <-< prompt-Enter a number:-1<Enter>-1-Enter a number:-2<Enter>-2-Enter a number:-3<Enter>-3-You shall not pass!-Enter a number:-4<Enter>-5<Enter>-6<Enter>-... <Prompts for input indefinitely and discards it>+    Then use 'close' only after we've already concatenated our files: -    'Strict' composition works best for inputs that are finite and require-    finalization.  'Lazy' composition works best for inputs that are infinite-    (and obviously an infinite input never needs finalization).+> files :: Frame () Text IO ()+> files = close $ do+>     read' "test.txt"+>     read' "dictionary.txt"+>     read' "poem.txt" -    However, unlike conventional strictness in Haskell, 'Strict' 'Pipe's do not-    load the entire input in memory.  They still stream and immediately handle-    input just as 'Lazy' 'Pipe's.  The only difference is that they guarantee-    input finalization (for better or for worse).  Also, for 'Strict'-    'Pipeline's the return value must come from the most upstream 'Pipe'.  Other-    than that, 'Strict' composition will have the exact same sequence of monadic-    effects, resource usage, memory profile, and performance.+    This is a more idiomatic 'Frame' programming style that lets you take+    advantage of both the 'Monad' and 'Category' instances. -    Like Haskell, you can mix 'Lazy' and 'Strict' composition.  Keep in mind,-    though, that while '<+<' is associative with itself and '<-<' is associative-    with itself, mixtures of them are not associative.  Alternatively, you-    could stick to 'Lazy' composition and sprinkle 'discard' statements-    wherever you desire strictness.  It's up to you.  However, when designing-    library functions, make them 'Lazy' by default, since you can make 'Lazy'-    code 'Strict' by adding a 'discard' statement, but you can't make 'Strict'-    code 'Lazy'.+    The beauty of compositional finalization is we can decompose complicated+    problems into smaller ones.  Imagine that we have a resource that needs a+    fine-grained finalization behavior like in our @take'@ function which does+    a cute little optimization to finalize early.  We can always decompose our+    frame into one that does the straight-forward thing (like @read'@) and then+    just compose it with @take'@ to get the cute optimization for free.  In this+    way we've decomposed the problem into two separate problems: generating the+    resource and doing the cute optimization. -} -module Control.Pipe (module Control.Pipe.Common) where+{- $fold+    'Frame's can actually do much more than manage finalization!  Using+    'Frame's, we can now correctly implement folds like @toList@ in a way that+    is truly compositional: -import Control.Category-import Control.Monad.Trans-import Control.Pipe.Common+> toList :: (Monad m) => Frame a Void m [a]+> toList = Frame go where+>     go = do+>         x <- await+>         case x of+>             Nothing -> close $ pure []+>             Just a  -> fmap (fmap (a:)) go+>             -- the extra fmap is an unfortunate extra detail++    This time I used an ordinary 'await', instead of 'awaitF', so I could access+    the underlying 'Maybe' values that these 'Frame's are passing around.+    Similarly, you could use 'yield' instead of 'yieldF' if you wanted to+    manually manage the finalizers passed downstream at each 'yield' statement+    instead of using the 'catchP' or 'finallyP' convenience functions.  Using+    these advanced features does not break any of the 'Category' laws.  I could+    expose every single internal of the library and you would not be able to+    break the 'Category' laws because the 'Frame's generated are still+    indistinguishable at the value level and fuse into the hand-written+    implementation.  The compositionality of 'Frame's is just as strong as the+    compositionality of 'Pipe's.++    Now let's use our @toList@ function:++>>> runFrame $ (Just <$> toList) <-< (Nothing <$ fromList [1..3])+Just [1,2,3]++    I still had to provide a return value for @fromList@ ('Nothing' in this+    case), because when @fromList@ terminates, it cannot guarantee that its+    return value will come from itself or from @toList@.  When @toList@ receives+    a 'Nothing' from upstream, it can choose to terminate and over-ride the+    return value from upstream or 'await' again and defer to the upstream return+    value (@fromList@ in this case).  It doesn't even have to immediately+    decide.  It could just 'yield' more values downstream and forget it had even+    received a 'Nothing' and if downstream terminates then composition will+    still ensure that everything \"just works\" the way you would expect and no+    finalizers are missed or duplicated.++    Composition handles every single corner case of finalization.  This directly+    follows from enforcing the 'Category' laws, because categories have no+    corners!+-}++{- $strict+    We can go a step further and modify @toList@ into something even cooler:++> strict :: (Monad m) => Frame a a m ()+> strict = Frame $ do+>     xs <- go+>     close $ mapM_ yieldF xs+>   where+>     go = do+>         x <- await+>         case x of+>             Nothing -> pure []+>             Just a  -> fmap (a:) go++    As the name suggests, @strict@ is strict in its input.  We can use @strict@+    to load the entire resource into memory immediately, allowing us to finalize+    it early.  Let's use this to create a strict version of our file reader:++>>> runFrame $ printer <-< take' 2 <-< strict <-< read' "test.txt"+Opening file ...+Closing file ...+"Line 1"+"Line 2"+You shall not pass!++    Now we have a way to seamlessly switch from laziness to strictness all+    implemented entirely within Haskell without the use of artificial 'seq'+    annotations.+-}++

@@ -1,188 +1,125 @@+{-# LANGUAGE Rank2Types #-}+ module Control.Pipe.Common (+    -- * Introduction+    -- $summary+     -- * Types-    Pipe(..),+    -- $types+    PipeF(..),+    Pipe,     Producer,     Consumer,     Pipeline,     -- * Create Pipes-    {-|-        'yield' and 'await' are the only two primitives you need to create-        'Pipe's.  Because 'Pipe' is a monad, you can assemble them using-        ordinary @do@ notation.  Since 'Pipe' is also a monad transformer, you-        can use 'lift' to invoke the base monad.  For example:--> check :: Pipe a a IO r-> check = forever $ do->     x <- await->     lift $ putStrLn $ "Can " ++ (show x) ++ " pass?"->     ok <- lift $ read <$> getLine->     when ok (yield x)-    -}+    -- $create     await,     yield,     pipe,-    discard,     -- * Compose Pipes-    {-|-        There are two possible category implementations for 'Pipe':--        ['Lazy' composition]--            * Use as little input as possible--            * Ideal for infinite input streams that never need finalization--        ['Strict' composition]--            * Use as much input as possible--            * Ideal for finite input streams that need finalization--        Both category implementations enforce the category laws:--        * Composition is associative (within each instance).  This is not-          merely associativity of monadic effects, but rather true-          associativity.  The result of composition produces identical-          composite 'Pipe's regardless of how you group composition.--        * 'id' is the identity 'Pipe'.  Composing a 'Pipe' with 'id' returns the-          original pipe.--        Both categories prioritize downstream effects over upstream effects.-    -}+    -- $newtype     Lazy(..),-    Strict(..),-    -- ** Compose Pipes-    {-|-        I provide convenience functions for composition that take care of-        newtype wrapping and unwrapping.  For example:--> p1 <+< p2 = unLazy $ Lazy p1 <<< Lazy p2--        '<+<' and '<-<' correspond to '<<<' from @Control.Category@--        '>+>' and '>+>' correspond to '>>>' from @Control.Category@--        '<+<' and '>+>' use 'Lazy' composition (Mnemonic: + for optimistic-        evaluation)--        '<-<' and '>->' use 'Strict' composition (Mnemonic: - for pessimistic-        evaluation) --        However, the above operators won't work with 'id' because they work on-        'Pipe's whereas 'id' is a newtype on a 'Pipe'.  However, both 'Category'-        instances share the same 'id' implementation:--> instance Category (Lazy m r) where->     id = Lazy $ pipe id->     ....-> instance Category (Strict m r) where->     id = Strict $ pipe id->     ...--        So if you need an identity 'Pipe' that works with the above convenience-        operators, you can use 'idP' which is just @pipe id@.-    -}+    -- $convenience     (<+<),     (>+>),-    (<-<),-    (>->),     idP,+    -- $category     -- * Run Pipes+    -- $runpipe     runPipe     ) where  import Control.Applicative import Control.Category-import Control.Monad-import Control.Monad.Trans-import Data.Void+import Control.Monad (forever)+import Control.Monad.Trans.Class (lift)+import Control.Monad.Trans.Free+import Data.Void (Void) import Prelude hiding ((.), id) -{-|-    The base type for pipes--    [@a@] The type of input received from upstream pipes--    [@b@] The type of output delivered to downstream pipes+{- $summary+    I completely expose the 'Pipe' data type and internals in order to encourage+    people to write their own 'Pipe' functions.  This does not compromise the+    correctness or safety of the library at all and you can feel free to use the+    constructors directly without violating any laws or invariants. -    [@m@] The base monad+    I promote using the 'Monad' and 'Category' instances to build and compose+    pipes, but this does not mean that they are the only option.  In fact, any+    combinator provided by other iteratee libraries can be recreated for pipes,+    too.  However, this core library does not provide many of the functions+    found in other libraries in order to encourage people to find principled and+    theoretically grounded solutions rather than devise ad-hoc solutions+    characteristic of other iteratee implementations.+-} -    [@r@] The type of the monad's final result+{- $types+    The 'Pipe' type is strongly inspired by Mario Blazevic's @Coroutine@ type in+    his concurrency article from Issue 19 of The Monad Reader and is formulated+    in the exact same way. -    The Pipe type is partly inspired by Mario Blazevic's Coroutine in his-    concurrency article from Issue 19 of The Monad Reader and partly inspired by-    the Trace data type from \"A Language Based Approach to Unifying Events and-    Threads\".+    His @Coroutine@ type is actually a free monad transformer (i.e. 'FreeT')+    and his @InOrOut@ functor corresponds to 'PipeF'. -}-data Pipe a b m r =-    Pure r                     -- pure = Pure-  | M     (m   (Pipe a b m r)) -- Monad-  | Await (a -> Pipe a b m r ) -- ((->) a) Functor-  | Yield (b,   Pipe a b m r ) -- ((,)  b) Functor-{- I could have factored Pipe as:+data PipeF a b x = Await (a -> x) | Yield (b, x) -data Computation f r = Pure r | F (f (Computation f r))-data PipeF a b m r = Await (a -> r) | Yield (b, r) | M (m r)-newtype Pipe a b m r = P { unP :: Computation (PipeF a b m) r }+-- I could use the "DerivingFunctor" extension, but I want to remain portable+instance Functor (PipeF a b) where+    fmap f (Await a) = Await $ fmap f a+    fmap f (Yield y) = Yield $ fmap f y -   This makes the Functor, Applicative, and Monad instances much simpler at the-   expense of making the Category instances *much* harder to follow because of-   excessive newtype and constructor wrapping/unwrapping.  Since the Category-   instance is the meat of the library, I opted to in-line PipeF into-   computation to make it much simpler.  It's a shame, because the Computation-   type is very useful in its own right and I will probably create a separate-   library around it. -}+{-|+    The base type for pipes -instance (Monad m) => Functor (Pipe a b m) where-    fmap f c = case c of-        Pure r   -> Pure $ f r-        M mc     -> M     $ liftM (fmap f) mc-        Await fc -> Await $ fmap  (fmap f) fc-        Yield fc -> Yield $ fmap  (fmap f) fc+    * @a@ - The type of input received from upstream pipes -instance (Monad m) => Applicative (Pipe a b m) where-    pure = Pure-    f <*> x = case f of-        Pure r   -> fmap r x-        M mc     -> M     $ liftM (<*> x) mc-        Await fc -> Await $ fmap  (<*> x) fc-        Yield fc -> Yield $ fmap  (<*> x) fc+    * @b@ - The type of output delivered to downstream pipes -instance (Monad m) => Monad (Pipe a b m) where-    return = pure-    m >>= f = case m of-        Pure r   -> f r-        M mc     -> M     $ liftM (>>= f) mc-        Await fc -> Await $ fmap  (>>= f) fc-        Yield fc -> Yield $ fmap  (>>= f) fc+    * @m@ - The base monad -instance MonadTrans (Pipe a b) where lift = M . liftM pure+    * @r@ - The type of the return value+-}+type Pipe a b = FreeT (PipeF a b) --- | A pipe that can only produce values-type Producer b m r = Pipe () b m r+-- | A pipe that produces values+type Producer b = Pipe () b --- | A pipe that can only consume values-type Consumer a m r = Pipe a Void m r+-- | A pipe that consumes values+type Consumer b = Pipe b Void  -- | A self-contained pipeline that is ready to be run-type Pipeline m r = Pipe () Void m r+type Pipeline = Pipe () Void +{- $create+    'yield' and 'await' are the only two primitives you need to create pipes.+    Since 'Pipe a b m' is a monad, you can assemble 'yield' and 'await'+    statements using ordinary @do@ notation.  Since 'Pipe a b' is also a monad+    transformer, you can use 'lift' to invoke the base monad.  For example, you+    could write a pipe stage that requests permission before forwarding any+    output:++> check :: (Show a) => Pipe a a IO r+> check = forever $ do+>     x <- await+>     lift $ putStrLn $ "Can '" ++ (show x) ++ "' pass?"+>     ok <- read <$> lift getLine+>     when ok (yield x)+-}+ {-|-    Wait for input from upstream within the 'Pipe' monad:+    Wait for input from upstream. -    'await' blocks until input is ready.+    'await' blocks until input is available from upstream. -}-await :: Pipe a b m a-await = Await Pure +await :: (Monad m) => Pipe a b m a+await = wrap $ Await return  {-|-    Pass output downstream within the 'Pipe' monad:+    Deliver output downstream. -    'yield' blocks until the output has been received.+    'yield' restores control back upstream and binds the result to 'await'. -}-yield :: b -> Pipe a b m ()-yield x = Yield (x, Pure ())+yield :: (Monad m) => b -> Pipe a b m ()+yield b = wrap $ Yield (b, return ())  {-|     Convert a pure function into a pipe@@ -194,57 +131,153 @@ pipe :: (Monad m) => (a -> b) -> Pipe a b m r pipe f = forever $ await >>= yield . f --- | The 'discard' pipe silently discards all input fed to it.-discard :: (Monad m) => Pipe a b m r-discard = forever await+{- $newtype+    Pipes form a 'Category', but if you want to define a proper 'Category'+    instance you have to wrap the 'Pipe' type using a newtype in order to+    rearrange the type variables:+-}+newtype Lazy m r a b = Lazy { unLazy :: Pipe a b m r} -newtype Lazy   m r a b = Lazy   { unLazy   :: Pipe a b m r}-newtype Strict m r a b = Strict { unStrict :: Pipe a b m r}+instance (Monad m) => Category (Lazy m r) where+    id = Lazy idP+    Lazy p1 . Lazy p2 = Lazy $ p1 <+< p2 +{- $convenience+    This means that if you want to compose pipes using ('.') from the 'Category'+    type class, you end up with a newtype mess: @unLazy (Lazy p1 . Lazy p2)@.++    You can avoid this by using convenient operators that do this newtype+    wrapping and unwrapping for you:++> p1 <+< p2 = unLazy $ Lazy p1 . Lazy p2+>+> idP = unLazy id+-}++-- | Corresponds to ('<<<')/('.') from @Control.Category@+(<+<) :: (Monad m) => Pipe b c m r -> Pipe a b m r -> Pipe a c m r+p1 <+< p2 = FreeT $ do+    x1 <- runFreeT p1+    let p1' = FreeT $ return x1+    runFreeT $ case x1 of+        Pure r         -> pure r+        Wrap (Yield y) -> wrap $ Yield $ fmap (<+< p2) y+        Wrap (Await f1) -> FreeT $ do+            x2 <- runFreeT p2+            runFreeT $ case x2 of+                Pure r              -> pure r+                Wrap (Yield (x, p)) -> f1 x <+< p+                Wrap (Await f2    ) -> wrap $ Await $ fmap (p1' <+<) f2++-- | Corresponds to ('>>>') from @Control.Category@+(>+>) :: (Monad m) => Pipe a b m r -> Pipe b c m r -> Pipe a c m r+(>+>) = flip (<+<)++{- These associativities might help performance since pipe evaluation is+   downstream-biased.  I set them to the same priority as (.). -}+infixr 9 <+<+infixl 9 >+>++-- | Corresponds to 'id' from @Control.Category@ idP :: (Monad m) => Pipe a a m r idP = pipe id -(<+<), (<-<) :: (Monad m) => Pipe b c m r -> Pipe a b m r -> Pipe a c m r-p1 <+< p2 = unLazy   (Lazy   p1 <<< Lazy   p2)-p1 <-< p2 = unStrict (Strict p1 <<< Strict p2)+{- $category+    You can compose two pipes using @p1 <+< p2@, which binds the output of @p2@+    to the input of @p1@.  For example: -(>+>), (>->) :: (Monad m) => Pipe a b m r -> Pipe b c m r -> Pipe a c m r-p1 >+> p2 = unLazy   (Lazy   p1 >>> Lazy   p2)-p1 >-> p2 = unStrict (Strict p1 >>> Strict p2)+> (await >>= lift . print) <+< yield 0+> = lift (print 0) --- These associativities help composition detect termination quickly-infixr 9 <+<, >->-infixl 9 >+>, <-<+    'idP' is the identity pipe which forwards all output untouched: -{- If you assume id = forever $ await >>= yield, then the below are the only two-   Category instances possible.  I couldn't find any other useful definition of-   id, but perhaps I'm not being creative enough. -}-instance (Monad m) => Category (Lazy m r) where-    id = Lazy $ pipe id-    Lazy p1' . Lazy p2' = Lazy $ case (p1', p2') of-        (Yield (x1, p1), p2            ) -> yield x1 >>         p1 <+< p2-        (M m1          , p2            ) -> lift m1  >>= \p1 -> p1 <+< p2-        (Pure r1       , _             ) -> Pure r1-        (Await f1      , Yield (x2, p2)) -> f1 x2 <+< p2-        (p1            , Await f2      ) -> await    >>= \x  -> p1 <+< f2 x-        (p1            , M m2          ) -> lift m2  >>= \p2 -> p1 <+< p2-        (_             , Pure r2       ) -> Pure r2+> idP = forever $ do+>   x <- await+>   yield x -instance (Monad m) => Category (Strict m r) where-    id = Strict $ pipe id-    Strict p1 . Strict p2 = Strict $ (p1 >> discard) <+< p2+    Pipes are lazy, meaning that control begins at the downstream pipe and+    control only transfers upstream when the downstream pipe 'await's input from+    upstream.  If a pipe never 'await's input, then pipes upstream of it will+    never run. +    Upstream pipes relinquish control back downstream whenever they 'yield' an+    output value.  This binds the 'yield'ed value to the return value of the+    downstream 'await'.  The upstream pipe does not regain control unless the+    downstream pipe requests input again.++    When a pipe terminates, it also terminates any pipes composed with it.++    The 'Category' instance obeys the 'Category' laws.  In other words:++    * Composition is truly associative.  The result of composition produces the+      exact same composite 'Pipe' regardless of how you group composition:++> (p1 <+< p2) <+< p3 = p1 <+< (p2 <+< p3)++    * 'idP' is a true identity pipe.  Composing a pipe with 'idP' returns the+      exact same original pipe:++> p <+< idP = p+> idP <+< p = p++    The 'Category' laws are \"correct by construction\", meaning that you cannot+    break them despite the library's internals being fully exposed.  The above+    equalities are true using the strongest denotational semantics possible in+    Haskell, namely that both sides of the equals sign correspond to the exact+    same value in Haskell, constructor-for-constructor, value-for-value.  You+    cannot create a function that can distinguish the results.++    Actually, all other class instances for 'Pipe's provide the same strong+    guarantees for their corresponding laws.  I only emphasize the guarantee for+    the 'Category' instance because it is one of the most distinguishing+    features of this library.+-}++{- $runpipe+    Note that you can also unwrap a 'Pipe' a single step at a time using+    'runFreeT' (since 'Pipe' is just a type synonym for a free monad+    transformer).  This will take you to the next /external/ 'await' or 'yield'+    statement.++    This means that a closed 'Pipeline' will unwrap to a single step, in which+    case you would have been better served by 'runPipe'.  This directly follows+    from the 'Category' laws, which guarantee that you cannot resolve a+    composite pipe into its component pipes.  When you compose two pipes, the+    internal await and yield statements fuse and completely disappear.++    'runFreeT' is ideal for more advanced users who wish to write their own+    'Pipe' functions while waiting for me to find more elegant solutions.+-} {-|-    Run the 'Pipe' monad transformer, converting it back into the base monad+    Run the 'Pipe' monad transformer, converting it back into the base monad. -    'runPipe' will not work on a pipe that has loose input or output ends.  If-    your pipe is still generating unhandled output, handle it.  I choose not to-    automatically 'discard' output for you, because that is only one of many-    ways to deal with unhandled output.+    'runPipe' imposes two conditions:++    * The pipe's input, if any, is trivially satisfiable (i.e. @()@)++    * The pipe does not 'yield' any output++    The latter restriction makes 'runPipe' less polymorphic than it could be,+    and I settled on the restriction for three reasons:++    * It prevents against accidental data loss.++    * It prevents wastefully draining a scarce resource by gratuitously+      demanding values from it.++    * It encourages an idiomatic pipe programming style where input is consumed+      in a structured way using a 'Consumer'.++    If you believe that discarding output is the appropriate behavior, you can+    specify this by explicitly feeding your output to a pipe that gratuitously+    discards it:++> runPipe $ forever await <+< p -} runPipe :: (Monad m) => Pipeline m r -> m r-runPipe p' = case p' of-    Pure r          -> return r-    M mp            -> mp >>= runPipe-    Await f         -> runPipe $ f ()-    Yield (_, p) -> runPipe p+runPipe p = do+    e <- runFreeT p+    case e of+        Pure   r       -> return r+        Wrap (Await f) -> runPipe $ f ()+        Wrap (Yield y) -> runPipe $ snd y

@@ -0,0 +1,424 @@+module Control.Pipe.Final (+    -- * Introduction+    -- $intro++    -- * Types+    Prompt,+    Ensure,+    Frame(..),+    Stack,+    -- * Create Frames+    -- $create+    yieldF,+    awaitF,+    -- * Prompt Finalization+    -- $prompt+    close,+    bindClosed,+    reopen,+    -- * Ensure Finalization+    -- $ensure+    catchP,+    finallyP,+    -- * Compose Frames+    -- $compose+    (<-<),+    (>->),+    idF,+    FrameC(..),+    -- * Run Frames+    -- $run+    runFrame+    ) where++import Control.Applicative+import Control.Category+import Control.Monad+import Control.Monad.Trans.Class+import Control.Monad.Trans.Free+import Control.Pipe.Common+import Data.Void+import Prelude hiding ((.), id)++{- $intro+    A 'Frame' is a higher-order type built on top of 'Pipe'.  It enables a+    richer composition with the ability to finalize resources in a manner that+    is:++    * Prompt: You can close resources when you no longer need input from them++    * Deterministic: Composition finalizes every 'Frame' when one terminates++    'Frame's differ from 'Pipe's in that they do not form monads, but instead+    form parametrized monads.  Unfortunately, parametrized monads are not+    mainstream in Haskell and require a ton of extensions along with a modified+    Prelude in order to recover @do@ notation, so this first release of the+    'Frame' implementation essentially \"in-lines\" the parametrized monad by+    splitting it into two monads.  Future releases will split off a version that+    takes advantage of parametrized monads for a much simpler underlying type+    and a significantly cleaner implementation.++    Ordinary users should start at the section \"Create Frames\", but if you+    encounter weird type errors and want to understand them, then consult the+    \"Types\" section.+-}++{-|+    An illustrative type synonym that demonstrates how 'Prompt' finalization+    works++    This type simulates a parametrized monad by breaking it up into two monads+    where the first monad returns the second one.  The first monad permits any+    pipe code and the second monad only permits pipe code that doesn't need+    input.++    For example if @p = Pipe@, the first monad becomes an ordinary 'Pipe' and+    the second monad becomes a 'Producer':++> Prompt Pipe a b m r = Pipe a b m (Pipe () b m r)++    The pipe does not require input by the time it reaches the second block,+    meaning that the finalization machinery can safely finalize upstream+    resources the moment.  The earlier you use 'close' the input end,+    the more promptly you release upstream resources.++    The finalization machinery also finalizes downstream pipes when the+    second monad terminates.  I use this trick to ensure a strict ordering of+    finalizers from upstream to downstream.++    I don't actually use the 'Prompt' type synonym, since that would require+    newtyping everything, but I will reference it in documentation to clarify+    type signatures.+-}+type Prompt p a b m r = p a b m (p () b m r)++{-|+    A pipe type that 'Ensure's deterministic finalization++    The finalization machinery uses the input and output ends in different ways+    to finalize the pipe when another pipe terminates first.++    If an upstream pipe terminates first, the current pipe will receive a+    'Nothing' once.  This allows it to finalize itself and if it terminates then+    its return value takes precedence over upstream's return value.  However, if+    it 'await's again, it defers to upstream's return value and never regains+    control.  You do not need to \"rethrow\" the 'Nothing' (nor can you):+    composition takes care of this for you.++    On the output end, the pipe must supply its most up-to-date finalizer+    alongside every value it 'yield's downstream.  This finalizer is guaranteed+    to be called if downstream terminates first.  You do not need to relay+    upstream finalizers alongside the pipe's own finalizer (nor can you):+    composition takes care of this for you.++    The combination of these two tricks allows a bidirectional guarantee of+    deterministic finalization that satisfies the 'Category' laws.+-}+type Ensure a b m r = Pipe (Maybe a) (m (), b) m r++{-|+    A pipe type that combines 'Prompt' and 'Ensure' to enable both prompt and+    deterministic finalization.++    The name connotes a stack frame, since finalized pipes can be thought of as+    forming the 'Category' of stack frames, where upstream finalization is+    equivalent to finalizing the heap, and downstream finalization is equivalent+    to throwing an exception up the stack.++    The type is equivalent to:++> type Frame a b m r = Prompt Ensure a b m r+-}+newtype Frame a b m r = Frame { unFrame :: Ensure a b m (Ensure () b  m r) }++instance (Monad m) => Functor (Frame a b m) where+    fmap f (Frame p) = Frame $ fmap (fmap f) p++-- | A 'Stack' is a 'Frame' that doesn't need input and doesn't generate output+type Stack = Frame () Void++{- $create+    The first step to convert 'Pipe' code to 'Frame' code is to replace all+    'yield's with 'yieldF's and all 'await's with 'awaitF's.++> contrived = do   -->  contrived = do+>     x1 <- await  -->      x1 <- awaitF+>     yield x1     -->      yieldF x1+>     x2 <- await  -->      x2 <- awaitF+>     yield x2     -->      yieldF x2+-}++-- | Like 'yield', but also yields an empty finalizer alongside the value+yieldF :: (Monad m) => b -> Ensure a b m ()+yieldF x = yield (unit, x)++-- | Like 'await', but ignores all 'Nothing's and just awaits again+awaitF :: (Monad m) => Ensure a b m a+awaitF = await >>= maybe awaitF return++{- $prompt+    The second step to convert 'Pipe' code to 'Frame' code is to mark the point+    where your 'Pipe' no longer 'await's by wrapping it in the 'close' function+    and then wrapping the 'Pipe' in a 'Frame' newtype:++> contrived :: (Monad m) => Frame a a m ()+> contrived = Frame $ do+>     x1 <- awaitF+>     yieldF x1+>     x2 <- awaitF+>     close $ yieldF x2++    If a non-terminating pipe demands input indefinitely, there is no need to+    'close' it.  It will type-check if the return value is polymorphic as a +    result of non-termination.+-}++{-|+    Use this to mark when a 'Frame' no longer requires input.  The earlier the+    better!+-}+close :: (Monad m) => Ensure () b m r -> Ensure a b m (Ensure () b m r)+close = pure++{-|+    Use this to bind to the 'close'd half of the 'Frame' if you want to continue+    where it left off but you still don't require input.++    This function would not be necessary if 'Prompt' were implemented as a+    parametrized monad, so if it seems ugly, that's because it is.+-}+bindClosed :: (Monad m) =>+    Frame a b m r1 -> (r1 -> Ensure () b m r2) -> Frame a b m r2+bindClosed (Frame p) f = Frame $ fmap (>>= f) p++{-|+    Use this to 'reopen' a 'Frame' if you change your mind and decide you want+    to continue to 'await' input after all.++    This postpones finalization of upstream until you 'close' the input end+    again.+-}+reopen :: (Monad m) => Frame a b m r -> Ensure a b m r+reopen (Frame p) = join $ fmap (<+< (forever $ yield $ Just ())) p++{- $ensure+    The third (optional) step to convert 'Pipe' code to 'Frame' code is to use+    'catchP' or 'finallyP' to register finalizers for blocks of code.++> contrived :: Frame a a IO ()+> contrived = Frame $ do+>     catchP (putStrLn "Stage 1 interrupted") $ do+>         x1 <- awaitF+>         catchP (putStrLn "Stage 1(b) interrupted") $ yieldF x1+>     catchP (putStrLn "Stage 2 interrupted") $ do+>         x2 <- awaitF+>         close $ yieldF x2+-}++{-|+    @catchP m p@ registers @m@ to be called only if another composed+    pipe terminates before @p@ is done.+-}+catchP :: (Monad m) => m () -> Ensure a b m r -> Ensure a b m r+catchP m p = FreeT $ do+    x <- runFreeT p+    runFreeT $ case x of+        Pure r -> pure r+        Wrap (Yield ((m', b), p')) -> wrap $ Yield ((m' >> m, b), catchP m p')+        Wrap (Await f) -> wrap $ Await $ \e -> case e of+            Nothing -> lift m >> catchP m (f e)+            Just _  ->           catchP m (f e)+{- catchP is equivalent to:++awaitF' m = await >>= maybe (lift m >> awaitF' m) return++yieldF' m x = yield (m, x)++catchP m p =  reopen $+     (forever $ awaitF >>= yieldF' m)+ <-< Frame (fmap close p)+ <-< (forever $ awaitF' m >>= yieldF) -}++{-|+    'finallyP' is like 'catchP' except that it also calls the finalizer if @p@+    completes normally.+-}+finallyP :: (Monad m) => m () -> Ensure a b m r -> Ensure a b m r+finallyP m p = do+    r <- catchP m p+    lift m+    return r++(<~<) :: (Monad m)+ => Pipe b c m (Pipe x c m r)+ -> Pipe a b m (Pipe x b m r)+ -> Pipe a c m (Pipe x c m r)+p1 <~< p2 = FreeT $ do+    x1 <- runFreeT p1+    runFreeT $ case x1 of+        Pure p1'       -> pure p1'+        Wrap (Yield y) -> wrap $ Yield $ fmap (<~< p2) y+        Wrap (Await f1) -> FreeT $ do+            let p1 = FreeT $ return x1+            x2 <- runFreeT p2+            runFreeT $ case x2 of+                Pure p2'              -> pure $ p1 <~| p2'+                Wrap (Yield (b2, p2')) -> f1 b2 <~< p2'+                Wrap (Await f2      ) -> wrap $ Await $ fmap (p1 <~<) f2++(<~|) :: (Monad m)+ => Pipe b c m (Pipe x c m r)+ -> Pipe x b m r+ -> Pipe x c m r+p1 <~| p2 = FreeT $ do+    x1 <- runFreeT p1+    runFreeT $ case x1 of+        Pure p1'        -> p1'+        Wrap (Yield y) -> wrap $ Yield $ fmap (<~| p2) y+        Wrap (Await f) -> FreeT $ do+            let p1 = FreeT $ return x1+            x2 <- runFreeT p2+            runFreeT $ case x2 of+                Pure r                -> pure r+                Wrap (Yield (b2, p2')) -> f b2 <~| p2'+                Wrap (Await f2      ) -> wrap $ Await $ fmap (p1 <~|) f2++unit :: (Monad m) => m ()+unit = return ()++mult :: (Monad m)+ => m ()+ -> Pipe (Maybe        b ) (m (), c) m (Pipe x (m (), c) m r)+ -> Pipe (Maybe (m (), b)) (m (), c) m (Pipe x (m (), c) m r)+mult m p = FreeT $ do+    x <- runFreeT p+    runFreeT $ case x of+        Pure p' -> pure $ lift m >> p'+        Wrap (Yield ((m', c), p')) -> wrap $ Yield ((m >> m', c), mult m p')+        Wrap (Await f) -> wrap $ Await $ \e -> case e of+            Nothing      -> mult unit (f   Nothing)+            Just (m', b) -> mult m'   (f $ Just b )++comult :: (Monad m)+ => Pipe (Maybe a)        b  m (Pipe x        b  m r)+ -> Pipe (Maybe a) (Maybe b) m (Pipe x (Maybe b) m r)+comult p = FreeT $ do+    x <- runFreeT p+    runFreeT $ case x of+        Pure p' -> pure $ warn p'+        Wrap (Yield (b, p')) -> wrap $ Yield (Just b, comult p')+        Wrap (Await f) -> wrap $ Await $ \e -> case e of+            Nothing -> schedule $ comult (f e)+            Just _  ->            comult (f e)++warn :: (Monad m)+ => Pipe x        b  m r+ -> Pipe x (Maybe b) m r+warn p = do+    r <- pipe Just <+< p+    yield Nothing+    return r++schedule :: (Monad m)+ => Pipe (Maybe a) (Maybe b) m (Pipe x (Maybe b) m r)+ -> Pipe (Maybe a) (Maybe b) m (Pipe x (Maybe b) m r)+schedule p = FreeT $ do+    x <- runFreeT p+    runFreeT $ case x of+        Pure p' -> pure p'+        Wrap (Await f) -> wrap $ Yield (Nothing, wrap $ Await f)+        Wrap (Yield y) -> wrap $ Yield $ fmap schedule y++{- $compose+    The fourth step to convert 'Pipe' code to 'Frame' code is to use ('<-<') to+    compose 'Frame's instead of ('<+<').++> printer  :: Frame a Void IO r+> fromList :: (Monad m) => [a] -> Frame () a m ()+>+> p :: Stack IO ()+> p = printer <-< contrived <-< fromList [1..]++    Similarly, 'idF' replaces 'idP'.++    When a 'Frame' terminates, the 'FrameC' category strictly orders the+    finalizers from upstream to downstream.  Specifically:++    * When any 'Frame' 'close's its input end, it finalizes all 'Frame's+      upstream of it.  These finalizers are ordered from upstream to downstream.++    * A 'Frame' is responsible for finalizing its own resources under ordinary+      operation (either manually, or using 'finallyP').++    * When a 'Frame' terminates, everything downstream of it is finalized.+      These finalizers are ordered from upstream to downstream.++    The 'Category' instance for 'FrameC' provides the same strong guarantees as+    the 'Lazy' category.  This confers many practical advantages:++    * Finalizers are never duplicated or dropped in corner cases.++    * The grouping of composition will never affect the ordering or behavior of+      finalizers.++    * Finalization does not grow more complex the more 'Frame's you add in your+      'Stack'.++    * You can reason about the finalization behavior of each 'Frame'+      independently of other 'Frame's it is composed with.+-}++-- | Corresponds to 'id' from @Control.Category@+idF :: (Monad m) => Frame a a m r+idF = Frame $ forever $ awaitF >>= yieldF++-- | Corresponds to ('<<<')/('.') from @Control.Category@+(<-<) :: (Monad m) => Frame b c m r -> Frame a b m r -> Frame a c m r+(Frame p1) <-< (Frame p2) = Frame $ mult unit p1 <~< comult p2++-- | Corresponds to ('>>>') from @Control.Category@+(>->) :: (Monad m) => Frame a b m r -> Frame b c m r -> Frame a c m r+(>->) = flip (<-<)++newtype FrameC m r a b = FrameC { unFrameC :: Frame a b m r }++instance (Monad m) => Category (FrameC m r) where+    (FrameC p1) . (FrameC p2) = FrameC $ p1 <-< p2+    id = FrameC idF++{- $run+    The final step to convert 'Pipe' code to 'Frame' code is to replace+    'runPipe' with 'runFrame'.++> printer  :: Frame a Void IO r+> take     :: (Monad m) => Int -> Frame a a m ()+> fromList :: (Monad m) => [a] -> Frame () a m ()++>>> runFrame $ printer <-< contrived <-< fromList [1..]+1+2++>>> runFrame $ printer <-< contrived <-< fromList [1]+1+Stage 2 interrupted++>>> runFrame $ printer <-< take 1 <-< contrived <-< fromList [1..]+Stage 1(b) interrupted+Stage 1 interrupted+1++For the last example, remember that 'take' is written to 'close' its input end+before yielding its final value, which is why the finalizers run before+@printer@ receives the 1.++-}++-- | Convert a 'Frame' back to the base monad.+runFrame :: (Monad m) => Stack m r -> m r+runFrame p = go (reopen p) where+    go p = do+        x <- runFreeT p+        case x of+            Pure r -> return r+            Wrap (Await f) -> go $ f (Just ())+            Wrap (Yield y) -> go $ snd y

@@ -1,5 +1,5 @@ Name: pipes-Version: 1.0.2+Version: 2.0.0 Cabal-Version: >=1.10.1 Build-Type: Simple License: BSD3@@ -12,15 +12,15 @@ Synopsis: Compositional pipelines Description:   \"Iteratees done right\".  This library implements-  iteratees\/enumerators\/enumeratees simply and elegantly, but uses different+  iteratees\/enumerators\/enumeratees simply and elegantly, using different   naming conventions.   .   Advantages over traditional iteratee implementations:   .   * /Simpler semantics/: There is only one data type ('Pipe'), two primitives     ('await' and 'yield'), and only one way to compose 'Pipe's ('.').  In fact,-    this library introduces no new operators, using only its 'Monad' and-    'Category' instances to implement all behavior.+    this library implements its entire behavior using its 'Monad' and 'Category'+    instances and enforces their laws strictly!   .   * /Clearer naming conventions/: Enumeratees are called 'Pipe's, Enumerators     are 'Producer's, and Iteratees are 'Consumer's.  'Producer's and 'Consumer's@@ -28,8 +28,6 @@     closed.   .   * /Pipes are Categories/: You compose them using ordinary composition.-    There are actually two 'Category' instances: one for 'Lazy' composition and-    one for 'Strict' composition.  Both instances satisfy the 'Category' laws.   .   * /Intuitive/: Pipe composition is easier to reason about because it is a true     'Category'.  Composition works seamlessly and you don't have to worry about@@ -41,18 +39,8 @@     Vertical Concatenation always works the way you expect, picking up where the     previous 'Pipe' left off.   .-  * /Symmetric implementation/: Most iteratee libraries are either-    enumerator-driven or iteratee-driven.  'Pipe's are implemented-    symmetrically, which is why they can be composed with either 'Lazy'-    ('Consumer'-driven) or 'Strict' ('Producer'-driven) semantics.-  .-  Check out "Control.Pipe" for a copious introduction (in the spirit of the-  @iterIO@ library) and "Control.Pipe.Common" for the actual implementation.-  .-  This library does not yet provide convenience 'Pipe's for common operations,-  but they are forthcoming.  However, there are several examples in the-  documentation to get you started and I encourage you to write your own to see-  how easy they are to write.+  Check out "Control.Pipe" for a copious tutorial and "Control.Pipe.Common" for+  the actual implementation. Category: Control, Enumerator Tested-With: GHC ==7.0.3 Source-Repository head@@ -60,7 +48,11 @@     Location: https://github.com/Gabriel439/Haskell-Pipes-Library  Library-    Build-Depends: base >= 4 && < 5, mtl, void-    Exposed-Modules: Control.Pipe, Control.Pipe.Common+    Build-Depends: base >= 4 && < 5, transformers, void+    Exposed-Modules:+        Control.Pipe,+        Control.Pipe.Common,+        Control.Pipe.Final,+        Control.Monad.Trans.Free     GHC-Options: -O2     Default-Language: Haskell2010