streaming 0.1.0.17 → 0.1.0.18
raw patch · 3 files changed
+271/−59 lines, 3 filesdep +bytestring
Dependencies added: bytestring
Files
- Streaming.hs +9/−17
- Streaming/Prelude.hs +19/−11
- streaming.cabal +243/−31
Streaming.hs view
@@ -74,37 +74,29 @@ The 'Stream' data type is equivalent to @FreeT@ and can represent any effectful succession of steps, where the form of the steps or 'commands' is - specified by the first (functor) parameter. The (hidden) implementation is+ specified by the first (functor) parameter. The present module exports+ functions that pertain to that general case. So for example, if the+ functor is -> data Stream f m r = Step !(f (Stream f m r)) | Delay (m (Stream f m r)) | Return r+ > data Split r = Split r r + The @Stream Split m r@ will the type of binary trees with @r@ at the leaves+ and in which each episode of branching results from an @m@-effect. + ++ In the simplest case, the base functor is @ (,) a @. Here the news or /command/ at each step is an /individual element of type/ @ a @, i.e. the command is a @yield@ statement. The associated @Streaming@ 'Streaming.Prelude' uses the left-strict pair @Of a b@ in place of the Haskell pair @(a,b)@ - In it, various operations are defined for fundamental streaming types like -> Stream (Of a) m r -- a generator or producer (in the pipes sense) -> -- compare [a], or rather ([a],r) -> Stream (Of a) m (Stream (Of a) m r) -- the effectful splitting of a producer-> -- compare ([a],[a]) or rather ([a],([a],r))-> Stream (Stream (Of a) m) m r -- segmentation of a producer-> -- cp. [[a]], or rather ([a],([a],([a],(...,r)))) - and so on. But of course any functor can be used, and this is part of - the point of this prelude - as we already see from - the type of the segmented stream, @Stream (Stream (Of a) m) m r@- and operations like e.g. > chunksOf :: Monad m => Int -> Stream f m r -> Stream (Stream f m) m r > mapsM Streaming.Prelude.length' :: Stream (Stream (Of a) m) r -> Stream (Of Int) m r - To avoid breaking reasoning principles, the constructors - should not be used directly. A pattern-match should go by way of 'inspect' - \- or, in the producer case, 'Streaming.Prelude.next'. These mirror- the type of @runFreeT@. The constructors are exported by the 'Internal' module. -} {-| Map a stream to its church encoding; compare @Data.List.foldr@
Streaming/Prelude.hs view
@@ -19,19 +19,23 @@ Here are some correspondences between the types employed here and elsewhere: -> streaming | pipes | conduit | io-streams-> -----------------------------------------------------------------------------------------------------------> Stream (Of a) m () | Producer a m () | Source m a | InputStream a-> | ListT m a | ConduitM () o m () | Generator r ()-> -----------------------------------------------------------------------------------------------------------> Stream (Of a) m r | Producer a m r | ConduitM () o m r | Generator a r-> -----------------------------------------------------------------------------------------------------------> Stream (Of a) m (Stream (Of a) m r) | Producer a m (Producer a m r) | -> -----------------------------------------------------------------------------------------------------------+> streaming | pipes | conduit | io-streams+> -------------------------------------------------------------------------------------------------------------------+> Stream (Of a) m () | Producer a m () | Source m a | InputStream a+> | ListT m a | ConduitM () o m () | Generator r ()+> -------------------------------------------------------------------------------------------------------------------+> Stream (Of a) m r | Producer a m r | ConduitM () o m r | Generator a r+> -------------------------------------------------------------------------------------------------------------------+> Stream (Of a) m (Stream (Of a) m r) | Producer a m (Producer a m r) | +> -------------------------------------------------------------------------------------------------------------------- > Stream (Stream (Of a) m) r | FreeT (Producer a m) m r |-+> --------------------------------------------------------------------------------------------------------------------+> --------------------------------------------------------------------------------------------------------------------+> ByteString m () | Producer ByteString m () | Source m ByteString | InputStream ByteString+> --------------------------------------------------------------------------------------------------------------------+> -}-{-# LANGUAGE RankNTypes, BangPatterns, DeriveDataTypeable,+{-# LANGUAGE RankNTypes, BangPatterns, DeriveDataTypeable, TypeFamilies, DeriveFoldable, DeriveFunctor, DeriveTraversable #-} module Streaming.Prelude (@@ -174,6 +178,7 @@ import Foreign.C.Error (Errno(Errno), ePIPE) import Control.Exception (throwIO, try) import Data.Monoid (Monoid (..))+import Data.String (IsString (..)) -- | A left-strict pair; the base functor for streams of individual elements. data Of a b = !a :> b@@ -212,6 +217,9 @@ {-#INLINE (>>) #-} m :> x >>= f = let m' :> y = f x in mappend m m' :> y {-#INLINE (>>=) #-}++instance (r ~ (), Monad m, f ~ Of Char) => IsString (Stream f m r) where+ fromString = each {-| Note that 'lazily', 'strictly', 'fst'', and 'mapOf' are all so-called /natural transformations/ on the primitive @Of a@ functor If we write
streaming.cabal view
@@ -1,10 +1,10 @@ name: streaming-version: 0.1.0.17+version: 0.1.0.18 cabal-version: >=1.10 build-type: Simple-synopsis: a free monad transformer optimized for streaming applications+synopsis: a free monad transformer optimized for streaming applications with an elementary streaming prelude -description: __The free stream on a streamable functor__+description: * __The free stream on a streamable functor__ . @Stream@ can be used wherever <https://hackage.haskell.org/package/free-4.12.1/docs/Control-Monad-Trans-Free.html FreeT> @@ -13,26 +13,92 @@ written in terms of `Stream`. @FreeT f m r@ / @Stream f m r@ is of course extremely general, and many functor-general combinators are exported by the general module @Streaming@. + .+ * __The general idea of streaming__+ .+ As soon as you consider the idea of an effectful stream of any kind+ whatsoever, for example, a stream of bytes from a handle, however+ constituted, you will inevitably be forced to contemplate the+ idea of a streaming /succession/ of /such streams/. Thus, for example,+ however you imagine your bytes streaming from a handle,+ you will want to consider a /succession/ of /such streams/ divided+ on newlines. Similarly, suppose you have the idea the unfolding of+ some sort of stream from a Haskell value, a seed - a file name, + as it might be. And suppose you /also/ have some idea of a stream of + such Haskell values - maybe a stream of file names coming from + something like @du@, subjected+ to some filter. Then you will also have the idea of a streaming + /succession/ of /such unfoldings/ linked together end to end in + accordance with the initial succession of seed values.+ .+ Call those 5 sentences the ABCs. If you understood the ABCs+ you have a total comprehension of @Stream f m r@. + .+ * @Stream@ itself expresses what the word "succession" meant in the ABCs+ .+ * The general parameter @f@ expresses what was meant by "such streams"+ .+ * @m@ expresses the relevant form of "effect".+ .+ General combinators for working with this idea of succession irrespective+ of the form of succession are+ contained in the module @Stream@. They can be used, or example,+ to organize a succession of io-streams @Generator@s or pipes + @Producer@s or the effectful+ bytestreams of the <https://hackage.haskell.org/package/streaming-bytestring + streaming-bytestring> library, + or whatever stream-form you can express in a Haskell functor. . - @Streaming.Prelude@ is focused on elementary /streaming/ applications.- Here the free iteration of the \'base\' functors - (readings of the @f@ in @Stream f m r@) express - forms of effectful sequence or succession. Some of types in question- appear in the streaming IO libraries under titles like+ * __A freely generated stream of /connected individual Haskell values/ is Producer, Generator or Source__ .- > pipes: Producer a m r, Producer a m (Producer a m r), FreeT (Producer a m) m r- > io-streams: InputStream a, Generator a r- > conduit: Source m a, ConduitM () o m r+ But, of course, as soon as you grasp the general form of /succession/, + you are already in possession of the most basic concrete form: a simple + /succession of individual Haskell values/ one after another. + This is just @Stream ((,) a) m r@, or as we write it here,+ @Stream (Of a) m r@, strictifying the left element of the pair.+ The pairing just links the present element with the rest of the+ stream. The primitive @yield@ statement just expresses the+ pairing of the yielded item with the rest of the stream; or rather+ it is itself the trivial singleton stream.+ @Streaming.Prelude@ is focused on the manipulation of this + all-important stream-form, which appears in the streaming + IO libraries under titles like: .- @Streaming.Prelude@ closely follows @Pipes.Prelude@, but cleverly /omits the pipes/:+ > io-streams: Generator a r+ > pipes: Producer a m r+ > conduit: ConduitM () o m r+ > streaming: Stream (Of a) m r .+ The only difference is that in @streaming@ the simple Generator or Producer+ concept is formulated explicitly in terms of the + /general/ concept of successive connection. But this is+ a concept you need and already possess anyway, as your comprehension of+ the four sentences above showed. + .+ The special case of a + /stream of individual Haskell values/ + that simply /comes to an end without a special result/ is variously+ expressed thus:+ .+ > io-streams: InputStream a + > pipes: Producer a m ()+ > conduit: Source m a+ > machines: SourceT m a (= forall k. MachineT m k a)+ > streaming: Stream (Of a) m ()+ .+ * __@Streaming.Prelude@__+ .+ @Streaming.Prelude@ closely follows @Pipes.Prelude@. + But since it restricts itself to use + only of the general idea of streaming, it cleverly /omits the pipes/:+ . > ghci> S.stdoutLn $ S.take 2 S.stdinLn > let's<Enter> > let's > stream<Enter> > stream .- And here we do a little /connect and resume/, as the streaming-io experts call it:+ Here's a little /connect and resume/, as the streaming-io experts call it: . > ghci> rest <- S.print $ S.splitAt 3 $ S.each [1..10] > 1@@ -44,16 +110,95 @@ Somehow, we didn't even need a four-character operator for that, nor advice about best practices! - just ordinary Haskell common sense. .- __Didn't I hear that free monads are horrible?__+ * __Mother's @Prelude@ vs. @Streaming.Prelude@__ .- If @Stream f m r@ is instantiated to @Stream f Identity m r@ then we have- the standard /free monad construction/. This is subject to certain familiar+ The effort of+ @Streaming.Prelude@ is to leverage the intuition the user has acquired+ in mastering @Prelude@ and @Data.List@ and to elevate her understanding+ into a general comprehension of effectful streaming transformations. + Unsurprisingly, it takes longer to type out+ the signatures. It cannot be emphasized enough, thought, that + /the transpositions are totally mechanical/:+ .+ > Data.List.Split.chunksOf :: Int -> [a] -> [[a]]+ > Streaming.chunksOf :: Int -> Stream f m r -> Stream (Stream f m) m r+ .+ > Prelude.splitAt :: Int -> [a] -> ([a],[a])+ > Streaming.splitAt :: Int -> Stream f m r -> Stream f m (Stream f m r)+ .+ These concepts are "functor general", in the jargon used in the documentation,+ and are thus exported by the main @Streaming@ module. + Something like @break@ requires us to inspect individual values for+ their properties, so it is found in the @Streaming.Prelude@+ .+ > Prelude.break :: (a -> Bool) -> [a] -> ([a],[a])+ > Streaming.Prelude.break :: (a -> Bool) -> Stream (Of a) m r -> Stream (Of a) m (Stream (Of a) m r)+ .+ It is easy to prove that /resistance to these types is resistance to effectful streaming itself/.+ I will labor this point a bit more below, but you can also find it developed, with+ greater skill, in the documentation for the pipes libraries.+ .+ * __How come there's not one of those fancy "ListT done right" implementations in here?__+ .+ The use of the final return value appears to be a complication, but in fact+ it is essentially contained in the idea of effectful streaming. This is why+ this library does not export a /ListT done right/, which would be simple enough -+ following @pipes@, as usual:+ .+ > newtype ListT m a = ListT (Stream (Of a) m ())+ .+ The associated monad instance would wrap+ .+ > yield :: (Monad m) => a -> Stream (Of a) m ()+ > for :: (Monad m, Functor f) => Stream (Of a) m r -> (a -> Stream f m ()) -> Stream f m r+ .+ To see the trouble, consider + <http://hackage.haskell.org/package/list-t-0.4.5.1/docs/ListT.html#v:splitAt this signature> + for splitting a ListT very much done right. Here's what becomes of + <http://hackage.haskell.org/package/list-t-0.4.5.1/docs/src/ListT.html#slice chunksOf>.+ As long as we are trapped in ListT, however much rightly implements, these operation can't be made to stream; + something like a list must be accumulated. Similarly, try to imagine+ adding a @splitAt@ or @lines@ function to + <https://hackage.haskell.org/package/list-t-text-0.2.0.2/docs/ListT-Text.html this API>. + It would accumulate strict text forever, just as + <https://hackage.haskell.org/package/io-streams-1.3.2.0/docs/System-IO-Streams-ByteString.html#v:lines this does> + and <https://hackage.haskell.org/package/pipes-bytestring-2.1.1/docs/src/Pipes-ByteString.html#lines this doesn't> and + <https://hackage.haskell.org/package/streaming-bytestring-0.1.0.6/docs/Data-ByteString-Streaming-Char8.html#v:lines this doesn't>+ The difference is simply that the latter libraries operate with the general concept of streaming, and+ the whole implementation is governed by it. + The attractions of the various "@ListT@ done right" implementations are superficial; the concept+ belongs to logic programming, not stream programming.+ .+ Note similarly that you can write a certain kind of + <http://hackage.haskell.org/package/machines-0.5.1/docs/Data-Machine-Process.html#v:taking take> + and + <http://hackage.haskell.org/package/machines-0.5.1/docs/Data-Machine-Process.html#v:dropping drop> + with the+ @machines@ library - as you can even with a "@ListT@ done right". But I + wish you luck writing @splitAt@! Similarly you can write a+ <http://hackage.haskell.org/package/machines-io-0.2.0.6/docs/System-IO-Machine.html getContents>; + but I wish you luck dividing the resulting bytestream on its lines. + This is - as usual! - because the library was not written with the general concept of+ effectful succession or streaming in view. Materials for+ sinking some elements of a stream in one way, and others in other ways - copying+ each line to a different file, as it might be, but without accumulation + - are documented within. So are are myriad other elementary operations of streaming io.+ .+ * __Didn't I hear that free monads are a real efficiency dog? Isn't Oleg working on this important problem?__+ .+ We noted above that if we instantiate @Stream f m r@ to @Stream ((,) a) m r@ + or the like, we get the standard idea of a producer or generator. + If it is instantiated to @Stream f Identity m r@ then we have+ the standard /free monad construction/. This construction is subject to + certain familiar objections from an efficiency perspective; efforts have been made to substitute exotic cps-ed implementations and so forth. + It is an interesting topic. .- In fact, the standard fast talk about /retraversing binds/ and /quadratic explosions/ and- /costly appends/, and so on become transparent nonsense with @Stream f m r@ - in its streaming use. The insight needed to see this is basically nil: Where @m@ is read as+ But in fact, the standard alarmist talk about /retraversing binds/ and /quadratic explosions/ and+ /costly appends/, and so on become __transparent__ nonsense with @Stream f m r@ + in its streaming use. The conceptual power needed to see this is + basically nil: Where @m@ is read as @IO@, or some transformed @IO@, then the dreaded /retraversing of the binds/ in a stream expression would involve repeating all the past actions. Don't worry, to get e.g. the second chunk of bytes from a handle, you won't need to start over and get the first@@ -73,7 +218,8 @@ . > accumulate :: Monad m, Functor f => Stream f m r -> m (Stream f Identity r) .- or @reifyBinds@, as you might call it. Small experience will+ or @reifyBindsRetraversingWherePossible@ or @_ICan'tTakeThisStreamingAnymore@, + as you might call it. /The types themselves/ teach the user how to avoid or control the sort of accumulation characteristic of @sequence@ in its various guises e.g. @mapM f = sequence . map f@ and @traverse f = sequence . fmap f@ and @replicateM n = sequence . replicate n@. @@ -83,18 +229,81 @@ > Streaming.Prelude.replicateM :: Int -> m a -> Stream (Of a) m () . If you want to tempt fate and replicate the irrationality of @Control.Monad.replicateM@, - then sure, you can write the hermaphroditic, chimerical+ then sure, you can define the hermaphroditic chimera . > accumulate . Streaming.Prelude.replicateM :: Int -> m a -> m (Stream (Of a) Identity ()) .- but once you know how to operate with a stream directly you will see less and less point- in what is called /extracting the (structured) value from IO/. With @sequence@ and @traverse@,- we accumulate a structure holding pure values from a structure holding monadic - values. Why bother when you have intrinsically monadic structures? @Stream f m r@ - gives you an immense body of such structures and a simple discipline for working with them.+ which is what we find in our diseased base libraries. + But once you know how to operate with a stream directly you will see less and less point+ in what is called /extracting the (structured) value from IO/. The+ distinction between .- __Interoperation with the streaming-io libraries__+ > "getContents" :: String .+ and+ .+ > getContents :: IO String + .+ but, omitting consideration of eof, we might define @getContents@ thus + .+ > getContents = sequence $ repeat getChar+ .+ There it is again! The very devil! By contrast there is no distinction + between+ .+ > "getContents" :: Stream (Of Char) m ()+ .+ and+ .+ > getContents :: MonadIO m => Stream (Of Char) m ()+ .+ They unify just fine. That is, if I make the type synonym+ .+ > type String m r = Stream (Of Char) m r+ .+ I get, for example:+ .+ > "getLine" :: String m ()+ > getLine :: String IO ()+ > "getLine" >> getLine :: String IO ()+ > splitAt 20 $ "getLine" >> getLine :: String IO (String IO ())+ > length $ "getLine" >> getLine :: IO Int+ .+ and can dispense with half the advice they will give you on @#haskell@. + It is only a slight exaggeration to say that a stream should never be "extracted from IO". + .+ With @sequence@ and @traverse@,+ we accumulate a pure succession of pure values from a pure + succession of monadic values. + Why bother if you have intrinsically monadic conception of + succession or traversal? @Stream f m r@ + gives you an immense body of such structures and a + simple discipline for working with them. Spinkle @id@ freely+ though your program if you get homesick.+ .+ Much of the discussion of the free monad concept is associated + with the "algebraic effects" program. A leading advertisement for this approach+ is that we can toss generators into the soup without missing a beat.+ See for example this + <http://hackage.haskell.org/package/extensible-effects-1.11.0.0/docs/Control-Eff-Coroutine.html#v:yield yield>.+ concept+ .+ > yield :: (Typeable a, Member (Yield a) r) => a -> Eff r ()+ .+ With it I can over course write, e.g.+ .+ > each :: (Traversable t, Typeable a, Member (Yield a) r) => t a -> Eff r ()+ > each = mapM_ yield+ .+ Once I have one of these "coroutine effects" on my hands,+ the fact that I am writing Haskell, not e.g. Python, will leave me with + little trouble splitting it at the 20th element, and reserving the rest for later use.+ I invite you, though, to divide such a "coroutine effect" on its lines or + into chunks of 500. There must be /some/ sense in which these effects are "extensible".+ But it seems not as far as the ABCs.+ .+ * __Interoperation with the streaming-io libraries__+ . The simplest form of interoperation with <http://hackage.haskell.org/package/pipes pipes> is accomplished with this isomorphism:@@ -102,9 +311,11 @@ > Pipes.unfoldr Streaming.next :: Stream (Of a) m r -> Producer a m r > Streaming.unfoldr Pipes.next :: Producer a m r -> Stream (Of a) m r .- (@streaming@ can be mixed with @pipes@ wherever @pipes@ + Of course, @streaming@ can be mixed with @pipes@ wherever @pipes@ itself employs @Control.Monad.Trans.Free@; speedups are frequently- appreciable.) Interoperation with + appreciable. (This was the original purpose of the main @Streaming@ module,+ which just mechanically transposes a simple optimization employed in @Pipes.Internal@.)+ Interoperation with <http://hackage.haskell.org/package/io-streams io-streams> is thus: .@@ -123,7 +334,7 @@ > Free.iterTM Stream.wrap :: FreeT f m a -> Stream f m a > Stream.iterTM Free.wrap :: Stream f m a -> FreeT f m a .- __Examples__+ * __Examples__ . For some simple ghci examples, see the commentary throughout the Prelude module. For slightly more advanced usage see the commentary in the haddocks of <https://hackage.haskell.org/package/streaming-bytestring streaming-bytestring>@@ -133,7 +344,7 @@ Here's a simple <https://gist.github.com/michaelt/2dcea1ba32562c091357 streaming GET request> with intrinsically streaming byte streams. .- __Problems__+ * __Problems__ . Questions about this library can be put as issues through the github site or on the <https://groups.google.com/forum/#!forum/haskell-pipes pipes mailing list>. @@ -169,6 +380,7 @@ , mtl >=2.1 && <2.3 , mmorph >=1.0 && <1.2 , transformers >=0.4 && <0.5+ , bytestring default-language: Haskell2010