streams 3.2.1 → 3.3
raw patch · 9 files changed
+272/−171 lines, 9 filesdep ~comonadnew-uploader
Dependency ranges changed: comonad
Files
- .gitignore +16/−0
- .travis.yml +95/−2
- CHANGELOG.markdown +11/−0
- src/Data/Stream/Future.hs +46/−38
- src/Data/Stream/Future/Skew.hs +44/−39
- src/Data/Stream/Infinite.hs +30/−48
- src/Data/Stream/Infinite/Functional/Zipper.hs +6/−10
- src/Data/Stream/Infinite/Skew.hs +22/−32
- streams.cabal +2/−2
.gitignore view
@@ -11,3 +11,19 @@ *.hi *~ *#+dist-*+cabal-dev+*.chi+*.chs.h+*.dyn_o+*.dyn_hi+.hpc+.hsenv+.cabal-sandbox/+cabal.sandbox.config+*.prof+*.aux+*.hp+*.eventlog+.stack-work/+cabal.project.local
.travis.yml view
@@ -1,8 +1,101 @@-language: haskell+# This file has been generated -- see https://github.com/hvr/multi-ghc-travis+language: c+sudo: false++cache:+ directories:+ - $HOME/.cabsnap+ - $HOME/.cabal/packages++before_cache:+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/build-reports.log+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.tar++matrix:+ include:+ - env: CABALVER=1.18 GHCVER=7.4.2+ compiler: ": #GHC 7.4.2"+ addons: {apt: {packages: [cabal-install-1.18,ghc-7.4.2], sources: [hvr-ghc]}}+ - env: CABALVER=1.18 GHCVER=7.6.3+ compiler: ": #GHC 7.6.3"+ addons: {apt: {packages: [cabal-install-1.18,ghc-7.6.3], sources: [hvr-ghc]}}+ - env: CABALVER=1.18 GHCVER=7.8.4+ compiler: ": #GHC 7.8.4"+ addons: {apt: {packages: [cabal-install-1.18,ghc-7.8.4], sources: [hvr-ghc]}}+ - env: CABALVER=1.22 GHCVER=7.10.3+ compiler: ": #GHC 7.10.3"+ addons: {apt: {packages: [cabal-install-1.22,ghc-7.10.3], sources: [hvr-ghc]}}+ - env: CABALVER=1.24 GHCVER=8.0.1+ compiler: ": #GHC 8.0.1"+ addons: {apt: {packages: [cabal-install-1.24,ghc-8.0.1], sources: [hvr-ghc]}}+ - env: CABALVER=head GHCVER=head+ compiler: ": #GHC head"+ addons: {apt: {packages: [cabal-install-head,ghc-head], sources: [hvr-ghc]}}++ allow_failures:+ - env: CABALVER=head GHCVER=head++before_install:+ - unset CC+ - export PATH=$HOME/.cabal/bin:/opt/ghc/$GHCVER/bin:/opt/cabal/$CABALVER/bin:$PATH++install:+ - cabal --version+ - echo "$(ghc --version) [$(ghc --print-project-git-commit-id 2> /dev/null || echo '?')]"+ - if [ -f $HOME/.cabal/packages/hackage.haskell.org/00-index.tar.gz ];+ then+ zcat $HOME/.cabal/packages/hackage.haskell.org/00-index.tar.gz >+ $HOME/.cabal/packages/hackage.haskell.org/00-index.tar;+ fi+ - travis_retry cabal update -v+ - sed -i 's/^jobs:/-- jobs:/' ${HOME}/.cabal/config+ - cabal install --only-dependencies --enable-tests --dry -v > installplan.txt+ - sed -i -e '1,/^Resolving /d' installplan.txt; cat installplan.txt++# check whether current requested install-plan matches cached package-db snapshot+ - if diff -u installplan.txt $HOME/.cabsnap/installplan.txt;+ then+ echo "cabal build-cache HIT";+ rm -rfv .ghc;+ cp -a $HOME/.cabsnap/ghc $HOME/.ghc;+ cp -a $HOME/.cabsnap/lib $HOME/.cabsnap/share $HOME/.cabsnap/bin $HOME/.cabal/;+ else+ echo "cabal build-cache MISS";+ rm -rf $HOME/.cabsnap;+ mkdir -p $HOME/.ghc $HOME/.cabal/lib $HOME/.cabal/share $HOME/.cabal/bin;+ cabal install -j --only-dependencies --enable-tests;+ fi++# snapshot package-db on cache miss+ - if [ ! -d $HOME/.cabsnap ];+ then+ echo "snapshotting package-db to build-cache";+ mkdir $HOME/.cabsnap;+ cp -a $HOME/.ghc $HOME/.cabsnap/ghc;+ cp -a $HOME/.cabal/lib $HOME/.cabal/share $HOME/.cabal/bin installplan.txt $HOME/.cabsnap/;+ fi++# Here starts the actual work to be performed for the package under test;+# any command which exits with a non-zero exit code causes the build to fail.+script:+ - cabal configure -v2 --enable-tests # -v2 provides useful information for debugging+ - cabal build # this builds all libraries and executables (including tests/benchmarks)+ - cabal sdist # tests that a source-distribution can be generated+ - export SRC_TGZ=$(cabal info . | awk '{print $2 ".tar.gz";exit}') ;+ cd dist/;+ if [ -f "$SRC_TGZ" ]; then+ cabal install "$SRC_TGZ";+ else+ echo "expected '$SRC_TGZ' not found";+ exit 1;+ fi+ notifications: irc: channels: - "irc.freenode.org#haskell-lens" skip_join: true template:- - "\x0313streams\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"+ - "\x0313streams\x0f/\x0306%{branch}\x0f \x0314%{commit}\x0f %{message} \x0302\x1f%{build_url}\x0f"++# EOF
CHANGELOG.markdown view
@@ -1,3 +1,14 @@+3.3+---+* Removed a number of redundant parts of the API. If a method you were using has been removed, consider the classes available. No functionality was lost.+* Better support for GHC 7.10, the `Foldable (length, null)` members are now defined directly leading to asymptotic improvements and helping to further shrink the API.+* Added `prepend` and `concat` functions to `Data.Stream.Infinite`+* Allow `comonad-5`++3.2.2+-----+* Bug fix in `Data.Stream.Infinite.Skew` and removed `fromList`.+ 3.2.1 ----- * Add support for `semigroupoids` 5 and GHC 7.10
src/Data/Stream/Future.hs view
@@ -1,12 +1,13 @@ {-# LANGUAGE BangPatterns #-}+{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE CPP #-}-#if __GLASGOW_HASKELL__ >= 702 && __GLASGOW_HASKELL__ < 710+#if __GLASGOW_HASKELL__ >= 702 {-# LANGUAGE Trustworthy #-} #endif ----------------------------------------------------------------------------- -- | -- Module : Data.Stream.Future--- Copyright : (C) 2011 Edward Kmett+-- Copyright : (C) 2011-2015 Edward Kmett -- License : BSD-style (see the file LICENSE) -- -- Maintainer : Edward Kmett <ekmett@gmail.com>@@ -17,35 +18,37 @@ module Data.Stream.Future ( Future(..)- , cons, (<|)- , head , tail , length- , tails- , map , index ) where -import Prelude hiding (head, tail, map, length)-#if !(MIN_VERSION_base(4,8,0))+#if MIN_VERSION_base(4,8,0)+import Prelude hiding (tail)+#else import Control.Applicative-#endif-import Control.Comonad-#if !(MIN_VERSION_base(4,8,0))+import Prelude hiding (tail, length) import Data.Foldable #endif++import Control.Comonad import Data.Functor.Alt import Data.Functor.Extend import Data.Traversable import Data.Semigroup hiding (Last) import Data.Semigroup.Foldable import Data.Semigroup.Traversable+ #ifdef LANGUAGE_DeriveDataTypeable import Data.Data #endif -infixr 5 :<, <|+#if MIN_VERSION_base(4,7,0)+import GHC.Exts as Exts+#endif +infixr 5 :<+ data Future a = Last a | a :< Future a deriving ( Eq, Ord, Show, Read #ifdef LANGUAGE_DeriveDataTypeable@@ -53,41 +56,20 @@ #endif ) -(<|) :: a -> Future a -> Future a-(<|) = (:<)-{-# INLINE (<|) #-}--cons :: a -> Future a -> Future a-cons = (:<)-{-# INLINE cons #-}--head :: Future a -> a-head (Last a) = a-head (a :< _) = a-{-# INLINE head #-}-+#if __GLASGOW_HASKELL__ < 710 length :: Future a -> Int length = go 1 where go !n (Last _) = n go !n (_ :< as) = go (n + 1) as {-# INLINE length #-}+#endif tail :: Future a -> Maybe (Future a) tail (Last _) = Nothing tail (_ :< as) = Just as {-# INLINE tail #-} -tails :: Future a -> Future (Future a)-tails w@(_ :< as) = w :< tails as-tails w@(Last _) = Last w-{-# INLINE tails #-}--map :: (a -> b) -> Future a -> Future b-map f (a :< as) = f a :< map f as-map f (Last a) = Last (f a)-{-# INLINE map #-}- index :: Int -> Future a -> a index n aas | n < 0 = error "index: negative index"@@ -97,12 +79,21 @@ _ :< as -> index (n - 1) as instance Functor Future where- fmap = map+ fmap f (a :< as) = f a :< fmap f as+ fmap f (Last a) = Last (f a) b <$ (_ :< as) = b :< (b <$ as) b <$ _ = Last b instance Foldable Future where foldMap = foldMapDefault+#if __GLASGOW_HASKELL__ >= 710+ length = go 1+ where+ go !n (Last _) = n+ go !n (_ :< as) = go (n + 1) as+ {-# INLINE length #-}+ null _ = False+#endif instance Traversable Future where traverse f (Last a) = Last <$> f a@@ -118,8 +109,12 @@ extended = extend instance Comonad Future where- extract = head- duplicate = tails+ extract (Last a) = a+ extract (a :< _) = a++ duplicate w@(_ :< as) = w :< duplicate as+ duplicate w@(Last _) = Last w+ extend f w@(_ :< as) = f w :< extend f as extend f w@(Last _) = Last (f w) @@ -153,4 +148,17 @@ (<* ) = (<. ) ( *>) = ( .>) +#if MIN_VERSION_base(4,7,0)+instance Exts.IsList (Future a) where+ type Item (Future a) = a + toList (Last a) = [a]+ toList (a :< as) = a : Exts.toList as++ fromList [] = error "Future.fromList: empty list"+ fromList (x:xs) = go x xs where+ go y [] = Last y+ go y (z:zs) = y :< go z zs++ fromListN _ = Exts.fromList+#endif
src/Data/Stream/Future/Skew.hs view
@@ -1,12 +1,13 @@-{-# LANGUAGE PatternGuards, BangPatterns #-}+{-# LANGUAGE PatternGuards, BangPatterns, TypeFamilies #-} {-# LANGUAGE CPP #-}-#if __GLASGOW_HASKELL__ >= 702 && __GLASGOW_HASKELL__ < 710+#if __GLASGOW_HASKELL__ >= 702 {-# LANGUAGE Trustworthy #-} #endif+ ----------------------------------------------------------------------------- -- | -- Module : Data.Stream.Future.Skew--- Copyright : (C) 2008-2011 Edward Kmett,+-- Copyright : (C) 2008-2015 Edward Kmett, -- (C) 2004 Dave Menendez -- License : BSD-style (see the file LICENSE) --@@ -24,11 +25,8 @@ module Data.Stream.Future.Skew ( Future(..) , (<|) -- O(1)- , cons , length -- O(log n)- , head -- O(1) , tail -- O(1)- , tails , last -- O(log n) , uncons -- O(1) , index -- O(log n)@@ -40,14 +38,13 @@ , span , split -- O(log n) , splitW -- O(log n)- , repeat , replicate -- O(log n) , insert -- O(n) , insertBy , update , adjust -- O(log n)- , fromList , toFuture+ , singleton ) where import Control.Applicative hiding (empty)@@ -55,15 +52,19 @@ import Data.Functor.Alt import Data.Functor.Extend #if MIN_VERSION_base(4,8,0)-import Data.Foldable hiding (toList, length)+import Prelude hiding (tail, drop, dropWhile, last, span, repeat, replicate, break)+import Data.Foldable (toList) #else-import Data.Foldable hiding (toList)+import Data.Foldable import Data.Traversable (Traversable, traverse)+import Prelude hiding (null, tail, drop, dropWhile, length, foldr, last, span, repeat, replicate, break) #endif import Data.Semigroup hiding (Last) import Data.Semigroup.Foldable import Data.Semigroup.Traversable-import Prelude hiding (null, head, tail, drop, dropWhile, length, foldr, last, span, repeat, replicate, break)+#if MIN_VERSION_base(4,7,0)+import qualified GHC.Exts as Exts+#endif infixr 5 :<, <| @@ -90,6 +91,11 @@ 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)+#if MIN_VERSION_base(4,8,0)+ length Tip{} = 1+ length (Bin n _ _ _) = n+ null _ = False+#endif instance Foldable1 Complete where foldMap1 f (Tip a) = f a@@ -134,7 +140,8 @@ 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+ extract (a :< _) = extract a+ extract (Last a) = extract a extendTree :: (Future a -> b) -> Complete a -> (Complete a -> Future a) -> Complete b extendTree g w@Tip{} f = Tip (g (f w))@@ -157,7 +164,9 @@ (<@>) = (<.>) instance Applicative Future where- pure = repeat+ pure a0 = go a0 (Tip a0) where+ go :: a -> Complete a -> Future a+ go a as | ass <- bin a as as = as :< go a ass (<*>) = (<.>) instance Alt Future where@@ -168,9 +177,11 @@ foldMap f (Last t) = foldMap f t foldr f z (t :< ts) = foldr f (foldr f z ts) t foldr f z (Last t) = foldr f z t--toList :: Future a -> [a]-toList = foldr (:) []+#if MIN_VERSION_base(4,8,0)+ length (Last t) = weight t+ length (t :< ts) = weight t + length ts+ null _ = False+#endif instance Foldable1 Future where foldMap1 f (t :< ts) = foldMap1 f t <> foldMap1 f ts@@ -184,13 +195,6 @@ 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- go a as | ass <- bin a as as = as :< go a ass-{-# INLINE repeat #-}- -- | /O(log n)/ replicate :: Int -> a -> Future a replicate n a@@ -236,10 +240,12 @@ singleton a = Last (Tip a) {-# INLINE singleton #-} +#if !(MIN_VERSION_base(4,8,0)) -- | /O(log n)/. length :: Future a -> Int length (Last t) = weight t length (t :< ts) = weight t + length ts+#endif -- | /O(1)/ cons (<|) :: a -> Future a -> Future a@@ -250,17 +256,6 @@ a <| as = Tip a :< as {-# INLINE (<|) #-} --cons :: a -> Future a -> Future a-cons = (<|)-{-# INLINE cons #-}---- | /O(1)/-head :: Future a -> a-head (a :< _) = extract a-head (Last a) = extract a-{-# INLINE head #-}- -- | /O(1)/. tail :: Future a -> Maybe (Future a) tail (Tip{} :< ts) = Just ts@@ -269,10 +264,6 @@ tail (Last (Bin _ _ l r)) = Just (l :< Last r) {-# INLINE tail #-} -tails :: Future a -> Future (Future a)-tails = duplicate-{-# INLINE tails #-}- -- | /O(log n)/. last :: Future a -> a last (_ :< as) = last as@@ -333,7 +324,7 @@ -- /O(n)/. dropWhile :: (a -> Bool) -> Future a -> Maybe (Future a) dropWhile p as- | p (head as) = tail as >>= dropWhile p+ | p (extract as) = tail as >>= dropWhile p | otherwise = Just as -- /O(n)/@@ -389,15 +380,29 @@ | w <- f r, p w, (ts, fs) <- splitCompleteW p l (:< w) = (a:ts, fs) | (ts, fs) <- splitCompleteW p r f = (a:foldr (:) ts l, fs) +#if MIN_VERSION_base(4,7,0)+instance Exts.IsList (Future a) where+ type Item (Future a) = a+ toList = Data.Foldable.toList+ fromList [] = error "fromList: empty list"+ fromList (x:xs) = go x xs+ where go a [] = singleton a+ go a (b:bs) = a <| go b bs+#else fromList :: [a] -> Future a fromList [] = error "fromList: empty list" fromList (x:xs) = go x xs where go a [] = singleton a go a (b:bs) = a <| go b bs+#endif toFuture :: [a] -> Maybe (Future a) toFuture [] = Nothing+#if MIN_VERSION_base(4,7,0)+toFuture xs = Just (Exts.fromList xs)+#else toFuture xs = Just (fromList xs)+#endif -- /O(n)/ insert :: Ord a => a -> Future a -> Future a
src/Data/Stream/Infinite.hs view
@@ -20,12 +20,11 @@ -- * The type of streams Stream(..) -- * Basic functions- , head -- :: Stream a -> a , tail -- :: Stream a -> Stream a , inits -- :: Stream a -> Stream [a]- , tails -- :: Stream a -> Stream (Stream a)+ , prepend -- :: [a] -> Stream a -> Stream a+ , concat -- :: Stream [a] -> Stream a -- * Stream transformations- , map -- :: (a -> b) -> Stream a -> Stream b , intersperse -- :: a -> Stream a -> Stream , interleave -- :: Stream a -> Stream a -> Stream a , scanl -- :: (b -> a -> b) -> b -> Stream a -> Stream b@@ -35,7 +34,6 @@ , transpose -- :: Stream (Stream a) -> Stream (Stream a) -- * Building streams , iterate -- :: (a -> a) -> a -> Stream a- , repeat -- :: a -> Stream a , cycle -- :: NonEmpty a -> Stream a , unfold -- :: (a -> (b, a)) -> a -> Stream b -- * Extracting sublists@@ -67,17 +65,15 @@ , unwords -- :: Stream String -> Stream Char , lines -- :: Stream Char -> Stream String , unlines -- :: Stream String -> Stream Char- -- * Converting to and from an infinite list- , fromList -- :: [a] -> Stream a ) where import Prelude hiding- ( head, tail, map, scanr, scanr1, scanl, scanl1+ ( tail, map, scanr, scanr1, scanl, scanl1 , iterate, take, drop, takeWhile , dropWhile, repeat, cycle, filter , (!!), zip, unzip, zipWith, words , unwords, lines, unlines, break, span- , splitAt, foldr+ , splitAt, foldr, concat ) #if !(MIN_VERSION_base(4,8,0))@@ -93,7 +89,7 @@ import Data.Semigroup import Data.Traversable #endif-import Data.Foldable+import Data.Foldable hiding (concat) import Data.Distributive import Data.Semigroup.Traversable import Data.Semigroup.Foldable@@ -108,16 +104,12 @@ infixr 5 :> --- | Map a pure function over a stream-map :: (a -> b) -> Stream a -> Stream b-map f (a :> as) = f a :> map f as- instance Functor Stream where- fmap = map- b <$ _ = repeat b+ fmap f (a :> as) = f a :> fmap f as+ b <$ _ = pure b instance Distributive Stream where- distribute w = fmap head w :> distribute (fmap tail w)+ distribute w = fmap extract w :> distribute (fmap tail w) instance Representable Stream where type Rep Stream = Int@@ -127,29 +119,20 @@ | n > 0 = xs !! (n - 1) | otherwise = error "Stream.!! negative argument" --- | Extract the first element of the sequence.-head :: Stream a -> a-head (a :> _) = a-{-# INLINE head #-} -- | Extract the sequence following the head of the stream. tail :: Stream a -> Stream a tail (_ :> as) = as {-# INLINE tail #-} --- | The 'tails' function takes a stream @xs@ and returns all the--- suffixes of @xs@.-tails :: Stream a -> Stream (Stream a)-tails w = w :> tails (tail w)- instance Extend Stream where- duplicated = tails- extended f w = f w :> extended f (tail w)+ duplicated = duplicate+ extended = extend instance Comonad Stream where- duplicate = tails+ duplicate w = w :> duplicate (tail w) extend f w = f w :> extend f (tail w)- extract = head+ extract (a :> _) = a instance Apply Stream where (f :> fs) <.> (a :> as) = f a :> (fs <.> as)@@ -161,13 +144,8 @@ as <@ _ = as _ @> bs = bs --- | 'repeat' @x@ returns a constant stream, where all elements are--- equal to @x@.-repeat :: a -> Stream a-repeat a = as where as = a :> as- instance Applicative Stream where- pure = repeat+ pure a = as where as = a :> as (<*>) = (<.>) (<* ) = (<. ) ( *>) = ( .>)@@ -176,6 +154,10 @@ fold (m :> ms) = m `mappend` fold ms foldMap f (a :> as) = f a `mappend` foldMap f as foldr f0 _ = go f0 where go f (a :> as) = f a (go f as)+#if __GLASGOW_HASKELL__ > 710+ length _ = error "infinite length"+ null _ = False+#endif instance Traversable Stream where traverse f ~(a :> as) = (:>) <$> f a <*> traverse f as@@ -192,8 +174,8 @@ unfold f c | (x, d) <- f c = x :> unfold f d instance Monad Stream where- return = repeat- m >>= f = unfold (\(bs :> bss) -> (head bs, tail <$> bss)) (fmap f m)+ return = pure+ m >>= f = unfold (\(bs :> bss) -> (extract bs, tail <$> bss)) (fmap f m) _ >> bs = bs -- | Interleave two Streams @xs@ and @ys@, alternating elements@@ -214,8 +196,16 @@ -- -- > inits _|_ = _|_ inits :: Stream a -> Stream [a]-inits xs = [] :> ((head xs :) <$> inits (tail xs))+inits xs = [] :> ((extract xs :) <$> inits (tail xs)) +-- | Prepend a list to a stream.+prepend :: Foldable f => f a -> Stream a -> Stream a+prepend xs ys = foldr (:>) ys xs++-- | Flatten a stream of lists into a stream.+concat :: Foldable f => Stream (f a) -> Stream a+concat = foldr prepend undefined+ -- | @'intersperse' y xs@ creates an alternating stream of -- elements from @xs@ and @y@. intersperse :: a -> Stream a -> Stream a@@ -246,7 +236,7 @@ -- | 'transpose' computes the transposition of a stream of streams. transpose :: Stream (Stream a) -> Stream (Stream a) transpose ~((x :> xs) :> yss) =- (x :> (head <$> yss)) :> transpose (xs :> (tail <$> yss))+ (x :> (extract <$> yss)) :> transpose (xs :> (tail <$> yss)) -- | @'iterate' f x@ produces the infinite sequence -- of repeated applications of @f@ to @x@.@@ -291,7 +281,7 @@ splitAt :: Int -> Stream a -> ([a],Stream a) splitAt n xs | n == 0 = ([],xs)- | n > 0, (prefix, rest) <- splitAt (n - 1) (tail xs) = (head xs : prefix, rest)+ | n > 0, (prefix, rest) <- splitAt (n - 1) (tail xs) = (extract xs : prefix, rest) | otherwise = error "Stream.splitAt: negative argument" -- | @'takeWhile' p xs@ returns the longest prefix of the stream@@ -457,11 +447,3 @@ -- joins lines, after appending a terminating newline to each. unlines :: Stream String -> Stream Char unlines ~(x :> xs) = foldr (:>) ('\n' :> unlines xs) x---- | The 'fromList' converts an infinite list to a--- stream.------ /Beware/: Passing a finite list, will cause an error.-fromList :: [a] -> Stream a-fromList (x:xs) = x :> fromList xs-fromList [] = error "Stream.listToStream applied to finite list"
src/Data/Stream/Infinite/Functional/Zipper.hs view
@@ -4,8 +4,8 @@ #endif ----------------------------------------------------------------------------- -- |--- Module : Data.Zipper.Infinite.Functional.Zipper--- Copyright : (C) 2011 Edward Kmett,+-- Module : Data.Stream.Infinite.Functional.Zipper+-- Copyright : (C) 2011-2015 Edward Kmett -- License : BSD-style (see the file LICENSE) -- -- Maintainer : Edward Kmett <ekmett@gmail.com>@@ -49,24 +49,17 @@ , dropWhile, repeat, cycle, filter , (!!), zip, unzip, zipWith, words , unwords, lines, unlines, break, span- , splitAt, foldr+ , splitAt, foldr, reverse ) import Control.Applicative import Control.Comonad--- import Data.Char (isSpace) #ifdef LANGUAGE_DeriveDataTypeable import Data.Data #endif import Data.Functor.Extend import Data.Functor.Apply--- import Data.Monoid import Data.Semigroup--- import Data.Foldable--- import Data.Traversable--- import Data.Semigroup.Traversable--- import Data.Semigroup.Foldable--- import Data.Zipper.NonEmpty (NonEmpty(..)) data Zipper a = !Integer :~ !(Integer -> a) #ifdef LANGUAGE_DeriveDataTypeable@@ -75,6 +68,9 @@ toSequence :: (Integer -> a) -> Zipper a toSequence = (0 :~)++reverse :: Zipper a -> Zipper a+reverse (n :~ f) = negate n :~ f . negate infixr 0 :~
src/Data/Stream/Infinite/Skew.hs view
@@ -24,9 +24,7 @@ ( Stream , (<|) -- O(1) , (!!)- , head -- O(1) , tail -- O(1)- , tails , uncons -- O(1) , drop -- O(log n) , dropWhile -- O(n)@@ -39,7 +37,6 @@ , insertBy , adjust -- O(log n) , update -- O(log n)- , fromList , from , indexed , interleave@@ -52,7 +49,7 @@ import Data.Functor.Alt import Data.Functor.Extend import Data.Functor.Rep-import Data.Foldable hiding (toList)+import Data.Foldable import Data.Traversable import Data.Semigroup hiding (Last) import Data.Semigroup.Foldable@@ -85,6 +82,11 @@ 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)+#if __GLASGOW_HASKELL__ >= 710+ length Tip{} = 1+ length (Bin n _ _ _) = fromIntegral n+ null _ = False+#endif instance Foldable1 Complete where foldMap1 f (Tip a) = f a@@ -128,7 +130,7 @@ 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)- extract = head+ extract (a :< _) = extract a instance Apply Stream where fs <.> as = mapWithIndex (\n f -> f (as !! n)) fs@@ -151,13 +153,13 @@ (q,0) -> as !! q (q,_) -> bs !! q - instance Foldable Stream where foldMap f (t :< ts) = foldMap f t `mappend` foldMap f ts foldr f z (t :< ts) = foldr f (foldr f z ts) t--toList :: Stream a -> [a]-toList = foldr (:) []+#if __GLASGOW_HASKELL__ >= 710+ length _ = error "infinite length"+ null _ = False+#endif instance Foldable1 Stream where foldMap1 f (t :< ts) = foldMap1 f t <> foldMap1 f ts@@ -216,21 +218,12 @@ a <| as = Tip a :< as {-# INLINE (<|) #-} --- | /O(1)/-head :: Stream a -> a-head (a :< _) = extract a-{-# INLINE head #-}- -- | /O(1)/. tail :: Stream a -> Stream a tail (Tip{} :< ts) = ts tail (Bin _ _ l r :< ts) = l :< r :< ts {-# INLINE tail #-} -tails :: Stream a -> Stream (Stream a)-tails = duplicate-{-# INLINE tails #-}- -- | /O(1)/. uncons :: Stream a -> (a, Stream a) uncons (Tip a :< as) = (a, as)@@ -269,23 +262,23 @@ where w' = div w 2 dropComplete _ _ _ = error "dropComplete" --- /O(n)/.+-- | /O(n)/. dropWhile :: (a -> Bool) -> Stream a -> Stream a dropWhile p as- | p (head as) = dropWhile p (tail as)+ | p (extract as) = dropWhile p (tail as) | otherwise = as --- /O(n)/+-- | /O(n)/ span :: (a -> Bool) -> Stream a -> ([a], Stream a) span p as- | a <- head as, p a = first (a:) $ span p (tail as)+ | a <- extract as, p a = first (a:) $ span p (tail as) | otherwise = ([], as) --- /O(n)/+-- | /O(n)/ break :: (a -> Bool) -> Stream a -> ([a], Stream a) break p = span (not . p) --- /(O(n), O(log n))/ split at _some_ edge where function goes from False to True.+-- | /(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) -> Stream a -> ([a], Stream a) split p (a :< as)@@ -300,7 +293,7 @@ | p (extract r), (ts, fs) <- splitComplete p l (:< f r) = (a:ts, fs) | (ts, fs) <- splitComplete p r f = (a:foldr (:) ts l, fs) --- /(O(n), O(log n))/ split at _some_ edge where function goes from False to True.+-- | /(O(n), O(log n))/ split at _some_ edge where function goes from False to True. -- best used with a monotonic function -- -- > splitW p xs = (map extract &&& fmap (fmap extract)) . split p . duplicate@@ -317,18 +310,15 @@ | w <- f r, p w, (ts, fs) <- splitCompleteW p l (:< w) = (a:ts, fs) | (ts, fs) <- splitCompleteW p r f = (a:foldr (:) ts l, fs) -fromList :: [a] -> Stream a-fromList = foldr (<|) (error "fromList: finite list")---- /O(n)/+-- | /O(n)/ insert :: Ord a => a -> Stream a -> Stream a insert a as | (ts, as') <- split (a<=) as = foldr (<|) (a <| as') ts --- /O(n)/. Finds the split in O(log n), but then has to recons+-- | /O(n)/. Finds the split in O(log n), but then has to recons insertBy :: (a -> a -> Ordering) -> a -> Stream a -> Stream a insertBy cmp a as | (ts, as') <- split (\b -> cmp a b <= EQ) as = foldr (<|) (a <| as') ts --- /O(log n)/ Change the value of the nth entry in the future+-- | /O(log n)/ Change the value of the nth entry in the future adjust :: Integer -> (a -> a) -> Stream a -> Stream a adjust !n f (a :< as) | n < w = adjustComplete n f a :< as@@ -340,7 +330,7 @@ adjustComplete _ _ t@Tip{} = t 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+ | n <= w = Bin m a (adjustComplete (n - 1) f l) r | otherwise = Bin m a l (adjustComplete (n - 1 - w) f r) where w = weight l
streams.cabal view
@@ -1,6 +1,6 @@ name: streams category: Control, Comonads-version: 3.2.1+version: 3.3 license: BSD3 cabal-version: >= 1.6 license-file: LICENSE@@ -70,7 +70,7 @@ build-depends: base >= 4 && < 5, adjunctions >= 4.0.1 && < 5,- comonad >= 4 && < 5,+ comonad >= 4 && < 6, distributive >= 0.2.1 && < 1, semigroupoids >= 4 && < 6, semigroups >= 0.8.3.1 && < 1