module Data.Edison.Seq.BraunSeq (
Seq,
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,
structuralInvariant,
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 qualified Control.Monad.Fail as Fail
import Control.Monad.Identity
import Data.Maybe
import Data.Monoid
import Data.Semigroup as SG
import Test.QuickCheck
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
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.BraunSeq"
data Seq a = E | B a (Seq a) (Seq a) deriving (Seq a -> Seq a -> Bool
forall a. Eq a => Seq a -> Seq a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Seq a -> Seq a -> Bool
$c/= :: forall a. Eq a => Seq a -> Seq a -> Bool
== :: Seq a -> Seq a -> Bool
$c== :: forall a. Eq a => Seq a -> Seq a -> Bool
Eq)
half :: Int -> Int
half :: Int -> Int
half Int
n = Int
n forall a. Integral a => a -> a -> a
`quot` Int
2
empty :: forall a. Seq a
empty = forall a. Seq a
E
singleton :: forall a. a -> Seq a
singleton a
x = forall a. a -> Seq a -> Seq a -> Seq a
B a
x forall a. Seq a
E forall a. Seq a
E
lcons :: forall a. a -> Seq a -> Seq a
lcons a
x Seq a
E = forall a. a -> Seq a
singleton a
x
lcons a
x (B a
y Seq a
a Seq a
b) = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (forall a. a -> Seq a -> Seq a
lcons a
y Seq a
b) Seq a
a
rcons :: forall a. a -> Seq a -> Seq a
rcons a
y Seq a
ys = Int -> Seq a -> Seq a
insAt (forall a. Seq a -> Int
size Seq a
ys) Seq a
ys
where insAt :: Int -> Seq a -> Seq a
insAt Int
0 Seq a
_ = forall a. a -> Seq a
singleton a
y
insAt Int
i (B a
x Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
i = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a
insAt (Int -> Int
half Int
i) Seq a
a) Seq a
b
| Bool
otherwise = forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a (Int -> Seq a -> Seq a
insAt (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1) Seq a
b)
insAt Int
_ Seq a
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.rcons: bug. Impossible case!"
append :: forall a. Seq a -> Seq a -> Seq a
append Seq a
xs Seq a
E = Seq a
xs
append Seq a
xs Seq a
ys = forall {a}. Int -> Seq a -> Seq a -> Seq a
app (forall a. Seq a -> Int
size Seq a
xs) Seq a
xs Seq a
ys
where app :: Int -> Seq a -> Seq a -> Seq a
app Int
0 Seq a
_ Seq a
ys = Seq a
ys
app Int
_ Seq a
xs Seq a
E = Seq a
xs
app Int
n (B a
x Seq a
a Seq a
b) (B a
y Seq a
c Seq a
d)
| forall a. Integral a => a -> Bool
odd Int
n = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a -> Seq a
app Int
m Seq a
a (forall a. a -> Seq a -> Seq a
lcons a
y Seq a
d)) (Int -> Seq a -> Seq a -> Seq a
app Int
m Seq a
b Seq a
c)
| Bool
otherwise = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a -> Seq a
app Int
m Seq a
a Seq a
c) (Int -> Seq a -> Seq a -> Seq a
app (Int
mforall a. Num a => a -> a -> a
-Int
1) Seq a
b (forall a. a -> Seq a -> Seq a
lcons a
y Seq a
d))
where m :: Int
m = Int -> Int
half Int
n
app Int
_ Seq a
_ Seq a
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.append: bug!"
lview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview Seq a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.lview: empty sequence"
lview (B a
x Seq a
a Seq a
b) = forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, forall a. Seq a -> Seq a -> Seq a
combine Seq a
a Seq a
b)
combine :: Seq a -> Seq a -> Seq a
combine :: forall a. Seq a -> Seq a -> Seq a
combine Seq a
E Seq a
_ = forall a. Seq a
E
combine (B a
x Seq a
a Seq a
b) Seq a
c = forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
c (forall a. Seq a -> Seq a -> Seq a
combine Seq a
a Seq a
b)
lhead :: forall a. Seq a -> a
lhead Seq a
E = forall a. HasCallStack => String -> a
error String
"BraunSeq.lhead: empty sequence"
lhead (B a
x Seq a
_ Seq a
_) = a
x
lheadM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m a
lheadM Seq a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.lheadM: empty sequence"
lheadM (B a
x Seq a
_ Seq a
_) = forall (m :: * -> *) a. Monad m => a -> m a
return a
x
ltail :: forall a. Seq a -> Seq a
ltail Seq a
E = forall a. HasCallStack => String -> a
error String
"BraunSeq.ltail: empty sequence"
ltail (B a
_ Seq a
a Seq a
b) = forall a. Seq a -> Seq a -> Seq a
combine Seq a
a Seq a
b
ltailM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
ltailM Seq a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.ltailM: empty sequence"
ltailM (B a
_ Seq a
a Seq a
b) = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Seq a -> Seq a -> Seq a
combine Seq a
a Seq a
b)
delAt :: Int -> Seq a -> Seq a
delAt :: forall a. Int -> Seq a -> Seq a
delAt Int
0 Seq a
_ = forall a. Seq a
E
delAt Int
i (B a
x Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
i = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (forall a. Int -> Seq a -> Seq a
delAt (Int -> Int
half Int
i) Seq a
a) Seq a
b
| Bool
otherwise = forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a (forall a. Int -> Seq a -> Seq a
delAt (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1) Seq a
b)
delAt Int
_ Seq a
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.delAt: bug. Impossible case!"
rview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
rview Seq a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.rview: empty sequence"
rview Seq a
xs = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> Seq a -> a
lookup Int
m Seq a
xs, forall a. Int -> Seq a -> Seq a
delAt Int
m Seq a
xs)
where m :: Int
m = forall a. Seq a -> Int
size Seq a
xs forall a. Num a => a -> a -> a
- Int
1
rhead :: forall a. Seq a -> a
rhead Seq a
E = forall a. HasCallStack => String -> a
error String
"BraunSeq.rhead: empty sequence"
rhead Seq a
xs = forall a. Int -> Seq a -> a
lookup (forall a. Seq a -> Int
size Seq a
xs forall a. Num a => a -> a -> a
- Int
1) Seq a
xs
rheadM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m a
rheadM Seq a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.rheadM: empty sequence"
rheadM Seq a
xs = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> Seq a -> a
lookup (forall a. Seq a -> Int
size Seq a
xs forall a. Num a => a -> a -> a
- Int
1) Seq a
xs)
rtail :: forall a. Seq a -> Seq a
rtail Seq a
E = forall a. HasCallStack => String -> a
error String
"BraunSeq.rtail: empty sequence"
rtail Seq a
xs = forall a. Int -> Seq a -> Seq a
delAt (forall a. Seq a -> Int
size Seq a
xs forall a. Num a => a -> a -> a
- Int
1) Seq a
xs
rtailM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
rtailM Seq a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.rtailM: empty sequence"
rtailM Seq a
xs = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> Seq a -> Seq a
delAt (forall a. Seq a -> Int
size Seq a
xs forall a. Num a => a -> a -> a
- Int
1) Seq a
xs)
null :: forall a. Seq a -> Bool
null Seq a
E = Bool
True
null Seq a
_ = Bool
False
size :: forall a. Seq a -> Int
size Seq a
E = Int
0
size (B a
_ Seq a
a Seq a
b) = Int
1 forall a. Num a => a -> a -> a
+ Int
n forall a. Num a => a -> a -> a
+ Int
n forall a. Num a => a -> a -> a
+ forall {a} {a}. Num a => Int -> Seq a -> a
diff Int
n Seq a
a
where n :: Int
n = forall a. Seq a -> Int
size Seq a
b
diff :: Int -> Seq a -> a
diff Int
0 Seq a
E = a
0
diff Int
0 (B a
_ Seq a
_ Seq a
_) = a
1
diff Int
i (B a
_ Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
i = Int -> Seq a -> a
diff (Int -> Int
half Int
i) Seq a
a
| Bool
otherwise = Int -> Seq a -> a
diff (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1) Seq a
b
diff Int
_ Seq a
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.size: bug. Impossible case in diff!"
reverse :: forall a. Seq a -> Seq a
reverse Seq a
xs = forall a. Int -> Seq a -> Seq a
rev00 (forall a. Seq a -> Int
size Seq a
xs) Seq a
xs
where
rev00 :: Int -> Seq a -> Seq a
rev00 Int
n Seq a
xs
| Int
n forall a. Ord a => a -> a -> Bool
<= Int
1 = Seq a
xs
rev00 Int
n (B a
x Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
n = let a' :: Seq a
a' = Int -> Seq a -> Seq a
rev00 Int
m Seq a
a
(a
x',Seq a
b') = forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
x Seq a
b in forall a. a -> Seq a -> Seq a -> Seq a
B a
x' Seq a
a' Seq a
b'
| Bool
otherwise = let (a
x',Seq a
a') = forall {a}. Int -> Seq a -> (a, Seq a)
rev01 Int
m Seq a
a
b' :: Seq a
b' = forall {a}. Int -> a -> Seq a -> Seq a
rev10 (Int
mforall a. Num a => a -> a -> a
-Int
1) a
x Seq a
b in forall a. a -> Seq a -> Seq a -> Seq a
B a
x' Seq a
b' Seq a
a'
where m :: Int
m = Int -> Int
half Int
n
rev00 Int
_ Seq a
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.reverse: bug!"
rev11 :: Int -> a -> Seq a -> (a, Seq a)
rev11 Int
_ a
x Seq a
E = (a
x,forall a. Seq a
E)
rev11 Int
n a
x (B a
y Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
n = let (a
x',Seq a
a') = Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
x Seq a
a
(a
y',Seq a
b') = Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
y Seq a
b in (a
y', forall a. a -> Seq a -> Seq a -> Seq a
B a
x' Seq a
b' Seq a
a')
| Bool
otherwise = let (a
x',Seq a
a') = Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
x Seq a
a
(a
y',Seq a
b') = Int -> a -> Seq a -> (a, Seq a)
rev11 (Int
mforall a. Num a => a -> a -> a
-Int
1) a
y Seq a
b in (a
x', forall a. a -> Seq a -> Seq a -> Seq a
B a
y' Seq a
a' Seq a
b')
where m :: Int
m = Int -> Int
half Int
n
rev01 :: Int -> Seq a -> (a, Seq a)
rev01 Int
_ Seq a
E = forall a. HasCallStack => String -> a
error String
"BraunSeq.reverse: bug!"
rev01 Int
n (B a
x Seq a
a Seq a
b)
| Int
n forall a. Eq a => a -> a -> Bool
== Int
1 = (a
x, forall a. Seq a
E)
| forall a. Integral a => a -> Bool
odd Int
n = let (a
y',Seq a
a') = Int -> Seq a -> (a, Seq a)
rev01 Int
m Seq a
a
(a
x',Seq a
b') = forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
x Seq a
b in (a
x', forall a. a -> Seq a -> Seq a -> Seq a
B a
y' Seq a
b' Seq a
a')
| Bool
otherwise = let (a
y',Seq a
a') = Int -> Seq a -> (a, Seq a)
rev01 Int
m Seq a
a
(a
x',Seq a
b') = forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 (Int
mforall a. Num a => a -> a -> a
-Int
1) a
x Seq a
b in (a
y', forall a. a -> Seq a -> Seq a -> Seq a
B a
x' Seq a
a' Seq a
b')
where m :: Int
m = Int -> Int
half Int
n
rev10 :: Int -> a -> Seq a -> Seq a
rev10 Int
_ a
x Seq a
E = forall a. a -> Seq a -> Seq a -> Seq a
B a
x forall a. Seq a
E forall a. Seq a
E
rev10 Int
n a
x (B a
y Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
n = let a' :: Seq a
a' = Int -> a -> Seq a -> Seq a
rev10 Int
m a
x Seq a
a
(a
y',Seq a
b') = forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
y Seq a
b in forall a. a -> Seq a -> Seq a -> Seq a
B a
y' Seq a
a' Seq a
b'
| Bool
otherwise = let (a
x',Seq a
a') = forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
x Seq a
a
b' :: Seq a
b' = Int -> a -> Seq a -> Seq a
rev10 (Int
mforall a. Num a => a -> a -> a
-Int
1) a
y Seq a
b in forall a. a -> Seq a -> Seq a -> Seq a
B a
x' Seq a
b' Seq a
a'
where m :: Int
m = Int -> Int
half Int
n
fromList :: forall a. [a] -> Seq a
fromList = forall a. [a] -> a
L.lhead forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr forall {a}. (Int, [a]) -> [Seq a] -> [Seq a]
build [forall a. Seq a
E] forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {a}. Int -> [a] -> [(Int, [a])]
rows Int
1
where rows :: Int -> [a] -> [(Int, [a])]
rows Int
_ [] = []
rows Int
k [a]
xs = (Int
k, [a]
ys) forall a. a -> [a] -> [a]
: Int -> [a] -> [(Int, [a])]
rows (Int
kforall a. Num a => a -> a -> a
+Int
k) [a]
zs
where ([a]
ys,[a]
zs) = forall a. Int -> [a] -> ([a], [a])
L.splitAt Int
k [a]
xs
build :: (Int, [a]) -> [Seq a] -> [Seq a]
build (Int
k,[a]
xs) [Seq a]
ts = forall {a}. [a] -> [Seq a] -> [Seq a] -> [Seq a]
zipWithB [a]
xs [Seq a]
ts1 [Seq a]
ts2
where ([Seq a]
ts1, [Seq a]
ts2) = forall a. Int -> [a] -> ([a], [a])
L.splitAt Int
k [Seq a]
ts
zipWithB :: [a] -> [Seq a] -> [Seq a] -> [Seq a]
zipWithB [] [Seq a]
_ [Seq a]
_ = []
zipWithB (a
x:[a]
xs) [] [Seq a]
_ = forall a. a -> Seq a
singleton a
x forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
L.map forall a. a -> Seq a
singleton [a]
xs
zipWithB (a
x:[a]
xs) (Seq a
t:[Seq a]
ts) [] = forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
t forall a. Seq a
E forall a. a -> [a] -> [a]
: [a] -> [Seq a] -> [Seq a] -> [Seq a]
zipWithB [a]
xs [Seq a]
ts []
zipWithB (a
x:[a]
xs) (Seq a
t1:[Seq a]
ts1) (Seq a
t2:[Seq a]
ts2) = forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
t1 Seq a
t2 forall a. a -> [a] -> [a]
: [a] -> [Seq a] -> [Seq a] -> [Seq a]
zipWithB [a]
xs [Seq a]
ts1 [Seq a]
ts2
toList :: forall a. Seq a -> [a]
toList Seq a
E = []
toList Seq a
t = forall {a}. [Seq a] -> [a]
tol [Seq a
t]
where tol :: [Seq a] -> [a]
tol [] = []
tol [Seq a]
ts = [a]
xs forall a. [a] -> [a] -> [a]
++ [Seq a] -> [a]
tol ([Seq a]
ts1 forall a. [a] -> [a] -> [a]
++ [Seq a]
ts2)
where xs :: [a]
xs = forall a b. (a -> b) -> [a] -> [b]
L.map forall a. Seq a -> a
root [Seq a]
ts
([Seq a]
ts1,[Seq a]
ts2) = forall {a}. [Seq a] -> ([Seq a], [Seq a])
children [Seq a]
ts
children :: [Seq a] -> ([Seq a], [Seq a])
children [] = ([],[])
children (B a
_ Seq a
E Seq a
_ : [Seq a]
_) = ([],[])
children (B a
_ Seq a
a Seq a
E : [Seq a]
ts) = (Seq a
a forall a. a -> [a] -> [a]
: forall {a}. [Seq a] -> [Seq a]
leftChildren [Seq a]
ts, [])
children (B a
_ Seq a
a Seq a
b : [Seq a]
ts) = (Seq a
a forall a. a -> [a] -> [a]
: [Seq a]
ts1, Seq a
b forall a. a -> [a] -> [a]
: [Seq a]
ts2)
where ([Seq a]
ts1, [Seq a]
ts2) = [Seq a] -> ([Seq a], [Seq a])
children [Seq a]
ts
children [Seq a]
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.toList: bug!"
leftChildren :: [Seq a] -> [Seq a]
leftChildren [] = []
leftChildren (B a
_ Seq a
E Seq a
_ : [Seq a]
_) = []
leftChildren (B a
_ Seq a
a Seq a
_ : [Seq a]
ts) = Seq a
a forall a. a -> [a] -> [a]
: [Seq a] -> [Seq a]
leftChildren [Seq a]
ts
leftChildren [Seq a]
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.toList: bug!"
root :: Seq a -> a
root (B a
x Seq a
_ Seq a
_) = a
x
root Seq a
_ = forall a. HasCallStack => String -> a
error String
"BraunSeq.toList: bug!"
(B a
_ Seq a
a Seq a
_) = Seq a
a
map :: forall a b. (a -> b) -> Seq a -> Seq b
map a -> b
_ Seq a
E = forall a. Seq a
E
map a -> b
f (B a
x Seq a
a Seq a
b) = forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b
f a
x) (forall a b. (a -> b) -> Seq a -> Seq b
map a -> b
f Seq a
a) (forall a b. (a -> b) -> Seq a -> Seq b
map a -> b
f Seq a
b)
copy :: forall a. Int -> a -> Seq a
copy Int
n a
x = if Int
n forall a. Ord a => a -> a -> Bool
<= Int
0 then forall a. Seq a
empty else forall a b. (a, b) -> a
fst (Int -> (Seq a, Seq a)
copy2 Int
n)
where copy2 :: Int -> (Seq a, Seq a)
copy2 Int
n
| forall a. Integral a => a -> Bool
odd Int
n = (forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a Seq a
a, forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
b Seq a
a)
| Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = (forall a. Seq a
E, forall a. a -> Seq a
singleton a
x)
| Bool
otherwise = (forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
b Seq a
a, forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
b Seq a
b)
where (Seq a
a, Seq a
b) = Int -> (Seq a, Seq a)
copy2 (Int -> Int
half (Int
nforall a. Num a => a -> a -> a
-Int
1))
inBounds :: forall a. Int -> Seq a -> Bool
inBounds Int
i Seq a
xs = (Int
i forall a. Ord a => a -> a -> Bool
>= Int
0) Bool -> Bool -> Bool
&& forall {a}. Seq a -> Int -> Bool
inb Seq a
xs Int
i
where inb :: Seq a -> Int -> Bool
inb Seq a
E Int
_ = Bool
False
inb (B a
_ Seq a
a Seq a
b) Int
i
| forall a. Integral a => a -> Bool
odd Int
i = Seq a -> Int -> Bool
inb Seq a
a (Int -> Int
half Int
i)
| Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = Bool
True
| Bool
otherwise = Seq a -> Int -> Bool
inb Seq a
b (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1)
lookup :: forall a. Int -> Seq a -> a
lookup Int
i Seq a
xs = forall a. Fail a -> a
runFail_ (forall (m :: * -> *) a. MonadFail m => Int -> Seq a -> m a
lookupM Int
i Seq a
xs)
lookupM :: forall (m :: * -> *) a. MonadFail m => Int -> Seq a -> m a
lookupM Int
i Seq a
xs
| Int
i forall a. Ord a => a -> a -> Bool
< Int
0 = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.lookupM: bad subscript"
| Bool
otherwise = forall {a}. Seq a -> Int -> m a
look Seq a
xs Int
i
where look :: Seq a -> Int -> m a
look Seq a
E Int
_ = forall {a}. m a
nothing
look (B a
x Seq a
a Seq a
b) Int
i
| forall a. Integral a => a -> Bool
odd Int
i = Seq a -> Int -> m a
look Seq a
a (Int -> Int
half Int
i)
| Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = forall (m :: * -> *) a. Monad m => a -> m a
return a
x
| Bool
otherwise = Seq a -> Int -> m a
look Seq a
b (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1)
nothing :: m a
nothing = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.lookupM: not found"
lookupWithDefault :: forall a. a -> Int -> Seq a -> a
lookupWithDefault a
d Int
i Seq a
xs = if Int
i forall a. Ord a => a -> a -> Bool
< Int
0 then a
d
else Seq a -> Int -> a
look Seq a
xs Int
i
where look :: Seq a -> Int -> a
look Seq a
E Int
_ = a
d
look (B a
x Seq a
a Seq a
b) Int
i
| forall a. Integral a => a -> Bool
odd Int
i = Seq a -> Int -> a
look Seq a
a (Int -> Int
half Int
i)
| Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = a
x
| Bool
otherwise = Seq a -> Int -> a
look Seq a
b (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1)
update :: forall {a}. Int -> a -> Seq a -> Seq a
update Int
i a
y Seq a
xs = if Int
i forall a. Ord a => a -> a -> Bool
< Int
0 then Seq a
xs else Int -> Seq a -> Seq a
upd Int
i Seq a
xs
where upd :: Int -> Seq a -> Seq a
upd Int
_ Seq a
E = forall a. Seq a
E
upd Int
i (B a
x Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
i = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a
upd (Int -> Int
half Int
i) Seq a
a) Seq a
b
| Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. a -> Seq a -> Seq a -> Seq a
B a
y Seq a
a Seq a
b
| Bool
otherwise = forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a (Int -> Seq a -> Seq a
upd (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1) Seq a
b)
adjust :: forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust a -> a
f Int
i Seq a
xs = if Int
i forall a. Ord a => a -> a -> Bool
< Int
0 then Seq a
xs else Int -> Seq a -> Seq a
adj Int
i Seq a
xs
where adj :: Int -> Seq a -> Seq a
adj Int
_ Seq a
E = forall a. Seq a
E
adj Int
i (B a
x Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
i = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a
adj (Int -> Int
half Int
i) Seq a
a) Seq a
b
| Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. a -> Seq a -> Seq a -> Seq a
B (a -> a
f a
x) Seq a
a Seq a
b
| Bool
otherwise = forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a (Int -> Seq a -> Seq a
adj (Int -> Int
half Int
i forall a. Num a => a -> a -> a
- Int
1) Seq a
b)
mapWithIndex :: forall a b. (Int -> a -> b) -> Seq a -> Seq b
mapWithIndex Int -> a -> b
f Seq a
xs = Int -> Int -> Seq a -> Seq b
mwi Int
0 Int
1 Seq a
xs
where mwi :: Int -> Int -> Seq a -> Seq b
mwi Int
_ Int
_ Seq a
E = forall a. Seq a
E
mwi Int
i Int
d (B a
x Seq a
a Seq a
b) = forall a. a -> Seq a -> Seq a -> Seq a
B (Int -> a -> b
f Int
i a
x) (Int -> Int -> Seq a -> Seq b
mwi (Int
iforall a. Num a => a -> a -> a
+Int
d) Int
dd Seq a
a) (Int -> Int -> Seq a -> Seq b
mwi (Int
iforall a. Num a => a -> a -> a
+Int
dd) Int
dd Seq a
b)
where dd :: Int
dd = Int
dforall a. Num a => a -> a -> a
+Int
d
take :: forall a. Int -> Seq a -> Seq a
take Int
n Seq a
xs = if Int
n forall a. Ord a => a -> a -> Bool
<= Int
0 then forall a. Seq a
E else forall a. Int -> Seq a -> Seq a
ta Int
n Seq a
xs
where ta :: Int -> Seq a -> Seq a
ta Int
_ Seq a
E = forall a. Seq a
E
ta Int
n (B a
x Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
n = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a
ta Int
m Seq a
a) (Int -> Seq a -> Seq a
ta Int
m Seq a
b)
| Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. Seq a
E
| Bool
otherwise = forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a
ta Int
m Seq a
a) (Int -> Seq a -> Seq a
ta (Int
mforall a. Num a => a -> a -> a
-Int
1) Seq a
b)
where m :: Int
m = Int -> Int
half Int
n
drop :: forall a. Int -> Seq a -> Seq a
drop Int
n Seq a
xs = if Int
n forall a. Ord a => a -> a -> Bool
<= Int
0 then Seq a
xs else forall a. Int -> Seq a -> Seq a
dr Int
n Seq a
xs
where dr :: Int -> Seq a -> Seq a
dr Int
_ Seq a
E = forall a. Seq a
E
dr Int
n t :: Seq a
t@(B a
_ Seq a
a Seq a
b)
| forall a. Integral a => a -> Bool
odd Int
n = forall a. Seq a -> Seq a -> Seq a
combine (Int -> Seq a -> Seq a
dr Int
m Seq a
a) (Int -> Seq a -> Seq a
dr Int
m Seq a
b)
| Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = Seq a
t
| Bool
otherwise = forall a. Seq a -> Seq a -> Seq a
combine (Int -> Seq a -> Seq a
dr (Int
mforall a. Num a => a -> a -> a
-Int
1) Seq a
b) (Int -> Seq a -> Seq a
dr Int
m Seq a
a)
where m :: Int
m = Int -> Int
half Int
n
zip :: forall a b. Seq a -> Seq b -> Seq (a, b)
zip (B a
x Seq a
a Seq a
b) (B b
y Seq b
c Seq b
d) = forall a. a -> Seq a -> Seq a -> Seq a
B (a
x,b
y) (forall a b. Seq a -> Seq b -> Seq (a, b)
zip Seq a
a Seq b
c) (forall a b. Seq a -> Seq b -> Seq (a, b)
zip Seq a
b Seq b
d)
zip Seq a
_ Seq b
_ = forall a. Seq a
E
zip3 :: forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3 (B a
x Seq a
a Seq a
b) (B b
y Seq b
c Seq b
d) (B c
z Seq c
e Seq c
f) = forall a. a -> Seq a -> Seq a -> Seq a
B (a
x,b
y,c
z) (forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3 Seq a
a Seq b
c Seq c
e) (forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3 Seq a
b Seq b
d Seq c
f)
zip3 Seq a
_ Seq b
_ Seq c
_ = forall a. Seq a
E
zipWith :: forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith a -> b -> c
f (B a
x Seq a
a Seq a
b) (B b
y Seq b
c Seq b
d) = forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b -> c
f a
x b
y) (forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith a -> b -> c
f Seq a
a Seq b
c) (forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith a -> b -> c
f Seq a
b Seq b
d)
zipWith a -> b -> c
_ Seq a
_ Seq b
_ = forall a. Seq a
E
zipWith3 :: forall a b c d.
(a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
zipWith3 a -> b -> c -> d
fn (B a
x Seq a
a Seq a
b) (B b
y Seq b
c Seq b
d) (B c
z Seq c
e Seq c
f) =
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b -> c -> d
fn a
x b
y c
z) (forall a b c d.
(a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
zipWith3 a -> b -> c -> d
fn Seq a
a Seq b
c Seq c
e) (forall a b c d.
(a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
zipWith3 a -> b -> c -> d
fn Seq a
b Seq b
d Seq c
f)
zipWith3 a -> b -> c -> d
_ Seq a
_ Seq b
_ Seq c
_ = forall a. Seq a
E
unzip :: forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip Seq (a, b)
E = (forall a. Seq a
E, forall a. Seq a
E)
unzip (B (a
x,b
y) Seq (a, b)
a Seq (a, b)
b) = (forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a1 Seq a
b1, forall a. a -> Seq a -> Seq a -> Seq a
B b
y Seq b
a2 Seq b
b2)
where (Seq a
a1,Seq b
a2) = forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip Seq (a, b)
a
(Seq a
b1,Seq b
b2) = forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip Seq (a, b)
b
unzip3 :: forall a b c. Seq (a, b, c) -> (Seq a, Seq b, Seq c)
unzip3 Seq (a, b, c)
E = (forall a. Seq a
E, forall a. Seq a
E, forall a. Seq a
E)
unzip3 (B (a
x,b
y,c
z) Seq (a, b, c)
a Seq (a, b, c)
b) = (forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a1 Seq a
b1, forall a. a -> Seq a -> Seq a -> Seq a
B b
y Seq b
a2 Seq b
b2, forall a. a -> Seq a -> Seq a -> Seq a
B c
z Seq c
a3 Seq c
b3)
where (Seq a
a1,Seq b
a2,Seq c
a3) = forall a b c. Seq (a, b, c) -> (Seq a, Seq b, Seq c)
unzip3 Seq (a, b, c)
a
(Seq a
b1,Seq b
b2,Seq c
b3) = forall a b c. Seq (a, b, c) -> (Seq a, Seq b, Seq c)
unzip3 Seq (a, b, c)
b
unzipWith :: forall a b c. (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith a -> b
_ a -> c
_ Seq a
E = (forall a. Seq a
E, forall a. Seq a
E)
unzipWith a -> b
f a -> c
g (B a
x Seq a
a Seq a
b) = (forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b
f a
x) Seq b
a1 Seq b
b1, forall a. a -> Seq a -> Seq a -> Seq a
B (a -> c
g a
x) Seq c
a2 Seq c
b2)
where (Seq b
a1,Seq c
a2) = forall a b c. (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith a -> b
f a -> c
g Seq a
a
(Seq b
b1,Seq c
b2) = forall a b c. (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith a -> b
f a -> c
g Seq a
b
unzipWith3 :: forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
unzipWith3 a -> b
_ a -> c
_ a -> d
_ Seq a
E = (forall a. Seq a
E, forall a. Seq a
E, forall a. Seq a
E)
unzipWith3 a -> b
f a -> c
g a -> d
h (B a
x Seq a
a Seq a
b) = (forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b
f a
x) Seq b
a1 Seq b
b1, forall a. a -> Seq a -> Seq a -> Seq a
B (a -> c
g a
x) Seq c
a2 Seq c
b2, forall a. a -> Seq a -> Seq a -> Seq a
B (a -> d
h a
x) Seq d
a3 Seq d
b3)
where (Seq b
a1,Seq c
a2,Seq d
a3) = forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
unzipWith3 a -> b
f a -> c
g a -> d
h Seq a
a
(Seq b
b1,Seq c
b2,Seq d
b3) = forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
unzipWith3 a -> b
f a -> c
g a -> d
h Seq a
b
strict :: forall a. Seq a -> Seq a
strict s :: Seq a
s@Seq a
E = Seq a
s
strict s :: Seq a
s@(B a
_ Seq a
l Seq a
r) = forall a. Seq a -> Seq a
strict Seq a
l seq :: forall a b. a -> b -> b
`seq` forall a. Seq a -> Seq a
strict Seq a
r seq :: forall a b. a -> b -> b
`seq` Seq a
s
strictWith :: forall a b. (a -> b) -> Seq a -> Seq a
strictWith a -> b
_ s :: Seq a
s@Seq a
E = Seq a
s
strictWith a -> b
f s :: Seq a
s@(B a
x Seq a
l Seq a
r) = a -> b
f a
x seq :: forall a b. a -> b -> b
`seq` forall a b. (a -> b) -> Seq a -> Seq a
strictWith a -> b
f Seq a
l seq :: forall a b. a -> b -> b
`seq` forall a b. (a -> b) -> Seq a -> Seq a
strictWith a -> b
f Seq a
r seq :: forall a b. a -> b -> b
`seq` Seq a
s
structuralInvariant :: forall a. Seq a -> Bool
structuralInvariant Seq a
E = Bool
True
structuralInvariant (B a
_ Seq a
l Seq a
r) = forall a. Maybe a -> Bool
isJust (forall a. Seq a -> Seq a -> Maybe Int
check Seq a
l Seq a
r)
where check :: Seq a -> Seq a -> Maybe Int
check :: forall a. Seq a -> Seq a -> Maybe Int
check Seq a
E Seq a
E = forall a. a -> Maybe a
Just Int
1
check (B a
_ Seq a
E Seq a
E) Seq a
E = forall a. a -> Maybe a
Just Int
2
check (B a
_ Seq a
l1 Seq a
l2) (B a
_ Seq a
r1 Seq a
r2) = do
Int
x <- forall a. Seq a -> Seq a -> Maybe Int
check Seq a
l1 Seq a
l2
Int
y <- forall a. Seq a -> Seq a -> Maybe Int
check Seq a
r1 Seq a
r2
if (Int
x forall a. Eq a => a -> a -> Bool
== Int
y) Bool -> Bool -> Bool
|| (Int
x forall a. Eq a => a -> a -> Bool
== Int
y forall a. Num a => a -> a -> a
+ Int
1)
then forall (m :: * -> *) a. Monad m => a -> m a
return (Int
xforall a. Num a => a -> a -> a
+Int
yforall a. Num a => a -> a -> a
+Int
1)
else forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"unbalanced tree"
check Seq a
_ Seq a
_ = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"unbalanced tree"
concat :: forall a. Seq (Seq a) -> Seq a
concat = forall (s :: * -> *) a. Sequence s => s (s a) -> s a
concatUsingFoldr
reverseOnto :: forall a. Seq a -> Seq a -> Seq a
reverseOnto = forall (s :: * -> *) a. Sequence s => s a -> s a -> s a
reverseOntoUsingReverse
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
fold :: forall a b. (a -> b -> b) -> b -> Seq a -> b
fold = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
foldrUsingLists
fold' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
fold' a -> b -> b
f = forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
foldl'UsingLists (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
f)
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 = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
foldrUsingLists
foldr' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr' = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
foldr'UsingLists
foldl :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl = forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
foldlUsingLists
foldl' :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl' = forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
foldl'UsingLists
foldr1 :: forall a. (a -> a -> a) -> Seq a -> a
foldr1 = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldr1UsingLists
foldr1' :: forall a. (a -> a -> a) -> Seq a -> a
foldr1' = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldr1'UsingLists
foldl1 :: forall a. (a -> a -> a) -> Seq a -> a
foldl1 = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldl1UsingLists
foldl1' :: forall a. (a -> a -> a) -> Seq a -> a
foldl1' = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldl1UsingLists
reducer :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducer = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducerUsingReduce1
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
reducelUsingReduce1
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
reduce1UsingLists
reduce1' :: forall a. (a -> a -> a) -> Seq a -> a
reduce1' = forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
reduce1'UsingLists
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
splitAt :: forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt = forall (s :: * -> *) a. Sequence s => Int -> s a -> (s a, s a)
splitAtDefault
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
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; 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; 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 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 = forall a. Arbitrary a => Gen a
arbitrary forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (forall (m :: * -> *) a. Monad m => a -> m a
return forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [a] -> Seq a
fromList)
instance CoArbitrary a => CoArbitrary (Seq a) where
coarbitrary :: forall b. Seq a -> Gen b -> Gen b
coarbitrary Seq a
xs = forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary (forall a. Seq a -> [a]
toList Seq a
xs)
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.<>)