-- |
--   Module      :  Data.Edison.Seq.BankersQueue
--   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)
--
--   This module implements Banker's Queues. It has the standard running
--   times from "Data.Edison.Seq" except for the following:
--
--   * rcons, size, inBounds   @O( 1 )@
--
--   /References:/
--
--   * Chris Okasaki, /Purely Functional Data Structures/,
--     1998, sections 6.3.2 and 8.4.1.
--
--   * Chris Okasaki, \"Simple and efficient purely functional
--     queues and deques\", /Journal of Function Programming/
--     5(4):583-592, October 1995.

module Data.Edison.Seq.BankersQueue (
    -- * Sequence Type
    Seq, -- instance of Sequence, Functor, Monad, MonadPlus

    -- * Sequence operations
    empty,singleton,lcons,rcons,append,lview,lhead,ltail,rview,rhead,rtail,
    lheadM,ltailM,rheadM,rtailM,
    null,size,concat,reverse,reverseOnto,fromList,toList,map,concatMap,
    fold,fold',fold1,fold1',foldr,foldr',foldl,foldl',foldr1,foldr1',foldl1,foldl1',
    reducer,reducer',reducel,reducel',reduce1,reduce1',
    copy,inBounds,lookup,lookupM,lookupWithDefault,update,adjust,
    mapWithIndex,foldrWithIndex,foldrWithIndex',foldlWithIndex,foldlWithIndex',
    take,drop,splitAt,subseq,filter,partition,takeWhile,dropWhile,splitWhile,
    zip,zip3,zipWith,zipWith3,unzip,unzip3,unzipWith,unzipWith3,
    strict, strictWith,

    -- * Unit testing
    structuralInvariant,

    -- * Documentation
    moduleName

) where

import Prelude hiding (concat,reverse,map,concatMap,foldr,foldl,foldr1,foldl1,
                       filter,takeWhile,dropWhile,lookup,take,drop,splitAt,
                       zip,zip3,zipWith,zipWith3,unzip,unzip3,null)

import qualified Control.Applicative as App

import Data.Edison.Prelude ( runFail_ )
import qualified Data.Edison.Seq as S ( Sequence(..) )
import Data.Edison.Seq.Defaults
import qualified Data.Edison.Seq.ListSeq as L
import Data.Monoid
import Data.Semigroup as SG
import qualified Control.Monad.Fail as Fail
import Control.Monad.Identity
import Test.QuickCheck

-- signatures for exported functions
moduleName     :: String
empty          :: Seq a
singleton      :: a -> Seq a
lcons          :: a -> Seq a -> Seq a
rcons          :: a -> Seq a -> Seq a
append         :: Seq a -> Seq a -> Seq a
lview          :: (Fail.MonadFail m) => Seq a -> m (a, Seq a)
lhead          :: Seq a -> a
lheadM         :: (Fail.MonadFail m) => Seq a -> m a
ltail          :: Seq a -> Seq a
ltailM         :: (Fail.MonadFail m) => Seq a -> m (Seq a)
rview          :: (Fail.MonadFail m) => Seq a -> m (a, Seq a)
rhead          :: Seq a -> a
rheadM         :: (Fail.MonadFail m) => Seq a -> m a
rtail          :: Seq a -> Seq a
rtailM         :: (Fail.MonadFail m) => Seq a -> m (Seq a)
null           :: Seq a -> Bool
size           :: Seq a -> Int
concat         :: Seq (Seq a) -> Seq a
reverse        :: Seq a -> Seq a
reverseOnto    :: Seq a -> Seq a -> Seq a
fromList       :: [a] -> Seq a
toList         :: Seq a -> [a]
map            :: (a -> b) -> Seq a -> Seq b
concatMap      :: (a -> Seq b) -> Seq a -> Seq b
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
foldl          :: (b -> a -> b) -> b -> Seq a -> b
foldr1         :: (a -> a -> a) -> Seq a -> a
foldl1         :: (a -> a -> a) -> Seq a -> a
reducer        :: (a -> a -> a) -> a -> Seq a -> a
reducel        :: (a -> a -> a) -> a -> Seq a -> a
reduce1        :: (a -> a -> a) -> Seq a -> a
foldr'         :: (a -> b -> b) -> b -> Seq a -> b
foldl'         :: (b -> a -> b) -> b -> Seq a -> b
foldr1'        :: (a -> a -> a) -> Seq a -> a
foldl1'        :: (a -> a -> a) -> Seq a -> a
reducer'       :: (a -> a -> a) -> a -> Seq a -> a
reducel'       :: (a -> a -> a) -> a -> Seq a -> a
reduce1'       :: (a -> a -> a) -> Seq a -> a
copy           :: Int -> a -> Seq a
inBounds       :: Int -> Seq a -> Bool
lookup         :: Int -> Seq a -> a
lookupM        :: (Fail.MonadFail 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
foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b
foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Seq a -> b
foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Seq a -> b
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)
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

moduleName :: String
moduleName = String
"Data.Edison.Seq.BankersQueue"


data Seq a = Q !Int [a] [a] !Int

-- invariant: front at least as long as rear
structuralInvariant :: forall a. Seq a -> Bool
structuralInvariant (Q Int
x [a]
f [a]
r Int
y) =
    forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
f forall a. Eq a => a -> a -> Bool
== Int
x Bool -> Bool -> Bool
&& forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
r forall a. Eq a => a -> a -> Bool
== Int
y Bool -> Bool -> Bool
&& Int
x forall a. Ord a => a -> a -> Bool
>= Int
y


-- not exported
makeQ :: Int -> [a] -> [a] -> Int -> Seq a
makeQ :: forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ Int
i [a]
xs [a]
ys Int
j
  | Int
j forall a. Ord a => a -> a -> Bool
> Int
i     = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
i forall a. Num a => a -> a -> a
+ Int
j) ([a]
xs forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [a]
L.reverse [a]
ys) [] Int
0
  | Bool
otherwise = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs [a]
ys Int
j

empty :: forall a. Seq a
empty = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
0 [] [] Int
0
singleton :: forall a. a -> Seq a
singleton a
x = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
1 [a
x] [] Int
0
lcons :: forall a. a -> Seq a -> Seq a
lcons a
x (Q Int
i [a]
xs [a]
ys Int
j) = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
iforall a. Num a => a -> a -> a
+Int
1) (a
xforall a. a -> [a] -> [a]
:[a]
xs) [a]
ys Int
j
rcons :: forall a. a -> Seq a -> Seq a
rcons a
y (Q Int
i [a]
xs [a]
ys Int
j) = forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ Int
i [a]
xs (a
yforall a. a -> [a] -> [a]
:[a]
ys) (Int
jforall a. Num a => a -> a -> a
+Int
1)

append :: forall a. Seq a -> Seq a -> Seq a
append (Q Int
i1 [a]
xs1 [a]
ys1 Int
j1) (Q Int
i2 [a]
xs2 [a]
ys2 Int
j2) =
    forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
i1 forall a. Num a => a -> a -> a
+ Int
j1 forall a. Num a => a -> a -> a
+ Int
i2) ([a]
xs1 forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [a] -> [a]
L.reverseOnto [a]
ys1 [a]
xs2) [a]
ys2 Int
j2

lview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview (Q Int
_ [] [a]
_ Int
_) = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BankersQueue.lview: empty sequence"
lview (Q Int
i (a
x:[a]
xs) [a]
ys Int
j) = forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ (Int
iforall a. Num a => a -> a -> a
-Int
1) [a]
xs [a]
ys Int
j)

lhead :: forall a. Seq a -> a
lhead (Q Int
_ [] [a]
_ Int
_) = forall a. HasCallStack => String -> a
error String
"BankersQueue.lhead: empty sequence"
lhead (Q Int
_ (a
x:[a]
_) [a]
_ Int
_) = a
x

lheadM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m a
lheadM (Q Int
_ [] [a]
_ Int
_) = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BankersQueue.lheadM: empty sequence"
lheadM (Q Int
_ (a
x:[a]
_) [a]
_ Int
_) = forall (m :: * -> *) a. Monad m => a -> m a
return a
x

ltail :: forall a. Seq a -> Seq a
ltail (Q Int
i (a
_:[a]
xs) [a]
ys Int
j) = forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ (Int
iforall a. Num a => a -> a -> a
-Int
1) [a]
xs [a]
ys Int
j
ltail Seq a
_ = forall a. HasCallStack => String -> a
error String
"BankersQueue.ltail: empty sequence"

ltailM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
ltailM (Q Int
i (a
_:[a]
xs) [a]
ys Int
j) = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ (Int
iforall a. Num a => a -> a -> a
-Int
1) [a]
xs [a]
ys Int
j)
ltailM Seq a
_ = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BankersQueue.ltail: empty sequence"

rview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
rview (Q Int
i [a]
xs (a
y:[a]
ys) Int
j) = forall (m :: * -> *) a. Monad m => a -> m a
return (a
y, forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs [a]
ys (Int
jforall a. Num a => a -> a -> a
-Int
1))
rview (Q Int
i [a]
xs [] Int
_) =
  case forall (rm :: * -> *) a. MonadFail rm => [a] -> rm (a, [a])
L.rview [a]
xs of
    Maybe (a, [a])
Nothing      -> forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BankersQueue.rview: empty sequence"
    Just (a
x,[a]
xs') -> forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
iforall a. Num a => a -> a -> a
-Int
1) [a]
xs' [] Int
0)

rhead :: forall a. Seq a -> a
rhead (Q Int
_ [a]
_ (a
y:[a]
_) Int
_) = a
y
rhead (Q Int
_ [] [] Int
_) = forall a. HasCallStack => String -> a
error String
"BankersQueue.rhead: empty sequence"
rhead (Q Int
_ [a]
xs [] Int
_) = forall a. [a] -> a
L.rhead [a]
xs

rheadM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m a
rheadM (Q Int
_ [a]
_ (a
y:[a]
_) Int
_) = forall (m :: * -> *) a. Monad m => a -> m a
return a
y
rheadM (Q Int
_ [] [] Int
_) = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BankersQueue.rheadM: empty sequence"
rheadM (Q Int
_ [a]
xs [] Int
_) = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. [a] -> a
L.rhead [a]
xs)

rtail :: forall a. Seq a -> Seq a
rtail (Q Int
i [a]
xs (a
_:[a]
ys) Int
j) = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs [a]
ys (Int
jforall a. Num a => a -> a -> a
-Int
1)
rtail (Q Int
_ [] [] Int
_) = forall a. HasCallStack => String -> a
error String
"BankersQueue.rtail: empty sequence"
rtail (Q Int
i [a]
xs [] Int
_) = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
iforall a. Num a => a -> a -> a
-Int
1) (forall a. [a] -> [a]
L.rtail [a]
xs) [] Int
0

rtailM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
rtailM (Q Int
i [a]
xs (a
_:[a]
ys) Int
j) = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs [a]
ys (Int
jforall a. Num a => a -> a -> a
-Int
1))
rtailM (Q Int
_ [] [] Int
_) = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BankersQueue.rtailM: empty sequence"
rtailM (Q Int
i [a]
xs [] Int
_) = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
iforall a. Num a => a -> a -> a
-Int
1) (forall a. [a] -> [a]
L.rtail [a]
xs) [] Int
0)

null :: forall a. Seq a -> Bool
null (Q Int
i [a]
_ [a]
_ Int
_) = (Int
i forall a. Eq a => a -> a -> Bool
== Int
0)
size :: forall a. Seq a -> Int
size (Q Int
i [a]
_ [a]
_ Int
j) = Int
i forall a. Num a => a -> a -> a
+ Int
j
reverse :: forall a. Seq a -> Seq a
reverse (Q Int
i [a]
xs [a]
ys Int
j) = forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ Int
j [a]
ys [a]
xs Int
i

reverseOnto :: forall a. Seq a -> Seq a -> Seq a
reverseOnto (Q Int
i1 [a]
xs1 [a]
ys1 Int
j1) (Q Int
i2 [a]
xs2 [a]
ys2 Int
j2) =
    forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
i1 forall a. Num a => a -> a -> a
+ Int
j1 forall a. Num a => a -> a -> a
+ Int
i2) ([a]
ys1 forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [a] -> [a]
L.reverseOnto [a]
xs1 [a]
xs2) [a]
ys2 Int
j2

fromList :: forall a. [a] -> Seq a
fromList [a]
xs = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) [a]
xs [] Int
0

toList :: forall a. Seq a -> [a]
toList (Q Int
_ [a]
xs [a]
ys Int
j)
  | Int
j forall a. Eq a => a -> a -> Bool
== Int
0 = [a]
xs
  | Bool
otherwise = [a]
xs forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [a]
L.reverse [a]
ys

map :: forall a b. (a -> b) -> Seq a -> Seq b
map a -> b
f (Q Int
i [a]
xs [a]
ys Int
j) = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i (forall a b. (a -> b) -> [a] -> [b]
L.map a -> b
f [a]
xs) (forall a b. (a -> b) -> [a] -> [b]
L.map a -> b
f [a]
ys) Int
j

-- local fn on lists
revfoldr :: (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr :: forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr t -> t1 -> t1
_ t1
e [] = t1
e
revfoldr t -> t1 -> t1
f t1
e (t
x:[t]
xs) = forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr t -> t1 -> t1
f (t -> t1 -> t1
f t
x t1
e) [t]
xs

revfoldr' :: (t -> a -> a) -> a -> [t] -> a
revfoldr' :: forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr' t -> a -> a
_ a
e [] = a
e
revfoldr' t -> a -> a
f a
e (t
x:[t]
xs) = a
e seq :: forall a b. a -> b -> b
`seq` forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr' t -> a -> a
f (t -> a -> a
f t
x a
e) [t]
xs

-- local fn on lists
revfoldl :: (t -> t1 -> t) -> t -> [t1] -> t
revfoldl :: forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl t -> t1 -> t
_ t
e [] = t
e
revfoldl t -> t1 -> t
f t
e (t1
x:[t1]
xs) = t -> t1 -> t
f (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl t -> t1 -> t
f t
e [t1]
xs) t1
x

revfoldl' :: (b -> t -> b) -> b -> [t] -> b
revfoldl' :: forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl' b -> t -> b
_ b
e [] = b
e
revfoldl' b -> t -> b
f b
e (t
x:[t]
xs) = (\b
z -> b -> t -> b
f b
z t
x) forall a b. (a -> b) -> a -> b
$! (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl b -> t -> b
f b
e [t]
xs)

fold :: forall a b. (a -> b -> b) -> b -> Seq a -> b
fold  a -> b -> b
f b
e (Q Int
_ [a]
xs [a]
ys Int
_) = forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
L.foldr a -> b -> b
f (forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
L.foldr a -> b -> b
f b
e [a]
ys) [a]
xs
fold' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
fold' a -> b -> b
f b
e (Q Int
_ [a]
xs [a]
ys Int
_) = (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
L.foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
f) forall a b. (a -> b) -> a -> b
$! (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
L.foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
f) b
e [a]
ys)) [a]
xs
fold1 :: forall a. (a -> a -> a) -> Seq a -> a
fold1  = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
fold1UsingFold
fold1' :: forall a. (a -> a -> a) -> Seq a -> a
fold1' = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
fold1'UsingFold'

foldr :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr  a -> b -> b
f b
e (Q Int
_ [a]
xs [a]
ys Int
_) = forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
L.foldr  a -> b -> b
f (forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr  a -> b -> b
f b
e [a]
ys) [a]
xs
foldr' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr' a -> b -> b
f b
e (Q Int
_ [a]
xs [a]
ys Int
_) = forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
L.foldr' a -> b -> b
f (forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr' a -> b -> b
f b
e [a]
ys) [a]
xs
foldl :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl  b -> a -> b
f b
e (Q Int
_ [a]
xs [a]
ys Int
_) = forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl  b -> a -> b
f (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
L.foldl  b -> a -> b
f b
e [a]
xs) [a]
ys
foldl' :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl' b -> a -> b
f b
e (Q Int
_ [a]
xs [a]
ys Int
_) = forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl' b -> a -> b
f (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
L.foldl' b -> a -> b
f b
e [a]
xs) [a]
ys

foldr1 :: forall a. (a -> a -> a) -> Seq a -> a
foldr1 a -> a -> a
f (Q Int
_ [a]
xs (a
y:[a]
ys) Int
_) = forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
L.foldr a -> a -> a
f (forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr a -> a -> a
f a
y [a]
ys) [a]
xs
foldr1 a -> a -> a
f (Q Int
i [a]
xs [] Int
_)
  | Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. HasCallStack => String -> a
error String
"BankersQueue.foldr1: empty sequence"
  | Bool
otherwise = forall a. (a -> a -> a) -> [a] -> a
L.foldr1 a -> a -> a
f [a]
xs

foldr1' :: forall a. (a -> a -> a) -> Seq a -> a
foldr1' a -> a -> a
f (Q Int
_ [a]
xs (a
y:[a]
ys) Int
_) = forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
L.foldr' a -> a -> a
f (forall t t1. (t -> t1 -> t1) -> t1 -> [t] -> t1
revfoldr' a -> a -> a
f a
y [a]
ys) [a]
xs
foldr1' a -> a -> a
f (Q Int
i [a]
xs [] Int
_)
  | Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. HasCallStack => String -> a
error String
"BankersQueue.foldr1': empty sequence"
  | Bool
otherwise = forall a. (a -> a -> a) -> [a] -> a
L.foldr1' a -> a -> a
f [a]
xs

foldl1 :: forall a. (a -> a -> a) -> Seq a -> a
foldl1 a -> a -> a
f (Q Int
_ (a
x:[a]
xs) [a]
ys Int
_) = forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl a -> a -> a
f (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
L.foldl a -> a -> a
f a
x [a]
xs) [a]
ys
foldl1 a -> a -> a
_ Seq a
_ = forall a. HasCallStack => String -> a
error String
"BankersQueue.foldl1: empty sequence"

foldl1' :: forall a. (a -> a -> a) -> Seq a -> a
foldl1' a -> a -> a
f (Q Int
_ (a
x:[a]
xs) [a]
ys Int
_) = forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
revfoldl' a -> a -> a
f (forall t t1. (t -> t1 -> t) -> t -> [t1] -> t
L.foldl' a -> a -> a
f a
x [a]
xs) [a]
ys
foldl1' a -> a -> a
_ Seq a
_ = forall a. HasCallStack => String -> a
error String
"BankersQueue.foldl1': empty sequence"

copy :: forall a. Int -> a -> Seq a
copy Int
n a
x
  | Int
n forall a. Ord a => a -> a -> Bool
< Int
0     = forall a. Seq a
empty
  | Bool
otherwise = forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
n (forall a. Int -> a -> [a]
L.copy Int
n a
x) [] Int
0

-- reduce1: given sizes could do more effective job of dividing evenly!

lookup :: forall a. Int -> Seq a -> a
lookup Int
idx Seq a
q = forall a. Fail a -> a
runFail_ (forall (m :: * -> *) a. MonadFail m => Int -> Seq a -> m a
lookupM Int
idx Seq a
q)

lookupM :: forall (m :: * -> *) a. MonadFail m => Int -> Seq a -> m a
lookupM Int
idx (Q Int
i [a]
xs [a]
ys Int
j)
  | Int
idx forall a. Ord a => a -> a -> Bool
< Int
i   = forall (m :: * -> *) a. MonadFail m => Int -> [a] -> m a
L.lookupM Int
idx [a]
xs
  | Bool
otherwise = forall (m :: * -> *) a. MonadFail m => Int -> [a] -> m a
L.lookupM (Int
j forall a. Num a => a -> a -> a
- (Int
idx forall a. Num a => a -> a -> a
- Int
i) forall a. Num a => a -> a -> a
- Int
1) [a]
ys

lookupWithDefault :: forall a. a -> Int -> Seq a -> a
lookupWithDefault a
d Int
idx (Q Int
i [a]
xs [a]
ys Int
j)
  | Int
idx forall a. Ord a => a -> a -> Bool
< Int
i   = forall a. a -> Int -> [a] -> a
L.lookupWithDefault a
d Int
idx [a]
xs
  | Bool
otherwise = forall a. a -> Int -> [a] -> a
L.lookupWithDefault a
d (Int
j forall a. Num a => a -> a -> a
- (Int
idx forall a. Num a => a -> a -> a
- Int
i) forall a. Num a => a -> a -> a
- Int
1) [a]
ys

update :: forall a. Int -> a -> Seq a -> Seq a
update Int
idx a
e q :: Seq a
q@(Q Int
i [a]
xs [a]
ys Int
j)
  | Int
idx forall a. Ord a => a -> a -> Bool
< Int
i = if Int
idx forall a. Ord a => a -> a -> Bool
< Int
0 then Seq a
q
             else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i (forall a. Int -> a -> [a] -> [a]
L.update Int
idx a
e [a]
xs) [a]
ys Int
j
  | Bool
otherwise = let k' :: Int
k' = Int
j forall a. Num a => a -> a -> a
- (Int
idx forall a. Num a => a -> a -> a
- Int
i) forall a. Num a => a -> a -> a
- Int
1
                in if Int
k' forall a. Ord a => a -> a -> Bool
< Int
0 then Seq a
q
                   else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs (forall a. Int -> a -> [a] -> [a]
L.update Int
k' a
e [a]
ys) Int
j

adjust :: forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust a -> a
f Int
idx q :: Seq a
q@(Q Int
i [a]
xs [a]
ys Int
j)
  | Int
idx forall a. Ord a => a -> a -> Bool
< Int
i = if Int
idx forall a. Ord a => a -> a -> Bool
< Int
0 then Seq a
q
             else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i (forall a. (a -> a) -> Int -> [a] -> [a]
L.adjust a -> a
f Int
idx [a]
xs) [a]
ys Int
j
  | Bool
otherwise = let k' :: Int
k' = Int
j forall a. Num a => a -> a -> a
- (Int
idx forall a. Num a => a -> a -> a
- Int
i) forall a. Num a => a -> a -> a
- Int
1
                in if Int
k' forall a. Ord a => a -> a -> Bool
< Int
0 then Seq a
q
                   else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs (forall a. (a -> a) -> Int -> [a] -> [a]
L.adjust a -> a
f Int
k' [a]
ys) Int
j

{-
could do
  mapWithIndex   :: (Int -> a -> b) -> s a -> s b
  foldrWithIndex :: (Int -> a -> b -> b) -> b -> s a -> b
  foldlWithIndex :: (b -> Int -> a -> b) -> b -> s a -> b
but don't bother for now
-}

take :: forall a. Int -> Seq a -> Seq a
take Int
len q :: Seq a
q@(Q Int
i [a]
xs [a]
ys Int
j) =
  if Int
len forall a. Ord a => a -> a -> Bool
<= Int
i then
    if Int
len forall a. Ord a => a -> a -> Bool
<= Int
0 then forall a. Seq a
empty
    else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
len (forall a. Int -> [a] -> [a]
L.take Int
len [a]
xs) [] Int
0
  else let len' :: Int
len' = Int
len forall a. Num a => a -> a -> a
- Int
i in
    if Int
len' forall a. Ord a => a -> a -> Bool
>= Int
j then Seq a
q
    else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs (forall a. Int -> [a] -> [a]
L.drop (Int
j forall a. Num a => a -> a -> a
- Int
len') [a]
ys) Int
len'

drop :: forall a. Int -> Seq a -> Seq a
drop Int
len q :: Seq a
q@(Q Int
i [a]
xs [a]
ys Int
j) =
  if Int
len forall a. Ord a => a -> a -> Bool
<= Int
i then
    if Int
len forall a. Ord a => a -> a -> Bool
<= Int
0 then Seq a
q
    else forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ (Int
i forall a. Num a => a -> a -> a
- Int
len) (forall a. Int -> [a] -> [a]
L.drop Int
len [a]
xs) [a]
ys Int
j
  else let len' :: Int
len' = Int
len forall a. Num a => a -> a -> a
- Int
i in
    if Int
len' forall a. Ord a => a -> a -> Bool
>= Int
j then forall a. Seq a
empty
    else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
j forall a. Num a => a -> a -> a
- Int
len') (forall a. [a] -> [a]
L.reverse (forall a. Int -> [a] -> [a]
L.take (Int
j forall a. Num a => a -> a -> a
- Int
len') [a]
ys)) [] Int
0
  -- could write more efficient version of reverse (take ...)

splitAt :: forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt Int
idx q :: Seq a
q@(Q Int
i [a]
xs [a]
ys Int
j) =
  if Int
idx forall a. Ord a => a -> a -> Bool
<= Int
i then
    if Int
idx forall a. Ord a => a -> a -> Bool
<= Int
0 then (forall a. Seq a
empty, Seq a
q)
    else let ([a]
xs',[a]
xs'') = forall a. Int -> [a] -> ([a], [a])
L.splitAt Int
idx [a]
xs
         in (forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
idx [a]
xs' [] Int
0, forall a. Int -> [a] -> [a] -> Int -> Seq a
makeQ (Int
i forall a. Num a => a -> a -> a
- Int
idx) [a]
xs'' [a]
ys Int
j)
  else let idx' :: Int
idx' = Int
idx forall a. Num a => a -> a -> a
- Int
i in
    if Int
idx' forall a. Ord a => a -> a -> Bool
>= Int
j then (Seq a
q, forall a. Seq a
empty)
    else let ([a]
ys', [a]
ys'') = forall a. Int -> [a] -> ([a], [a])
L.splitAt (Int
j forall a. Num a => a -> a -> a
- Int
idx') [a]
ys
         in (forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs [a]
ys'' Int
idx', forall a. Int -> [a] -> [a] -> Int -> Seq a
Q (Int
j forall a. Num a => a -> a -> a
- Int
idx') (forall a. [a] -> [a]
L.reverse [a]
ys') [] Int
0)
      -- could do splitAt followed by reverse more efficiently...


strict :: forall a. Seq a -> Seq a
strict l :: Seq a
l@(Q Int
_ [a]
xs [a]
ys Int
_) = forall a. [a] -> [a]
L.strict [a]
xs seq :: forall a b. a -> b -> b
`seq` forall a. [a] -> [a]
L.strict [a]
ys seq :: forall a b. a -> b -> b
`seq` Seq a
l
strictWith :: forall a b. (a -> b) -> Seq a -> Seq a
strictWith a -> b
f l :: Seq a
l@(Q Int
_ [a]
xs [a]
ys Int
_) = forall a b. (a -> b) -> [a] -> [a]
L.strictWith a -> b
f [a]
xs seq :: forall a b. a -> b -> b
`seq` forall a b. (a -> b) -> [a] -> [a]
L.strictWith a -> b
f [a]
ys seq :: forall a b. a -> b -> b
`seq` Seq a
l

-- the remaining functions all use defaults

concat :: forall a. Seq (Seq a) -> Seq a
concat = forall (s :: * -> *) a. Sequence s => s (s a) -> s a
concatUsingFoldr
concatMap :: forall a b. (a -> Seq b) -> Seq a -> Seq b
concatMap = forall (s :: * -> *) a b. Sequence s => (a -> s b) -> s a -> s b
concatMapUsingFoldr
reducer :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducer = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducerUsingReduce1
reducel :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducel = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducelUsingReduce1
reduce1 :: forall a. (a -> a -> a) -> Seq a -> a
reduce1 = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
reduce1UsingLists
reducer' :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducer' = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducer'UsingReduce1'
reducel' :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducel' = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducel'UsingReduce1'
reduce1' :: forall a. (a -> a -> a) -> Seq a -> a
reduce1' = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
reduce1'UsingLists
inBounds :: forall a. Int -> Seq a -> Bool
inBounds = forall (s :: * -> *) a. Sequence s => Int -> s a -> Bool
inBoundsUsingSize
mapWithIndex :: forall a b. (Int -> a -> b) -> Seq a -> Seq b
mapWithIndex = forall (s :: * -> *) a b.
Sequence s =>
(Int -> a -> b) -> s a -> s b
mapWithIndexUsingLists
foldrWithIndex :: forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
foldrWithIndex  = forall (s :: * -> *) a b.
Sequence s =>
(Int -> a -> b -> b) -> b -> s a -> b
foldrWithIndexUsingLists
foldrWithIndex' :: forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
foldrWithIndex' = forall (s :: * -> *) a b.
Sequence s =>
(Int -> a -> b -> b) -> b -> s a -> b
foldrWithIndex'UsingLists
foldlWithIndex :: forall b a. (b -> Int -> a -> b) -> b -> Seq a -> b
foldlWithIndex  = forall (s :: * -> *) b a.
Sequence s =>
(b -> Int -> a -> b) -> b -> s a -> b
foldlWithIndexUsingLists
foldlWithIndex' :: forall b a. (b -> Int -> a -> b) -> b -> Seq a -> b
foldlWithIndex' = forall (s :: * -> *) b a.
Sequence s =>
(b -> Int -> a -> b) -> b -> s a -> b
foldlWithIndex'UsingLists
subseq :: forall a. Int -> Int -> Seq a -> Seq a
subseq = forall (s :: * -> *) a. Sequence s => Int -> Int -> s a -> s a
subseqDefault
filter :: forall a. (a -> Bool) -> Seq a -> Seq a
filter = forall (s :: * -> *) a. Sequence s => (a -> Bool) -> s a -> s a
filterUsingLists
partition :: forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
partition = forall (s :: * -> *) a.
Sequence s =>
(a -> Bool) -> s a -> (s a, s a)
partitionUsingLists
takeWhile :: forall a. (a -> Bool) -> Seq a -> Seq a
takeWhile = forall (s :: * -> *) a. Sequence s => (a -> Bool) -> s a -> s a
takeWhileUsingLview
dropWhile :: forall a. (a -> Bool) -> Seq a -> Seq a
dropWhile = forall (s :: * -> *) a. Sequence s => (a -> Bool) -> s a -> s a
dropWhileUsingLview
splitWhile :: forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
splitWhile = forall (s :: * -> *) a.
Sequence s =>
(a -> Bool) -> s a -> (s a, s a)
splitWhileUsingLview
zip :: forall a b. Seq a -> Seq b -> Seq (a, b)
zip = forall (s :: * -> *) a b. Sequence s => s a -> s b -> s (a, b)
zipUsingLists
zip3 :: forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3 = forall (s :: * -> *) a b c.
Sequence s =>
s a -> s b -> s c -> s (a, b, c)
zip3UsingLists
zipWith :: forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith = forall (s :: * -> *) a b c.
Sequence s =>
(a -> b -> c) -> s a -> s b -> s c
zipWithUsingLists
zipWith3 :: forall a b c d.
(a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
zipWith3 = forall (s :: * -> *) a b c d.
Sequence s =>
(a -> b -> c -> d) -> s a -> s b -> s c -> s d
zipWith3UsingLists
unzip :: forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip = forall (s :: * -> *) a b. Sequence s => s (a, b) -> (s a, s b)
unzipUsingLists
unzip3 :: forall a b c. Seq (a, b, c) -> (Seq a, Seq b, Seq c)
unzip3 = forall (s :: * -> *) a b c.
Sequence s =>
s (a, b, c) -> (s a, s b, s c)
unzip3UsingLists
unzipWith :: forall a b c. (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith = forall (s :: * -> *) a b c.
Sequence s =>
(a -> b) -> (a -> c) -> s a -> (s b, s c)
unzipWithUsingLists
unzipWith3 :: forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
unzipWith3 = forall (s :: * -> *) a b c d.
Sequence s =>
(a -> b) -> (a -> c) -> (a -> d) -> s a -> (s b, s c, s d)
unzipWith3UsingLists

-- instances

instance S.Sequence Seq where
  {lcons :: forall a. a -> Seq a -> Seq a
lcons = forall a. a -> Seq a -> Seq a
lcons; rcons :: forall a. a -> Seq a -> Seq a
rcons = forall a. a -> Seq a -> Seq a
rcons;
   lview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview = forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview; lhead :: forall a. Seq a -> a
lhead = forall a. Seq a -> a
lhead; ltail :: forall a. Seq a -> Seq a
ltail = forall a. Seq a -> Seq a
ltail;
   lheadM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m a
lheadM = forall (m :: * -> *) a. MonadFail m => Seq a -> m a
lheadM; ltailM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
ltailM = forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
ltailM; rheadM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m a
rheadM = forall (m :: * -> *) a. MonadFail m => Seq a -> m a
rheadM; rtailM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
rtailM = forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
rtailM;
   rview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
rview = forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
rview; rhead :: forall a. Seq a -> a
rhead = forall a. Seq a -> a
rhead; rtail :: forall a. Seq a -> Seq a
rtail = forall a. Seq a -> Seq a
rtail; null :: forall a. Seq a -> Bool
null = forall a. Seq a -> Bool
null;
   size :: forall a. Seq a -> Int
size = forall a. Seq a -> Int
size; concat :: forall a. Seq (Seq a) -> Seq a
concat = forall a. Seq (Seq a) -> Seq a
concat; reverse :: forall a. Seq a -> Seq a
reverse = forall a. Seq a -> Seq a
reverse;
   reverseOnto :: forall a. Seq a -> Seq a -> Seq a
reverseOnto = forall a. Seq a -> Seq a -> Seq a
reverseOnto; fromList :: forall a. [a] -> Seq a
fromList = forall a. [a] -> Seq a
fromList; toList :: forall a. Seq a -> [a]
toList = forall a. Seq a -> [a]
toList;
   fold :: forall a b. (a -> b -> b) -> b -> Seq a -> b
fold = forall a b. (a -> b -> b) -> b -> Seq a -> b
fold; fold' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
fold' = forall a b. (a -> b -> b) -> b -> Seq a -> b
fold'; fold1 :: forall a. (a -> a -> a) -> Seq a -> a
fold1 = forall a. (a -> a -> a) -> Seq a -> a
fold1; fold1' :: forall a. (a -> a -> a) -> Seq a -> a
fold1' = forall a. (a -> a -> a) -> Seq a -> a
fold1';
   foldr :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr = forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr; foldr' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr' = forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr'; foldl :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl = forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl; foldl' :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl' = forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl';
   foldr1 :: forall a. (a -> a -> a) -> Seq a -> a
foldr1 = forall a. (a -> a -> a) -> Seq a -> a
foldr1; foldr1' :: forall a. (a -> a -> a) -> Seq a -> a
foldr1' = forall a. (a -> a -> a) -> Seq a -> a
foldr1'; foldl1 :: forall a. (a -> a -> a) -> Seq a -> a
foldl1 = forall a. (a -> a -> a) -> Seq a -> a
foldl1; foldl1' :: forall a. (a -> a -> a) -> Seq a -> a
foldl1' = forall a. (a -> a -> a) -> Seq a -> a
foldl1';
   reducer :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducer = forall a. (a -> a -> a) -> a -> Seq a -> a
reducer; reducer' :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducer' = forall a. (a -> a -> a) -> a -> Seq a -> a
reducer';
   reducel :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducel = forall a. (a -> a -> a) -> a -> Seq a -> a
reducel; reducel' :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducel' = forall a. (a -> a -> a) -> a -> Seq a -> a
reducel'; reduce1 :: forall a. (a -> a -> a) -> Seq a -> a
reduce1 = forall a. (a -> a -> a) -> Seq a -> a
reduce1; reduce1' :: forall a. (a -> a -> a) -> Seq a -> a
reduce1' = forall a. (a -> a -> a) -> Seq a -> a
reduce1';
   copy :: forall a. Int -> a -> Seq a
copy = forall a. Int -> a -> Seq a
copy; inBounds :: forall a. Int -> Seq a -> Bool
inBounds = forall a. Int -> Seq a -> Bool
inBounds; lookup :: forall a. Int -> Seq a -> a
lookup = forall a. Int -> Seq a -> a
lookup;
   lookupM :: forall (m :: * -> *) a. MonadFail m => Int -> Seq a -> m a
lookupM = forall (m :: * -> *) a. MonadFail m => Int -> Seq a -> m a
lookupM; lookupWithDefault :: forall a. a -> Int -> Seq a -> a
lookupWithDefault = forall a. a -> Int -> Seq a -> a
lookupWithDefault;
   update :: forall a. Int -> a -> Seq a -> Seq a
update = forall a. Int -> a -> Seq a -> Seq a
update; adjust :: forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust = forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust; mapWithIndex :: forall a b. (Int -> a -> b) -> Seq a -> Seq b
mapWithIndex = forall a b. (Int -> a -> b) -> Seq a -> Seq b
mapWithIndex;
   foldrWithIndex :: forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
foldrWithIndex = forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
foldrWithIndex; foldlWithIndex :: forall b a. (b -> Int -> a -> b) -> b -> Seq a -> b
foldlWithIndex = forall b a. (b -> Int -> a -> b) -> b -> Seq a -> b
foldlWithIndex;
   foldrWithIndex' :: forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
foldrWithIndex' = forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
foldrWithIndex'; foldlWithIndex' :: forall b a. (b -> Int -> a -> b) -> b -> Seq a -> b
foldlWithIndex' = forall b a. (b -> Int -> a -> b) -> b -> Seq a -> b
foldlWithIndex';
   take :: forall a. Int -> Seq a -> Seq a
take = forall a. Int -> Seq a -> Seq a
take; drop :: forall a. Int -> Seq a -> Seq a
drop = forall a. Int -> Seq a -> Seq a
drop; splitAt :: forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt = forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt; subseq :: forall a. Int -> Int -> Seq a -> Seq a
subseq = forall a. Int -> Int -> Seq a -> Seq a
subseq;
   filter :: forall a. (a -> Bool) -> Seq a -> Seq a
filter = forall a. (a -> Bool) -> Seq a -> Seq a
filter; partition :: forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
partition = forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
partition; takeWhile :: forall a. (a -> Bool) -> Seq a -> Seq a
takeWhile = forall a. (a -> Bool) -> Seq a -> Seq a
takeWhile;
   dropWhile :: forall a. (a -> Bool) -> Seq a -> Seq a
dropWhile = forall a. (a -> Bool) -> Seq a -> Seq a
dropWhile; splitWhile :: forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
splitWhile = forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
splitWhile; zip :: forall a b. Seq a -> Seq b -> Seq (a, b)
zip = forall a b. Seq a -> Seq b -> Seq (a, b)
zip;
   zip3 :: forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3 = forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3; zipWith :: forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith = forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith; zipWith3 :: forall a b c d.
(a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
zipWith3 = forall a b c d.
(a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
zipWith3; unzip :: forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip = forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip;
   unzip3 :: forall a b c. Seq (a, b, c) -> (Seq a, Seq b, Seq c)
unzip3 = forall a b c. Seq (a, b, c) -> (Seq a, Seq b, Seq c)
unzip3; unzipWith :: forall a b c. (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith = forall a b c. (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith; unzipWith3 :: forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
unzipWith3 = forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
unzipWith3;
   strict :: forall a. Seq a -> Seq a
strict = forall a. Seq a -> Seq a
strict; strictWith :: forall a b. (a -> b) -> Seq a -> Seq a
strictWith = forall a b. (a -> b) -> Seq a -> Seq a
strictWith;
   structuralInvariant :: forall a. Seq a -> Bool
structuralInvariant = forall a. Seq a -> Bool
structuralInvariant; instanceName :: forall a. Seq a -> String
instanceName Seq a
_ = String
moduleName}

instance Functor Seq where
  fmap :: forall a b. (a -> b) -> Seq a -> Seq b
fmap = forall a b. (a -> b) -> Seq a -> Seq b
map

instance App.Alternative Seq where
  empty :: forall a. Seq a
empty = forall a. Seq a
empty
  <|> :: forall a. Seq a -> Seq a -> Seq a
(<|>) = forall a. Seq a -> Seq a -> Seq a
append

instance App.Applicative Seq where
  pure :: forall a. a -> Seq a
pure = forall (m :: * -> *) a. Monad m => a -> m a
return
  Seq (a -> b)
x <*> :: forall a b. Seq (a -> b) -> Seq a -> Seq b
<*> Seq a
y = do
     a -> b
x' <- Seq (a -> b)
x
     a
y' <- Seq a
y
     forall (m :: * -> *) a. Monad m => a -> m a
return (a -> b
x' a
y')

instance Monad Seq where
  return :: forall a. a -> Seq a
return = forall a. a -> Seq a
singleton
  Seq a
xs >>= :: forall a b. Seq a -> (a -> Seq b) -> Seq b
>>= a -> Seq b
k = forall a b. (a -> Seq b) -> Seq a -> Seq b
concatMap a -> Seq b
k Seq a
xs

instance MonadPlus Seq where
  mplus :: forall a. Seq a -> Seq a -> Seq a
mplus = forall a. Seq a -> Seq a -> Seq a
append
  mzero :: forall a. Seq a
mzero = forall a. Seq a
empty

instance Eq a => Eq (Seq a) where
  Seq a
q1 == :: Seq a -> Seq a -> Bool
== Seq a
q2 =
    (forall a. Seq a -> Int
size Seq a
q1 forall a. Eq a => a -> a -> Bool
== forall a. Seq a -> Int
size Seq a
q2) Bool -> Bool -> Bool
&& (forall a. Seq a -> [a]
toList Seq a
q1 forall a. Eq a => a -> a -> Bool
== forall a. Seq a -> [a]
toList Seq a
q2)

instance Ord a => Ord (Seq a) where
  compare :: Seq a -> Seq a -> Ordering
compare = forall a (s :: * -> *).
(Ord a, Sequence s) =>
s a -> s a -> Ordering
defaultCompare

instance Show a => Show (Seq a) where
  showsPrec :: Int -> Seq a -> ShowS
showsPrec = forall a (s :: * -> *). (Show a, Sequence s) => Int -> s a -> ShowS
showsPrecUsingToList

instance Read a => Read (Seq a) where
  readsPrec :: Int -> ReadS (Seq a)
readsPrec = forall a (s :: * -> *). (Read a, Sequence s) => Int -> ReadS (s a)
readsPrecUsingFromList

instance Arbitrary a => Arbitrary (Seq a) where
  arbitrary :: Gen (Seq a)
arbitrary =
    do [a]
xs <- forall a. Arbitrary a => Gen a
arbitrary
       [a]
ys <- forall a. Arbitrary a => Gen a
arbitrary
       forall (m :: * -> *) a. Monad m => a -> m a
return (let i :: Int
i = forall a. [a] -> Int
L.size [a]
xs
                   j :: Int
j = forall a. [a] -> Int
L.size [a]
ys
               in if Int
i forall a. Ord a => a -> a -> Bool
>= Int
j then forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
i [a]
xs [a]
ys Int
j else forall a. Int -> [a] -> [a] -> Int -> Seq a
Q Int
j [a]
ys [a]
xs Int
i)

instance CoArbitrary a => CoArbitrary (Seq a) where
  coarbitrary :: forall b. Seq a -> Gen b -> Gen b
coarbitrary (Q Int
_ [a]
xs [a]
ys Int
_) = forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary [a]
xs forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary [a]
ys

instance Semigroup (Seq a) where
  <> :: Seq a -> Seq a -> Seq a
(<>) = forall a. Seq a -> Seq a -> Seq a
append
instance Monoid (Seq a) where
  mempty :: Seq a
mempty  = forall a. Seq a
empty
  mappend :: Seq a -> Seq a -> Seq a
mappend = forall a. Semigroup a => a -> a -> a
(SG.<>)