-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | utilities for DP -- -- Small set of utility functions, as well as the base types for generic -- backtracing. @package DPutils @version 0.1.0.0 -- | The base constructors for generic backtracing. -- -- NOTE this currently can capture dot-bracket notation, but not deep -- semantics. module DP.Backtraced.Core -- | This is a bit like a lazy Data.Sequence in terms of -- constructors. We can not be spine-strict, otherwise we'd use -- Data.Sequence and enjoy the better performance. data Backtraced ty -- | This backtrace is done [Epsilon] :: Backtraced ty -- | Expand a backtrace to the left. This is lazy, since backtracing relies -- on laziness. [Cons] :: ty -> Backtraced ty -> Backtraced ty -- | Expand lazily to the right. [Snoc] :: Backtraced ty -> ty -> Backtraced ty -- | concatenate two structures [Append] :: Backtraced ty -> Backtraced ty -> Backtraced ty (<|) :: () => ty -> Backtraced ty -> Backtraced ty infixr 5 <| (|>) :: () => Backtraced ty -> ty -> Backtraced ty infixl 5 |> (><) :: () => Backtraced ty -> Backtraced ty -> Backtraced ty infixr 5 >< instance Data.Traversable.Traversable DP.Backtraced.Core.Backtraced instance Data.Foldable.Foldable DP.Backtraced.Core.Backtraced instance GHC.Base.Functor DP.Backtraced.Core.Backtraced instance GHC.Generics.Generic (DP.Backtraced.Core.Backtraced ty) instance GHC.Read.Read ty => GHC.Read.Read (DP.Backtraced.Core.Backtraced ty) instance GHC.Show.Show ty => GHC.Show.Show (DP.Backtraced.Core.Backtraced ty) instance GHC.Classes.Ord ty => GHC.Classes.Ord (DP.Backtraced.Core.Backtraced ty) instance GHC.Classes.Eq ty => GHC.Classes.Eq (DP.Backtraced.Core.Backtraced ty) instance Control.Lens.Cons.Cons (DP.Backtraced.Core.Backtraced ty) (DP.Backtraced.Core.Backtraced ty') ty ty' instance Control.Lens.Cons.Snoc (DP.Backtraced.Core.Backtraced ty) (DP.Backtraced.Core.Backtraced ty') ty ty' instance Test.SmallCheck.Series.Serial m a => Test.SmallCheck.Series.Serial m (DP.Backtraced.Core.Backtraced a) -- | Taken from Michael Thompson -- http://hackage.haskell.org/package/streaming-utils module Data.Attoparsec.ByteString.Streaming type Message = ([String], String) -- | The parsed function from streaming-utils parsed :: Monad m => Parser a -> ByteString m r -> Stream (Of a) m (Either (Message, ByteString m r) r) -- | Splitting functions for ByteString m r into Stream -- (ByteString m) m r. -- -- TODO These functions need quickcheck tests. module Data.ByteString.Streaming.Split -- | Split a ByteString m r after every k characters. -- -- Streams in constant memory. -- -- BUG: Once the stream is exhausted, it will still call -- splitAt, forever creating empty ByteStrings. splitsByteStringAt :: Monad m => Int -> ByteString m r -> Stream (ByteString m) m r -- | For lists, this would be sbs (f :: [a] -> ([a],[a])) -> [a] -- -> [[a]]. Takes a function that splits the bytestring into two -- elements repeatedly, where the first is followed by the repeated -- application of the function. -- -- cf. -- http://hackage.haskell.org/package/streaming-utils-0.1.4.7/docs/src/Streaming-Pipes.html#chunksOf -- -- TODO these functions should go into a helper library separatesByteString :: Monad m => (ByteString m r -> ByteString m (ByteString m r)) -> ByteString m r -> Stream (ByteString m) m r -- | Convert between Word8 and Char. Mostly for -- attoparsec's bytestring module. module Data.Char.Util c2w8 :: Char -> Word8 w82c :: Word8 -> Char module Data.Paired.Common -- | Shall we combine elements on the main diagonal as well? -- -- If we choose NoDiag, we deal with upper triangular matrices -- that are effectively one element smaller. data OnDiag OnDiag :: OnDiag NoDiag :: OnDiag -- | Select only a subset of the possible enumerations. data Enumerate -- | Enumerate all elements All :: Enumerate -- | Enumerate from a value and at most N elements FromN :: Int -> Int -> Enumerate -- | If the size of the input is known before-hand or not. data SizeHint UnknownSize :: SizeHint KnownSize :: Int -> SizeHint instance GHC.Classes.Eq Data.Paired.Common.SizeHint instance GHC.Classes.Eq Data.Paired.Common.Enumerate instance GHC.Classes.Eq Data.Paired.Common.OnDiag module Data.Paired.Vector -- | Upper triangular elements. upperTriVG :: (Vector v a, Vector w (a, a)) => OnDiag -> v a -> (Int, w (a, a)) -- | Outer pairing of all as with all bs. This one is -- quasi-trivial, but here for completeness. rectangularVG :: (Vector va a, Vector vb b, Vector w (a, b)) => va a -> vb b -> (Int, w (a, b)) -- | Helper functions for turnings streams into vectors. -- -- Mostly very similar to bundle conversion functions from the -- vector package. module Data.Vector.Generic.Unstream -- | Turns a stream into a vector. -- -- TODO insert index checks? Generalized flag devel streamToVectorM :: forall m v a. (Monad m, Vector v a) => Stream m a -> m (v a) -- | Triangular numbers and various helper functions. -- -- Main use is for linearization of triangular array indexing. -- -- Triangular numbers: @ T_n = Σ_{k=1)^n k = 1 + 2 + 3 + ... + n = -- -- n * (n+1) / 2 = (n+1) choose 2 @ module Math.TriangularNumbers -- | Triangular numbers. -- -- https://oeis.org/A000217 triangularNumber :: Int -> Int -- | Size of an upper triangle starting at i and ending at -- j. "(0,N)" what be the normal thing to use. linearizeUppertri :: (Int, Int) -> Int -- | Subword indexing. Given the longest subword and the current subword, -- calculate a linear index "[0,..]". "(l,n)" in this case means "l"ower -- bound, length "n". And "(i,j)" is the normal index. -- -- 
--   0 1 2 3    <- j = ...
--   
--   0 1 2 3    i=0
--   _ 4 5 6    i=1
--   _ _ 7 8    i=2
--         9    i=3
--   
--   i=2, j=3  -> (4+1) * i - tri i + j
--   
--   _
--   _ _  the triangular number to subtract.
--
toLinear :: Int -> (Int, Int) -> Int -- | Linear index to paired. -- -- We have indices in [0,N], and linear index k. -- -- 
--   (N+1)*i - (i*(i+1)/2) + j == K
--
fromLinear :: Int -> Int -> (Int, Int) -- | Efficient enumeration of subsets of triangular elements. Given a list -- [1..n] we want to enumerate a subset [(i,j)] of -- ordered pairs in such a way that we only have to hold the elements -- necessary for this subset in memory. module Data.Paired.Foldable -- | Generalized upper triangular elements. Given a list of elements -- [e_1,...,e_k], we want to return pairs (e_i,e_j) -- such that we have all ordered pairs with i<j (if -- NoDiagonal elements), or i<=j (if -- OnDiagonal elements). -- -- upperTri will force the spine of t a but is consumed -- linearly with a strict Data.Foldable.foldl'. Internally we -- keep a Data.IntMap of the retained elements. -- -- This is important if the Enumerate type is set to FromN k -- n. We start at the kth element, and produce n -- elements. -- -- TODO compare IntMap and HashMap. -- -- TODO inRange is broken. upperTri :: Foldable t => SizeHint -> OnDiag -> Enumerate -> t a -> Either String (IntMap a, Int, [((Int, Int), (a, a))]) -- | Pipes that introduce parallelism on different levels. module Pipes.Parallel -- | Evaluates chunks of pipes elements in parallel with a pure function. pipePar :: Monad m => Int -> Strategy b -> (a -> b) -> Pipe a b m () -- | Evaluates chunks of pipes elements in parallel with a pure function. -- Before and after each parallel step, a monadic function is run. This -- allows generation of certain statistics or information during runs. pipeParBA :: Monad m => Int -> Strategy b -> (a -> b) -> ([a] -> m (x, [a])) -> (x -> [b] -> m [b]) -> Pipe a b m () -- | Split incombing bytestrings based on bytestrings. module Pipes.Split.ByteString type Lens' a b = forall f. Functor f => (b -> f b) -> (a -> f a) -- | Splits bytestrings after each pattern pat. Tries to minimize -- the number of intermediate bytestring constructors. -- -- The following function ske expects a string str and -- a pattern pat and then returns a tuple with the splitted -- bytestrings in fst and the return value in snd. -- -- The inner parser parse uses zoom to draw the full -- inner producer, which should contain just one bytestring, namely one -- of the split off ones. parse doesn't do anything with the -- inner producer, except returning the contained bytestring. -- -- parse returns Right $ concat xs on a correct parse, -- and Left [] once the input has been exhausted. -- -- 
--   ske :: ByteString -> ByteString -> ([ByteString],[ByteString],[ByteString])
--   ske pat str | BS.null pat || BS.null str = ([],[],[])
--   ske pat str =
--     let parse = do
--           xs <- zoom (splitKeepEnd pat) PP.drawAll
--           case xs of
--             [] -> return $ Left []
--             xs -> return $ Right $ BS.concat xs
--         (a,(b,p)) = runIdentity . P.toListM' $ PP.parsed parse $ PP.yield str
--     in (a,b, fst . runIdentity . P.toListM' $ p)
--
splitKeepEnd :: Monad m => ByteString -> Lens' (Producer ByteString m x) (Producer ByteString m (Producer ByteString m x)) -- | Split a string into substrings, where each substring starts with -- pat and continues until just before the next pat (or -- until there is no more input). -- -- Any prefix that does not start with the substring is kept! -- -- Since each substring is supposed to start with pat, there is -- a small problem. What about a header that prefixes the string we are -- interested in? splitKeepStart :: Monad m => ByteString -> Lens' (Producer ByteString m x) (Producer ByteString m (Producer ByteString m x)) -- | Generic splitting function. Takes a bytestring [a,b,c] (where -- a,b,c are substrings of the bytestring!) and performs the -- split. splitGeneric :: Monad m => (ByteString -> Int -> Int -> Int -> (ByteString, ByteString)) -> ByteString -> Lens' (Producer ByteString m x) (Producer ByteString m (Producer ByteString m x)) referenceByteStringTokenizer :: ByteString -> ByteString -> [ByteString] module Streaming.Primitive instance (GHC.Base.Monad m, Control.Monad.Primitive.PrimMonad m, GHC.Base.Functor f) => Control.Monad.Primitive.PrimMonad (Streaming.Internal.Stream f m)