packages feed

streams 0.8.2 → 3.0

raw patch · 8 files changed

+127/−86 lines, 8 filesdep ~comonaddep ~semigroupoidsdep ~semigroups

Dependency ranges changed: comonad, semigroupoids, semigroups

Files

+ .travis.yml view
@@ -0,0 +1,1 @@+language: haskell
Data/Stream/Future.hs view
@@ -11,7 +11,7 @@ -- ---------------------------------------------------------------------------- -module Data.Stream.Future +module Data.Stream.Future   ( Future(..)   , cons, (<|)   , head@@ -27,6 +27,7 @@ import Control.Comonad import Data.Foldable import Data.Functor.Alt+import Data.Functor.Extend import Data.Traversable import Data.Semigroup hiding (Last) import Data.Semigroup.Foldable@@ -37,7 +38,7 @@  infixr 5 :<, <| -data Future a = Last a | a :< Future a deriving +data Future a = Last a | a :< Future a deriving   ( Eq, Ord, Show, Read #ifdef LANGUAGE_DeriveDataTypeable   , Data, Typeable@@ -48,7 +49,7 @@ (<|) = (:<) {-# INLINE (<|) #-} -cons :: a -> Future a -> Future a +cons :: a -> Future a -> Future a cons = (:<) {-# INLINE cons #-} @@ -91,10 +92,10 @@   fmap = map   b <$ (_ :< as) = b :< (b <$ as)   b <$ _         = Last b-  -instance Foldable Future where ++instance Foldable Future where   foldMap = foldMapDefault-  + instance Traversable Future where   traverse f (Last a)  = Last <$> f a   traverse f (a :< as) = (:<) <$> f a <*> traverse f as@@ -106,12 +107,13 @@   traverse1 f (a :< as) = (:<) <$> f a <.> traverse1 f as  instance Extend Future where-  duplicate = tails-  extend f w@(_ :< as) = f w :< extend f as-  extend f w@(Last _)  = Last (f w)+  extended = extend  instance Comonad Future where   extract = head+  duplicate = tails+  extend f w@(_ :< as) = f w :< extend f as+  extend f w@(Last _)  = Last (f w)  instance Apply Future where   Last f    <.> Last a    = Last (f a)@@ -126,14 +128,17 @@   _          .> Last b   = Last b   Last _     .> (b :< _) = Last b   (_ :< as)  .> (b :< bs) = b :< (as .> bs)-  ++instance ComonadApply Future where+  (<@>) = (<.>)+ instance Alt Future where   Last a    <!> bs = a :< bs   (a :< as) <!> bs = a :< (as <!> bs)  instance Semigroup (Future a) where   (<>) = (<!>)-  + instance Applicative Future where   pure = Last   (<*>) = (<.>)
Data/Stream/Future/Skew.hs view
@@ -11,13 +11,13 @@ -- Portability :  portable -- -- Anticausal streams implemented as non-empty skew binary random access lists--- +-- -- The Applicative zips streams, but since these are potentially infinite--- this is stricter than would be desired. You almost always want +-- this is stricter than would be desired. You almost always want ------------------------------------------------------------------------------  -module Data.Stream.Future.Skew +module Data.Stream.Future.Skew     ( Future(..)     , (<|)      -- O(1)     , cons@@ -33,22 +33,23 @@     , indexed     , from     , break-    , span +    , span     , split     -- O(log n)     , splitW    -- O(log n)-    , repeat   -    , replicate -- O(log n) +    , repeat+    , replicate -- O(log n)     , insert    -- O(n)     , insertBy     , update     , adjust    -- O(log n)     , fromList     , toFuture-    ) where +    ) where  import Control.Applicative hiding (empty) import Control.Comonad import Data.Functor.Alt+import Data.Functor.Extend import Data.Foldable hiding (toList) import Data.Traversable (Traversable, traverse) import Data.Semigroup hiding (Last)@@ -58,7 +59,7 @@  infixr 5 :<, <| -data Complete a +data Complete a     = Tip a     | Bin {-# UNPACK #-} !Int a !(Complete a) !(Complete a)     deriving Show@@ -68,15 +69,16 @@   fmap f (Bin w a l r) = Bin w (f a) (fmap f l) (fmap f r)  instance Extend Complete where-  extend f w@Tip {} = Tip (f w)-  extend f w@(Bin n _ l r) = Bin n (f w) (extend f l) (extend f r)+  extended = extend  instance Comonad Complete where+  extend f w@Tip {} = Tip (f w)+  extend f w@(Bin n _ l r) = Bin n (f w) (extend f l) (extend f r)   extract (Tip a) = a   extract (Bin _ a _ _) = a  instance Foldable Complete where-  foldMap f (Tip a) = f a +  foldMap f (Tip a) = f a   foldMap f (Bin _ a l r) = f a `mappend` foldMap f l `mappend` foldMap f r   foldr f z (Tip a) = f a z   foldr f z (Bin _ a l r) = f a (foldr f (foldr f z r) l)@@ -86,14 +88,14 @@   foldMap1 f (Bin _ a l r) = f a <> foldMap1 f l <> foldMap1 f r  instance Traversable Complete where-  traverse f (Tip a) = Tip <$> f a +  traverse f (Tip a) = Tip <$> f a   traverse f (Bin n a l r) = Bin n <$> f a <*> traverse f l <*> traverse f r  instance Traversable1 Complete where-  traverse1 f (Tip a) = Tip <$> f a +  traverse1 f (Tip a) = Tip <$> f a   traverse1 f (Bin n a l r) = Bin n <$> f a <.> traverse1 f l <.> traverse1 f r -bin :: a -> Complete a -> Complete a -> Complete a +bin :: a -> Complete a -> Complete a -> Complete a bin a l r = Bin (1 + weight l + weight r) a l r {-# INLINE bin #-} @@ -103,15 +105,15 @@ {-# INLINE weight #-}  -- A future is a non-empty skew binary random access list of nodes.--- The last node, however, is allowed to contain fewer values. -data Future a -  = Last !(Complete a) +-- The last node, however, is allowed to contain fewer values.+data Future a+  = Last !(Complete a)   | !(Complete a) :< Future a --  deriving Show   instance Show a => Show (Future a) where-  showsPrec d as = showParen (d >= 10) $ +  showsPrec d as = showParen (d >= 10) $     showString "fromList " . showsPrec 11 (toList as)  instance Functor Future where@@ -119,10 +121,11 @@   fmap f (Last t) = Last (fmap f t)  instance Extend Future where-  extend g (Last t)  = Last (extendTree g t Last)-  extend g (t :< ts) = extendTree g t (:< ts) :< extend g ts+  extended = extend  instance Comonad Future where+  extend g (Last t)  = Last (extendTree g t Last)+  extend g (t :< ts) = extendTree g t (:< ts) :< extend g ts   extract = head  extendTree :: (Future a -> b) -> Complete a -> (Complete a -> Future a) -> Complete b@@ -142,6 +145,9 @@   Tip f :< fs          <.> Bin _ a la ra :< as  = f a <| (fs             <.> la :< ra :< as)   Tip f :< fs          <.> Last (Bin _ a la ra) = f a <| (fs             <.> la :< Last ra ) +instance ComonadApply Future where+  (<@>) = (<.>)+ instance Applicative Future where   pure = repeat   (<*>) = (<.>)@@ -170,10 +176,10 @@   traverse1 f (t :< ts) = (:<) <$> traverse1 f t <.> traverse1 f ts   traverse1 f (Last t) = Last <$> traverse1 f t -repeat :: a -> Future a -repeat a0 = go a0 (Tip a0) -    where -      go :: a -> Complete a -> Future a +repeat :: a -> Future a+repeat a0 = go a0 (Tip a0)+    where+      go :: a -> Complete a -> Future a       go a as | ass <- bin a as as = as :< go a ass {-# INLINE repeat #-} @@ -182,20 +188,20 @@ replicate n a   | n <= 0    = error "replicate: non-positive argument"   | otherwise = go 1 n a (Tip a) (\ _ r -> r)-  where -  -- invariants: +  where+  -- invariants:   -- tb is a complete tree of i nodes all equal to b   -- 1 <= i = 2^m-1 <= j   -- k accepts r such that 0 <= r < i   go :: Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r-  go !i !j b tb k +  go !i !j b tb k     | j >= i2p1 = go i2p1 j b (Bin i2p1 b tb tb) k'     | j >= i2   = k (j - i2) (tb :< Last tb)     | otherwise = k (j - i) (Last tb)-    where +    where       i2 = i * 2       i2p1 = i2 + 1-      k' r xs +      k' r xs         | r >= i2   = k (r - i2) (tb :< tb :< xs)         | r >= i    = k (r - i) (tb :< xs)         | otherwise = k r xs@@ -203,7 +209,7 @@  mapWithIndex :: (Int -> a -> b) -> Future a -> Future b mapWithIndex f0 as0 = spine f0 0 as0-  where +  where     spine f m (Last as) = Last (tree f m as)     spine f m (a :< as) = tree f m a :< spine f (m + weight a) as     tree f m (Tip a) = Tip (f m a)@@ -218,7 +224,7 @@ {-# INLINE from #-}  -- | /O(1)/-singleton :: a -> Future a +singleton :: a -> Future a singleton a = Last (Tip a) {-# INLINE singleton #-} @@ -229,22 +235,22 @@  -- | /O(1)/ cons (<|) :: a -> Future a -> Future a-a <| (l :< Last r)  +a <| (l :< Last r)   | weight l == weight r = Last (bin a l r)-a <| (l :< r :< as) +a <| (l :< r :< as)   | weight l == weight r = bin a l r :< as a <| as = Tip a :< as {-# INLINE (<|) #-}   cons :: a -> Future a -> Future a-cons = (<|)  +cons = (<|) {-# INLINE cons #-}  -- | /O(1)/ head :: Future a -> a head (a :< _) = extract a-head (Last a) = extract a +head (Last a) = extract a {-# INLINE head #-}  -- | /O(1)/.@@ -276,17 +282,17 @@  -- | /O(log n)/. index :: Int -> Future a -> a-index i (Last t) +index i (Last t)   | i < weight t = indexComplete i t   | otherwise    = error "index: out of range"-index i (t :< ts) +index i (t :< ts)   | i < w     = indexComplete i t   | otherwise = index (i - w) ts   where w = weight t  indexComplete :: Int -> Complete a -> a indexComplete 0 (Tip a) = a-indexComplete i (Bin w a l r) +indexComplete i (Bin w a l r)   | i == 0    = a   | i <= w'   = indexComplete (i-1) l   | otherwise = indexComplete (i-1-w') r@@ -301,24 +307,24 @@   EQ -> Just ts   GT -> drop (i - w) ts   where w = weight t-drop i (Last t) +drop i (Last t)   | i < w     = Just (dropComplete i t Last)   | otherwise = Nothing   where w = weight t -dropComplete :: Int -> Complete a -> (Complete a -> Future a) -> Future a +dropComplete :: Int -> Complete a -> (Complete a -> Future a) -> Future a dropComplete 0 t f             = f t dropComplete 1 (Bin _ _ l r) f = l :< f r dropComplete i (Bin w _ l r) f = case compare (i - 1) w' of   LT -> dropComplete (i-1) l (:< f r)   EQ -> f r-  GT -> dropComplete (i-1-w') r f +  GT -> dropComplete (i-1-w') r f   where w' = div w 2 dropComplete _ _ _ = error "drop: index out of range"  -- /O(n)/. dropWhile :: (a -> Bool) -> Future a -> Maybe (Future a)-dropWhile p as +dropWhile p as   | p (head as) = tail as >>= dropWhile p   | otherwise = Just as @@ -336,7 +342,7 @@ -- /(O(n), O(log n))/ split at _some_ edge where function goes from False to True. -- best used with a monotonic function split :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))-split p l@(Last a) +split p l@(Last a)   | p (extract a)  = ([], Just l)   | otherwise      = splitComplete p a Last split p (a :< as)@@ -361,7 +367,7 @@ splitW p l@(Last a)   | p l       = ([], Just l)   | otherwise = splitCompleteW p a Last-splitW p (a :< as) +splitW p (a :< as)   | p as                    = splitCompleteW p a (:< as)   | (ts, fs) <- splitW p as = (foldr (:) ts a, fs) @@ -381,7 +387,7 @@   where go a [] = singleton a         go a (b:bs) = a <| go b bs -toFuture :: [a] -> Maybe (Future a) +toFuture :: [a] -> Maybe (Future a) toFuture [] = Nothing toFuture xs = Just (fromList xs) @@ -399,10 +405,10 @@  -- /O(log n)/ Change the value of the nth entry in the future adjust :: Int -> (a -> a) -> Future a -> Future a-adjust !n f d@(Last a) +adjust !n f d@(Last a)   | n < weight a = Last (adjustComplete n f a)   | otherwise = d-adjust !n f (a :< as) +adjust !n f (a :< as)   | n < w = adjustComplete n f a :< as   | otherwise = a :< adjust (n - w) f as   where w = weight a@@ -410,7 +416,7 @@ adjustComplete :: Int -> (a -> a) -> Complete a -> Complete a adjustComplete 0 f (Tip a) = Tip (f a) adjustComplete _ _ t@Tip{} = t-adjustComplete n f (Bin m a l r) +adjustComplete n f (Bin m a l r)   | n == 0 = Bin m (f a) l r   | n < w = Bin m a (adjustComplete (n - 1) f l) r   | otherwise = Bin m a l (adjustComplete (n - 1 - w) f r)
Data/Stream/Infinite.hs view
@@ -80,6 +80,7 @@ import Data.Char (isSpace) import Data.Data import Data.Functor.Apply+import Data.Functor.Extend import Data.Semigroup import Data.Foldable import Data.Traversable@@ -124,16 +125,23 @@ tails w = w :> tails (tail w)  instance Extend Stream where-  duplicate = tails-  extend f w = f w :> extend f (tail w)+  duplicated = tails+  extended f w = f w :> extended f (tail w)  instance Comonad Stream where+  duplicate = tails+  extend f w = f w :> extend f (tail w)   extract = head  instance Apply Stream where   (f :> fs) <.> (a :> as) = f a :> (fs <.> as)   as        <.  _         = as   _          .> bs        = bs++instance ComonadApply Stream where+  (f :> fs) <@> (a :> as) = f a :> (fs <@> as)+  as        <@  _         = as+  _          @> bs        = bs  -- | 'repeat' @x@ returns a constant stream, where all elements are -- equal to @x@.
Data/Stream/Infinite/Functional/Zipper.hs view
@@ -55,6 +55,7 @@ #ifdef LANGUAGE_DeriveDataTypeable import Data.Data #endif+import Data.Functor.Extend import Data.Functor.Apply -- import Data.Monoid import Data.Semigroup@@ -102,9 +103,10 @@ uncons (n :~ f) = (f n, n + 1 :~ f)  instance Extend Zipper where-  duplicate (n :~ f) = n :~ (:~ f)+  duplicated (n :~ f) = n :~ (:~ f)  instance Comonad Zipper where+  duplicate (n :~ f) = n :~ (:~ f)   extract (n :~ f) = f n  instance Apply Zipper where@@ -113,6 +115,12 @@     = nf :~ \n -> f n (a (n + dn))   as        <.  _         = as   _          .> bs        = bs++instance ComonadApply Zipper where+  (<@>) = (<.>)+  (<@) = (<.)+  (@>) = (.>)+  instance Applicative Zipper where   pure = repeat
Data/Stream/Infinite/Skew.hs view
@@ -47,6 +47,7 @@ import Control.Comonad import Data.Distributive import Data.Functor.Alt+import Data.Functor.Extend import Data.Foldable hiding (toList) import Data.Traversable import Data.Semigroup hiding (Last)@@ -66,10 +67,12 @@   fmap f (Bin w a l r) = Bin w (f a) (fmap f l) (fmap f r)  instance Extend Complete where-  extend f w@Tip {} = Tip (f w)-  extend f w@(Bin n _ l r) = Bin n (f w) (extend f l) (extend f r)+  extended f w@Tip {} = Tip (f w)+  extended f w@(Bin n _ l r) = Bin n (f w) (extended f l) (extended f r)  instance Comonad Complete where+  extend f w@Tip {} = Tip (f w)+  extend f w@(Bin n _ l r) = Bin n (f w) (extend f l) (extend f r)   extract (Tip a) = a   extract (Bin _ a _ _) = a @@ -113,19 +116,25 @@   fmap f (t :< ts) = fmap f t :< fmap f ts  instance Extend Stream where+  extended = extend++instance Comonad Stream where   extend g0 (t :< ts) = go g0 t (:< ts) :< extend g0 ts-    where +    where       go :: (Stream a -> b) -> Complete a -> (Complete a -> Stream a) -> Complete b       go g w@Tip{}         f = Tip (g (f w))       go g w@(Bin n _ l r) f = Bin n (g (f w)) (go g l (:< f r))  (go g r f)--instance Comonad Stream where   extract = head  instance Apply Stream where   fs <.> as = mapWithIndex (\n f -> f (as !! n)) fs   as <.  _  = as   _   .> bs = bs++instance ComonadApply Stream where+  (<@>) = (<.>)+  (<@) = (<.)+  (@>) = (.>)  instance Applicative Stream where   pure = repeat
Data/Stream/Supply.hs view
@@ -42,6 +42,7 @@ import Control.Applicative import Control.Comonad import Data.Functor.Apply+import Data.Functor.Extend import Data.Foldable import Data.IORef(newIORef, atomicModifyIORef) import Data.Traversable@@ -75,10 +76,12 @@   a <$ _ = pure a  instance Extend Supply where-  extend f s@(Supply _ l r) = Supply (f s) (extend f l) (extend f r)-  duplicate s@(Supply _ l r) = Supply s (duplicate l) (duplicate r)+  extended f s@(Supply _ l r) = Supply (f s) (extended f l) (extended f r)+  duplicated s@(Supply _ l r) = Supply s (duplicated l) (duplicated r)  instance Comonad Supply where+  extend f s@(Supply _ l r) = Supply (f s) (extend f l) (extend f r)+  duplicate s@(Supply _ l r) = Supply s (duplicate l) (duplicate r)   extract (Supply a _ _) = a  instance Apply Supply where
streams.cabal view
@@ -1,6 +1,6 @@ name:          streams category:      Control, Comonads-version:       0.8.2+version:       3.0 license:       BSD3 cabal-version: >= 1.6 license-file:  LICENSE@@ -8,38 +8,39 @@ maintainer:    Edward A. Kmett <ekmett@gmail.com> stability:     provisional homepage:      http://github.com/ekmett/streams-copyright:     Copyright 2011 Edward Kmett+homepage:      http://github.com/ekmett/streams/issues+copyright:     Copyright 2011-2012 Edward Kmett                Copyright 2010 Tony Morris, Oliver Taylor, Eelis van der Weegen                Copyright 2007-2010 Wouter Swierstra, Bas van Dijk                Copyright 2008 Iavor S. Diatchki synopsis:      Various Haskell 2010 stream comonads build-type:    Simple-extra-source-files: README-description:   +extra-source-files: README .travis.yml+description:   Various Haskell 2010 stream comonads.-  * "Data.Stream.Future" provides a coinductive anti-causal stream, or non-empty 'ZipList'. The comonad provides access to only the +  * "Data.Stream.Future" provides a coinductive anti-causal stream, or non-empty 'ZipList'. The comonad provides access to only the     tail of the stream. Like a conventional 'ZipList', this is /not/ a monad.   .   > data Future a = Last a | a :< Future a   .   * "Data.Stream.Future.Skew" provides a non-empty skew-binary random-access-list with the semantics of @Data.Stream.Future@. As with-    "Data.Stream.Future" this stream is not a 'Monad', since the 'Applicative' instance zips streams of potentially differing lengths. -    The random-access-list structure provides a number of operations logarithmic access time, but makes 'Data.Stream.Future.Skew.cons' -    less productive. Where applicable "Data.Stream.Infinite.Skew" may be more efficient, due to a lazier and more efficient 'Applicative' +    "Data.Stream.Future" this stream is not a 'Monad', since the 'Applicative' instance zips streams of potentially differing lengths.+    The random-access-list structure provides a number of operations logarithmic access time, but makes 'Data.Stream.Future.Skew.cons'+    less productive. Where applicable "Data.Stream.Infinite.Skew" may be more efficient, due to a lazier and more efficient 'Applicative'     instance.-  . +  .   >   .   * "Data.Stream.Infinite" provides a coinductive infinite anti-causal stream. The 'Comonad' provides access to the tail of the-    stream and the 'Applicative' zips streams together. Unlike 'Future', infinite stream form a 'Monad'. The monad diagonalizes -    the 'Stream', which is consistent with the behavior of the 'Applicative', and the view of a 'Stream' as a isomorphic to the reader +    stream and the 'Applicative' zips streams together. Unlike 'Future', infinite stream form a 'Monad'. The monad diagonalizes+    the 'Stream', which is consistent with the behavior of the 'Applicative', and the view of a 'Stream' as a isomorphic to the reader     monad from the natural numbers. Being infinite in length, there is no 'Alternative' instance, but instead the 'FunctorAlt'     instance provides access to the 'Semigroup' of interleaving streams.   .   > data Stream a = a :< Stream a   .   * "Data.Stream.Infinite.Skew" provides an infinite skew-binary random-access-list with the semantics of "Data.Stream.Infinite"-    Since every stream is infinite, the 'Applicative' instance can be considerably less strict than the corresponding instance for +    Since every stream is infinite, the 'Applicative' instance can be considerably less strict than the corresponding instance for     "Data.Stream.Future.Skew" and performs asymptotically better.   .   >@@ -64,7 +65,7 @@   .   * Data.Stream.Supply added   .-  /Changes since 0.1/: +  /Changes since 0.1/:   .   * A number of strictness issues with 'NonEmpty' were fixed   .@@ -73,7 +74,7 @@ source-repository head   type: git   location: git://github.com/ekmett/streams.git-  + library   other-extensions:     PatternGuards@@ -81,10 +82,10 @@    build-depends:     base          >= 4       && < 5,-    comonad       >= 1.1.1.3 && < 1.2,+    comonad       == 3.0.*,     distributive  >= 0.2.1   && < 0.3,-    semigroupoids >= 1.3     && < 1.4,-    semigroups    >= 0.8.2   && < 0.9+    semigroupoids == 3.0.*,+    semigroups    >= 0.8.3.1 && < 0.9    extensions: CPP   if impl(ghc)