Copyright	Copyright (c) 1998-1999 2008 Chris Okasaki
License	MIT; see COPYRIGHT file for terms and conditions
Maintainer	robdockins AT fastmail DOT fm
Stability	stable
Portability	GHC, Hugs (MPTC and FD)
Safe Haskell	None
Language	Haskell2010

Data.Edison.Seq.SimpleQueue

Contents

Sequence Type
Sequence Operations
Unit testing
Documentation

Description

Simple Queues. All operations have running times as listed in Data.Edison.Seq except for the following:

rcons, fromList O( 1 )
lview, ltail* O( 1 ) if single threaded, O( n ) otherwise
inBounds, lookup, update, drop, splitAt O( n )

References:

Chris Okasaki. Purely Functional Data Structures. 1998. Section 5.2.
F. Warren Burton. "An efficient functional implementation of FIFO queues". Information Processing Letters, 14(5):205-206, July 1982.

Synopsis

Sequence Type

data Seq a Source #

Instances

Monad Seq Source #
Methods (>>=) :: Seq a -> (a -> Seq b) -> Seq b # (>>) :: Seq a -> Seq b -> Seq b # return :: a -> Seq a # fail :: String -> Seq a #
Functor Seq Source #
Methods fmap :: (a -> b) -> Seq a -> Seq b # (<$) :: a -> Seq b -> Seq a #
Applicative Seq Source #
Methods pure :: a -> Seq a # (<>) :: Seq (a -> b) -> Seq a -> Seq b # liftA2 :: (a -> b -> c) -> Seq a -> Seq b -> Seq c # (>) :: Seq a -> Seq b -> Seq b # (<*) :: Seq a -> Seq b -> Seq a #
Sequence Seq Source #
Methods lcons :: a -> Seq a -> Seq a # rcons :: a -> Seq a -> Seq a # fromList :: [a] -> Seq a # copy :: Int -> a -> Seq a # lview :: Monad m => Seq a -> m (a, Seq a) # lhead :: Seq a -> a # lheadM :: Monad m => Seq a -> m a # ltail :: Seq a -> Seq a # ltailM :: Monad m => Seq a -> m (Seq a) # rview :: Monad m => Seq a -> m (a, Seq a) # rhead :: Seq a -> a # rheadM :: Monad m => Seq a -> m a # rtail :: Seq a -> Seq a # rtailM :: Monad m => Seq a -> m (Seq a) # null :: Seq a -> Bool # size :: Seq a -> Int # toList :: Seq a -> [a] # concat :: Seq (Seq a) -> Seq a # reverse :: Seq a -> Seq a # reverseOnto :: Seq a -> Seq a -> Seq a # fold :: (a -> b -> b) -> b -> Seq a -> b # fold' :: (a -> b -> b) -> b -> Seq a -> b # fold1 :: (a -> a -> a) -> Seq a -> a # fold1' :: (a -> a -> a) -> Seq a -> a # foldr :: (a -> b -> b) -> b -> Seq a -> b # foldr' :: (a -> b -> b) -> b -> Seq a -> b # foldl :: (b -> a -> b) -> b -> Seq a -> b # foldl' :: (b -> a -> b) -> b -> Seq a -> b # foldr1 :: (a -> a -> a) -> Seq a -> a # foldr1' :: (a -> a -> a) -> Seq a -> a # foldl1 :: (a -> a -> a) -> Seq a -> a # foldl1' :: (a -> a -> a) -> Seq a -> a # reducer :: (a -> a -> a) -> a -> Seq a -> a # reducer' :: (a -> a -> a) -> a -> Seq a -> a # reducel :: (a -> a -> a) -> a -> Seq a -> a # reducel' :: (a -> a -> a) -> a -> Seq a -> a # reduce1 :: (a -> a -> a) -> Seq a -> a # reduce1' :: (a -> a -> a) -> Seq a -> a # take :: Int -> Seq a -> Seq a # drop :: Int -> Seq a -> Seq a # splitAt :: Int -> Seq a -> (Seq a, Seq a) # subseq :: Int -> Int -> Seq a -> Seq a # filter :: (a -> Bool) -> Seq a -> Seq a # partition :: (a -> Bool) -> Seq a -> (Seq a, Seq a) # takeWhile :: (a -> Bool) -> Seq a -> Seq a # dropWhile :: (a -> Bool) -> Seq a -> Seq a # splitWhile :: (a -> Bool) -> Seq a -> (Seq a, Seq a) # inBounds :: Int -> Seq a -> Bool # lookup :: Int -> Seq a -> a # lookupM :: Monad m => Int -> Seq a -> m a # lookupWithDefault :: a -> Int -> Seq a -> a # update :: Int -> a -> Seq a -> Seq a # adjust :: (a -> a) -> Int -> Seq a -> Seq a # mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b # foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b # foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Seq a -> b # foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b # foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Seq a -> b # zip :: Seq a -> Seq b -> Seq (a, b) # zip3 :: Seq a -> Seq b -> Seq c -> Seq (a, b, c) # zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c # zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d # unzip :: Seq (a, b) -> (Seq a, Seq b) # unzip3 :: Seq (a, b, c) -> (Seq a, Seq b, Seq c) # unzipWith :: (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c) # unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d) # strict :: Seq a -> Seq a # strictWith :: (a -> b) -> Seq a -> Seq a # structuralInvariant :: Seq a -> Bool # instanceName :: Seq a -> String #
Alternative Seq Source #
Methods empty :: Seq a # (<\|>) :: Seq a -> Seq a -> Seq a # some :: Seq a -> Seq [a] # many :: Seq a -> Seq [a] #
MonadPlus Seq Source #
Methods mzero :: Seq a # mplus :: Seq a -> Seq a -> Seq a #
Eq a => Eq (Seq a) Source #
Methods (==) :: Seq a -> Seq a -> Bool # (/=) :: Seq a -> Seq a -> Bool #
Ord a => Ord (Seq a) Source #
Methods compare :: Seq a -> Seq a -> Ordering # (<) :: Seq a -> Seq a -> Bool # (<=) :: Seq a -> Seq a -> Bool # (>) :: Seq a -> Seq a -> Bool # (>=) :: Seq a -> Seq a -> Bool # max :: Seq a -> Seq a -> Seq a # min :: Seq a -> Seq a -> Seq a #
Read a => Read (Seq a) Source #
Methods readsPrec :: Int -> ReadS (Seq a) # readList :: ReadS [Seq a] # readPrec :: ReadPrec (Seq a) # readListPrec :: ReadPrec [Seq a] #
Show a => Show (Seq a) Source #
Methods showsPrec :: Int -> Seq a -> ShowS # show :: Seq a -> String # showList :: [Seq a] -> ShowS #
Semigroup (Seq a) Source #
Methods (<>) :: Seq a -> Seq a -> Seq a # sconcat :: NonEmpty (Seq a) -> Seq a # stimes :: Integral b => b -> Seq a -> Seq a #
Monoid (Seq a) Source #
Methods mempty :: Seq a # mappend :: Seq a -> Seq a -> Seq a # mconcat :: [Seq a] -> Seq a #
Arbitrary a => Arbitrary (Seq a) Source #
Methods arbitrary :: Gen (Seq a) # shrink :: Seq a -> [Seq a] #
CoArbitrary a => CoArbitrary (Seq a) Source #
Methods coarbitrary :: Seq a -> Gen b -> Gen b #