-- |
--   Module      :  Data.Edison.Seq.BraunSeq
--   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)
--
--   One-sided Braun sequences.  All running times are as listed in
--   "Data.Edison.Seq" except the following:
--
--   * lview, lcons, ltail*   @O( log n )@
--
--   * rcons, rview, rhead*, rtail*, size   @O( log^2 n )@
--
--   * copy, inBounds, lookup*, update, adjust  @O( log i )@
--
--   * append            @O( n1 log n2 )@
--
--   * concat            @O( n + m log m )@
--
--   * drop, splitAt     @O( i log n )@
--
--   * subseq            @O( i log n + len )@
--
--   * reverseOnto       @O( n1 log n2 )@
--
--   * concatMap, (>>=)  @O( n * t + m log m )@, where @n@ is the length of the input sequence
--                                               @m@ is the length of the output sequence and @t@
--                                               is the running time of @f@
--
--   By keeping track of the size, we could get rcons, rview, rhead*, and rtail*
--   down to @O(log n)@ as well; furthermore, size would be @O( 1 )@.
--
--   /References:/
--
--   * Rob Hoogerwoord. \"A symmetric set of efficient list operations\".
--     /Journal of Functional Programming/, 2(4):505--513, 1992.
--
--   * Rob Hoogerwoord. \"A Logarithmic Implementation of Flexible Arrays\".
--     /Mathematics of Program Construction/ (MPC'92), pages 191-207.
--
--   * Chris Okasaki. \"Three algorithms on Braun Trees\".
--     /Journal of Function Programming/ 7(6):661-666. Novemebr 1997.

module Data.Edison.Seq.BraunSeq (
    -- * 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,foldl',
                       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
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


-- 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.BraunSeq"


data Seq a = E | B a (Seq a) (Seq a)    deriving (Seq a -> Seq a -> Bool
(Seq a -> Seq a -> Bool) -> (Seq a -> Seq a -> Bool) -> Eq (Seq a)
forall a. Eq a => Seq a -> Seq a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$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
/= :: Seq a -> Seq a -> Bool
Eq)

half :: Int -> Int
half :: Int -> Int
half Int
n = Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
2  -- use a shift?

empty :: forall a. Seq a
empty = Seq a
forall a. Seq a
E
singleton :: forall a. a -> Seq a
singleton a
x = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
forall a. Seq a
E Seq a
forall a. Seq a
E

lcons :: forall a. a -> Seq a -> Seq a
lcons a
x Seq a
E = a -> Seq a
forall a. a -> Seq a
singleton a
x
lcons a
x (B a
y Seq a
a Seq a
b) = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x (a -> Seq a -> Seq a
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 (Seq a -> Int
forall a. Seq a -> Int
size Seq a
ys) Seq a
ys
  where insAt :: Int -> Seq a -> Seq a
insAt Int
0 Seq a
_ = a -> Seq a
forall a. a -> Seq a
singleton a
y
        insAt Int
i (B a
x Seq a
a Seq a
b)
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i     = a -> Seq a -> Seq a -> Seq a
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 = a -> Seq a -> Seq a -> Seq a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Seq a
b)
        insAt Int
_ Seq a
_ = String -> 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 = Int -> Seq a -> Seq a -> Seq a
forall {a}. Int -> Seq a -> Seq a -> Seq a
app (Seq a -> Int
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)
            | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
n     = a -> Seq a -> Seq a -> Seq a
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 (a -> Seq a -> Seq 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 = a -> Seq a -> Seq a -> Seq a
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
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Seq a
b (a -> Seq a -> Seq a
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
_ = String -> Seq a
forall a. HasCallStack => String -> a
error String
"BraunSeq.append: bug!"
  -- how does it compare to converting to/from lists?

lview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview Seq a
E = String -> m (a, Seq a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.lview: empty sequence"
lview (B a
x Seq a
a Seq a
b) = (a, Seq a) -> m (a, Seq a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
combine Seq a
a Seq a
b)

-- not exported
combine :: Seq a -> Seq a -> Seq a
combine :: forall a. Seq a -> Seq a -> Seq a
combine Seq a
E Seq a
_ = Seq a
forall a. Seq a
E
combine (B a
x Seq a
a Seq a
b) Seq a
c = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
c (Seq a -> Seq a -> Seq a
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 = String -> a
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 = String -> m a
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.lheadM: empty sequence"
lheadM (B a
x Seq a
_ Seq a
_) = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
x

ltail :: forall a. Seq a -> Seq a
ltail Seq a
E = String -> Seq a
forall a. HasCallStack => String -> a
error String
"BraunSeq.ltail: empty sequence"
ltail (B a
_ Seq a
a Seq a
b) = Seq a -> Seq a -> Seq a
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 = String -> m (Seq a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.ltailM: empty sequence"
ltailM (B a
_ Seq a
a Seq a
b) = Seq a -> m (Seq a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
combine Seq a
a Seq a
b)

-- not exported
-- precondition: i >= 0
delAt :: Int -> Seq a -> Seq a
delAt :: forall a. Int -> Seq a -> Seq a
delAt Int
0 Seq a
_ = Seq a
forall a. Seq a
E
delAt Int
i (B a
x Seq a
a Seq a
b)
  | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i     = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x (Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
delAt (Int -> Int
half Int
i) Seq a
a) Seq a
b
  | Bool
otherwise = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a (Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
delAt (Int -> Int
half Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Seq a
b)
delAt Int
_ Seq a
_ = String -> 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 = String -> m (a, Seq a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.rview: empty sequence"
rview Seq a
xs = (a, Seq a) -> m (a, Seq a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Seq a -> a
forall a. Int -> Seq a -> a
lookup Int
m Seq a
xs, Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
delAt Int
m Seq a
xs)
  where m :: Int
m = Seq a -> Int
forall a. Seq a -> Int
size Seq a
xs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

rhead :: forall a. Seq a -> a
rhead Seq a
E = String -> a
forall a. HasCallStack => String -> a
error String
"BraunSeq.rhead: empty sequence"
rhead Seq a
xs = Int -> Seq a -> a
forall a. Int -> Seq a -> a
lookup (Seq a -> Int
forall a. Seq a -> Int
size Seq a
xs Int -> Int -> Int
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 = String -> m a
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail  String
"BraunSeq.rheadM: empty sequence"
rheadM Seq a
xs = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Seq a -> a
forall a. Int -> Seq a -> a
lookup (Seq a -> Int
forall a. Seq a -> Int
size Seq a
xs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Seq a
xs)

rtail :: forall a. Seq a -> Seq a
rtail Seq a
E = String -> Seq a
forall a. HasCallStack => String -> a
error String
"BraunSeq.rtail: empty sequence"
rtail Seq a
xs = Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
delAt (Seq a -> Int
forall a. Seq a -> Int
size Seq a
xs Int -> Int -> Int
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 = String -> m (Seq a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.rtailM: empty sequence"
rtailM Seq a
xs = Seq a -> m (Seq a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
delAt (Seq a -> Int
forall a. Seq a -> Int
size Seq a
xs Int -> Int -> Int
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Seq a -> Int
forall {a} {a}. Num a => Int -> Seq a -> a
diff Int
n Seq a
a
  where n :: Int
n = Seq a -> Int
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)
          | Int -> Bool
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Seq a
b
        diff Int
_ Seq a
_ = String -> 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 = Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
rev00 (Seq a -> Int
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 = Seq a
xs
    rev00 Int
n (B a
x Seq a
a Seq a
b)
      | Int -> Bool
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') = Int -> a -> Seq a -> (a, Seq a)
forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
x Seq a
b      in a -> Seq a -> Seq a -> Seq a
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') = Int -> Seq a -> (a, Seq a)
forall {a}. Int -> Seq a -> (a, Seq a)
rev01 Int
m Seq a
a
                        b' :: Seq a
b'      = Int -> a -> Seq a -> Seq a
forall {a}. Int -> a -> Seq a -> Seq a
rev10 (Int
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a
x Seq a
b  in a -> Seq a -> Seq a -> Seq a
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
_ = String -> 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,Seq a
forall a. Seq a
E)
    rev11 Int
n a
x (B a
y Seq a
a Seq a
b)
      | Int -> Bool
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', a -> Seq a -> Seq a -> Seq a
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
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a
y Seq a
b  in (a
x', a -> Seq a -> Seq a -> Seq a
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 = String -> (a, Seq a)
forall a. HasCallStack => String -> a
error String
"BraunSeq.reverse: bug!"
    rev01 Int
n (B a
x Seq a
a Seq a
b)
      | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1    = (a
x, Seq a
forall a. Seq a
E)
      | Int -> Bool
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') = Int -> a -> Seq a -> (a, Seq a)
forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
x Seq a
b      in (a
x', a -> Seq a -> Seq a -> Seq a
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') = Int -> a -> Seq a -> (a, Seq a)
forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 (Int
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a
x Seq a
b  in (a
y', a -> Seq a -> Seq a -> Seq a
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 = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
forall a. Seq a
E Seq a
forall a. Seq a
E
    rev10 Int
n a
x (B a
y Seq a
a Seq a
b)
      | Int -> Bool
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') = Int -> a -> Seq a -> (a, Seq a)
forall {a}. Int -> a -> Seq a -> (a, Seq a)
rev11 Int
m a
y Seq a
b      in a -> Seq a -> Seq a -> Seq a
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') = Int -> a -> Seq a -> (a, Seq 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
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a
y Seq a
b  in a -> Seq a -> Seq a -> Seq a
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 = [Seq a] -> Seq a
forall a. [a] -> a
L.lhead ([Seq a] -> Seq a) -> ([a] -> [Seq a]) -> [a] -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, [a]) -> [Seq a] -> [Seq a])
-> [Seq a] -> [(Int, [a])] -> [Seq a]
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr (Int, [a]) -> [Seq a] -> [Seq a]
forall {a}. (Int, [a]) -> [Seq a] -> [Seq a]
build [Seq a
forall a. Seq a
E] ([(Int, [a])] -> [Seq a])
-> ([a] -> [(Int, [a])]) -> [a] -> [Seq a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [a] -> [(Int, [a])]
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) (Int, [a]) -> [(Int, [a])] -> [(Int, [a])]
forall a. a -> [a] -> [a]
: Int -> [a] -> [(Int, [a])]
rows (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
k) [a]
zs
          where ([a]
ys,[a]
zs) = Int -> [a] -> ([a], [a])
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 = [a] -> [Seq a] -> [Seq a] -> [Seq a]
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) = Int -> [Seq a] -> ([Seq a], [Seq a])
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]
_ = a -> Seq a
forall a. a -> Seq a
singleton a
x Seq a -> [Seq a] -> [Seq a]
forall a. a -> [a] -> [a]
: (a -> Seq a) -> [a] -> [Seq a]
forall a b. (a -> b) -> [a] -> [b]
L.map a -> Seq a
forall a. a -> Seq a
singleton [a]
xs
        zipWithB (a
x:[a]
xs) (Seq a
t:[Seq a]
ts) [] = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
t Seq a
forall a. Seq a
E Seq a -> [Seq a] -> [Seq a]
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) = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
t1 Seq a
t2 Seq a -> [Seq a] -> [Seq a]
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 = [Seq a] -> [a]
forall {a}. [Seq a] -> [a]
tol [Seq a
t]
  where tol :: [Seq a] -> [a]
tol [] = []
        tol [Seq a]
ts = [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [Seq a] -> [a]
tol ([Seq a]
ts1 [Seq a] -> [Seq a] -> [Seq a]
forall a. [a] -> [a] -> [a]
++ [Seq a]
ts2)
          where xs :: [a]
xs = (Seq a -> a) -> [Seq a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map Seq a -> a
forall a. Seq a -> a
root [Seq a]
ts
                ([Seq a]
ts1,[Seq a]
ts2) = [Seq a] -> ([Seq a], [Seq a])
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 Seq a -> [Seq a] -> [Seq a]
forall a. a -> [a] -> [a]
: [Seq a] -> [Seq 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 Seq a -> [Seq a] -> [Seq a]
forall a. a -> [a] -> [a]
: [Seq a]
ts1, Seq a
b Seq a -> [Seq a] -> [Seq a]
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]
_ = String -> ([Seq a], [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 Seq a -> [Seq a] -> [Seq a]
forall a. a -> [a] -> [a]
: [Seq a] -> [Seq a]
leftChildren [Seq a]
ts
                leftChildren [Seq a]
_ = String -> [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
_ = String -> a
forall a. HasCallStack => String -> a
error String
"BraunSeq.toList: bug!"

                (B a
_ Seq a
a Seq a
_) = Seq a
a
--                (left _) = error "BraunSeq.toList: bug!"

map :: forall a b. (a -> b) -> Seq a -> Seq b
map a -> b
_ Seq a
E = Seq b
forall a. Seq a
E
map a -> b
f (B a
x Seq a
a Seq a
b) = b -> Seq b -> Seq b -> Seq b
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b
f a
x) ((a -> b) -> Seq a -> Seq b
forall a b. (a -> b) -> Seq a -> Seq b
map a -> b
f Seq a
a) ((a -> b) -> Seq a -> Seq b
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 then Seq a
forall a. Seq a
empty else (Seq a, Seq a) -> Seq a
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
            | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
n     = (a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a Seq a
a, a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
b Seq a
a)
            | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = (Seq a
forall a. Seq a
E, a -> Seq a
forall a. a -> Seq a
singleton a
x)
            | Bool
otherwise = (a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
b Seq a
a, a -> Seq a -> Seq a -> Seq 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
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1))

inBounds :: forall a. Int -> Seq a -> Bool
inBounds Int
i Seq a
xs = (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0) Bool -> Bool -> Bool
&& Seq a -> Int -> 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
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i     = Seq a -> Int -> Bool
inb Seq a
a (Int -> Int
half Int
i)
          | Int
i Int -> Int -> Bool
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

lookup :: forall a. Int -> Seq a -> a
lookup Int
i Seq a
xs = Fail a -> a
forall a. Fail a -> a
runFail_ (Int -> Seq a -> Fail a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0     = String -> m a
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BraunSeq.lookupM: bad subscript"
  | Bool
otherwise = Seq a -> Int -> m a
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
_ = m a
forall {a}. m a
nothing
        look (B a
x Seq a
a Seq a
b) Int
i
          | Int -> Bool
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = a -> m a
forall a. a -> m a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
        nothing :: m a
nothing = String -> m a
forall a. String -> m a
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 Int -> Int -> Bool
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
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i     = Seq a -> Int -> a
look Seq a
a (Int -> Int
half Int
i)
          | Int
i Int -> Int -> Bool
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 Int -> Int -> Int
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 Int -> Int -> Bool
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 = Seq a
forall a. Seq a
E
        upd Int
i (B a
x Seq a
a Seq a
b)
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i     = a -> Seq a -> Seq a -> Seq a
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
y Seq a
a Seq a
b
          | Bool
otherwise = a -> Seq a -> Seq a -> Seq a
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 Int -> Int -> Int
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 Int -> Int -> Bool
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 = Seq a
forall a. Seq a
E
        adj Int
i (B a
x Seq a
a Seq a
b)
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i     = a -> Seq a -> Seq a -> Seq a
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> a
f a
x) Seq a
a Seq a
b
          | Bool
otherwise = a -> Seq a -> Seq a -> Seq a
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 Int -> Int -> Int
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 = Seq b
forall a. Seq a
E
        mwi Int
i Int
d (B a
x Seq a
a Seq a
b) = b -> Seq b -> Seq b -> Seq 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
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
d) Int
dd Seq a
a) (Int -> Int -> Seq a -> Seq b
mwi (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
dd) Int
dd Seq a
b)
          where dd :: Int
dd = Int
dInt -> Int -> Int
forall 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 then Seq a
forall a. Seq a
E else Int -> Seq a -> Seq a
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 = Seq a
forall a. Seq a
E
        ta Int
n (B a
x Seq a
a Seq a
b)
            | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
n     = a -> Seq a -> Seq a -> Seq a
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = Seq a
forall a. Seq a
E
            | Bool
otherwise = a -> Seq a -> Seq a -> Seq a
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
mInt -> Int -> Int
forall 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 then Seq a
xs else Int -> Seq a -> Seq a
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 = Seq a
forall a. Seq a
E
        dr Int
n t :: Seq a
t@(B a
_ Seq a
a Seq a
b)
            | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
n     = Seq a -> Seq a -> Seq a
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = Seq a
t
            | Bool
otherwise = Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
combine (Int -> Seq a -> Seq a
dr (Int
mInt -> Int -> Int
forall 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) = (a, b) -> Seq (a, b) -> Seq (a, b) -> Seq (a, b)
forall a. a -> Seq a -> Seq a -> Seq a
B (a
x,b
y) (Seq a -> Seq b -> Seq (a, b)
forall a b. Seq a -> Seq b -> Seq (a, b)
zip Seq a
a Seq b
c) (Seq a -> Seq b -> Seq (a, b)
forall a b. Seq a -> Seq b -> Seq (a, b)
zip Seq a
b Seq b
d)
zip Seq a
_ Seq b
_ = Seq (a, 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) = (a, b, c) -> Seq (a, b, c) -> Seq (a, b, c) -> Seq (a, b, c)
forall a. a -> Seq a -> Seq a -> Seq a
B (a
x,b
y,c
z) (Seq a -> Seq b -> Seq c -> Seq (a, b, c)
forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3 Seq a
a Seq b
c Seq c
e) (Seq a -> Seq b -> Seq c -> Seq (a, b, c)
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
_ = Seq (a, b, 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) = c -> Seq c -> Seq c -> Seq c
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b -> c
f a
x b
y) ((a -> b -> c) -> Seq a -> Seq b -> Seq c
forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith a -> b -> c
f Seq a
a Seq b
c) ((a -> b -> c) -> Seq a -> Seq b -> Seq 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
_ = Seq c
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) =
    d -> Seq d -> Seq d -> Seq d
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b -> c -> d
fn a
x b
y c
z) ((a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
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) ((a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
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
_ = Seq d
forall a. Seq a
E

unzip :: forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip Seq (a, b)
E = (Seq a
forall a. Seq a
E, Seq b
forall a. Seq a
E)
unzip (B (a
x,b
y) Seq (a, b)
a Seq (a, b)
b) = (a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a1 Seq a
b1, b -> Seq b -> Seq b -> Seq b
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) = Seq (a, b) -> (Seq a, Seq b)
forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip Seq (a, b)
a
        (Seq a
b1,Seq b
b2) = Seq (a, b) -> (Seq a, Seq b)
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 = (Seq a
forall a. Seq a
E, Seq b
forall a. Seq a
E, Seq c
forall a. Seq a
E)
unzip3 (B (a
x,b
y,c
z) Seq (a, b, c)
a Seq (a, b, c)
b) = (a -> Seq a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a -> Seq a
B a
x Seq a
a1 Seq a
b1, b -> Seq b -> Seq b -> Seq b
forall a. a -> Seq a -> Seq a -> Seq a
B b
y Seq b
a2 Seq b
b2, c -> Seq c -> Seq c -> Seq c
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) = Seq (a, b, c) -> (Seq a, Seq b, Seq c)
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) = Seq (a, b, c) -> (Seq a, Seq b, Seq c)
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 = (Seq b
forall a. Seq a
E, Seq c
forall a. Seq a
E)
unzipWith a -> b
f a -> c
g (B a
x Seq a
a Seq a
b) = (b -> Seq b -> Seq b -> Seq b
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b
f a
x) Seq b
a1 Seq b
b1, c -> Seq c -> Seq c -> Seq c
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) = (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
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) = (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
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 = (Seq b
forall a. Seq a
E, Seq c
forall a. Seq a
E, Seq d
forall a. Seq a
E)
unzipWith3 a -> b
f a -> c
g a -> d
h (B a
x Seq a
a Seq a
b) = (b -> Seq b -> Seq b -> Seq b
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> b
f a
x) Seq b
a1 Seq b
b1, c -> Seq c -> Seq c -> Seq c
forall a. a -> Seq a -> Seq a -> Seq a
B (a -> c
g a
x) Seq c
a2 Seq c
b2, d -> Seq d -> Seq d -> Seq d
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) = (a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
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) = (a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
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) = Seq a -> Seq a
forall a. Seq a -> Seq a
strict Seq a
l Seq a -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` Seq a -> Seq a
forall a. Seq a -> Seq a
strict Seq a
r Seq a -> Seq a -> Seq a
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 b -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` (a -> b) -> Seq a -> Seq a
forall a b. (a -> b) -> Seq a -> Seq a
strictWith a -> b
f Seq a
l Seq a -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` (a -> b) -> Seq a -> Seq a
forall a b. (a -> b) -> Seq a -> Seq a
strictWith a -> b
f Seq a
r Seq a -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` Seq a
s

-- invariants:
--   * Left subtree is exactily the same size as the right
--     subtree, or one element larger

-- structuralInvariant :: Seq a -> Bool
structuralInvariant :: forall a. Seq a -> Bool
structuralInvariant Seq a
E         = Bool
True
structuralInvariant (B a
_ Seq a
l Seq a
r) = Maybe Int -> Bool
forall a. Maybe a -> Bool
isJust (Seq a -> Seq a -> Maybe Int
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           = Int -> Maybe Int
forall a. a -> Maybe a
Just Int
1
        check (B a
_ Seq a
E Seq a
E)   Seq a
E           = Int -> Maybe Int
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 <- Seq a -> Seq a -> Maybe Int
forall a. Seq a -> Seq a -> Maybe Int
check Seq a
l1 Seq a
l2
           Int
y <- Seq a -> Seq a -> Maybe Int
forall a. Seq a -> Seq a -> Maybe Int
check Seq a
r1 Seq a
r2
           if (Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
y) Bool -> Bool -> Bool
|| (Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
y Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
              then Int -> Maybe Int
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
              else String -> Maybe Int
forall a. String -> Maybe a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"unbalanced tree"
        check Seq a
_ Seq a
_ = String -> Maybe Int
forall a. String -> Maybe a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"unbalanced tree"


-- the remaining functions all use defaults

concat :: forall a. Seq (Seq a) -> Seq a
concat = Seq (Seq a) -> Seq a
forall (s :: * -> *) a. Sequence s => s (s a) -> s a
concatUsingFoldr
reverseOnto :: forall a. Seq a -> Seq a -> Seq a
reverseOnto = Seq a -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => s a -> s a -> s a
reverseOntoUsingReverse
concatMap :: forall a b. (a -> Seq b) -> Seq a -> Seq b
concatMap = (a -> Seq b) -> Seq a -> Seq b
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 = (a -> b -> b) -> b -> Seq a -> b
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 = (b -> a -> b) -> b -> Seq a -> b
forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
foldl'UsingLists ((a -> b -> b) -> b -> a -> b
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 = (a -> a -> a) -> Seq a -> a
forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
fold1UsingFold
fold1' :: forall a. (a -> a -> a) -> Seq a -> a
fold1' = (a -> a -> a) -> Seq a -> a
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) -> b -> Seq a -> b
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' = (a -> b -> b) -> b -> Seq a -> b
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 = (b -> a -> b) -> b -> Seq a -> b
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' = (b -> a -> b) -> b -> Seq a -> b
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 = (a -> a -> a) -> Seq a -> a
forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldr1UsingLists
foldr1' :: forall a. (a -> a -> a) -> Seq a -> a
foldr1' = (a -> a -> a) -> Seq a -> a
forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldr1'UsingLists
foldl1 :: forall a. (a -> a -> a) -> Seq a -> a
foldl1 = (a -> a -> a) -> Seq a -> a
forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldl1UsingLists
foldl1' :: forall a. (a -> a -> a) -> Seq a -> a
foldl1' = (a -> a -> a) -> Seq a -> a
forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
foldl1UsingLists
reducer :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducer = (a -> a -> a) -> a -> Seq a -> a
forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducerUsingReduce1
reducer' :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducer' = (a -> a -> a) -> a -> Seq a -> a
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 = (a -> a -> a) -> a -> Seq a -> a
forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducelUsingReduce1
reducel' :: forall a. (a -> a -> a) -> a -> Seq a -> a
reducel' = (a -> a -> a) -> a -> Seq a -> a
forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
reducel'UsingReduce1'
reduce1 :: forall a. (a -> a -> a) -> Seq a -> a
reduce1 = (a -> a -> a) -> Seq a -> a
forall (s :: * -> *) a. Sequence s => (a -> a -> a) -> s a -> a
reduce1UsingLists
reduce1' :: forall a. (a -> a -> a) -> Seq a -> a
reduce1' = (a -> a -> a) -> Seq a -> a
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  = (Int -> a -> b -> b) -> b -> Seq a -> b
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' = (Int -> a -> b -> b) -> b -> Seq a -> b
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  = (b -> Int -> a -> b) -> b -> Seq a -> b
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' = (b -> Int -> a -> b) -> b -> Seq a -> b
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 = Int -> Seq a -> (Seq a, Seq a)
forall (s :: * -> *) a. Sequence s => Int -> s a -> (s a, s a)
splitAtDefault
subseq :: forall a. Int -> Int -> Seq a -> Seq a
subseq = Int -> Int -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => Int -> Int -> s a -> s a
subseqDefault
filter :: forall a. (a -> Bool) -> Seq a -> Seq a
filter = (a -> Bool) -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => (a -> Bool) -> s a -> s a
filterUsingLists
partition :: forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
partition = (a -> Bool) -> Seq a -> (Seq a, Seq a)
forall (s :: * -> *) a.
Sequence s =>
(a -> Bool) -> s a -> (s a, s a)
partitionUsingLists
takeWhile :: forall a. (a -> Bool) -> Seq a -> Seq a
takeWhile = (a -> Bool) -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => (a -> Bool) -> s a -> s a
takeWhileUsingLview
dropWhile :: forall a. (a -> Bool) -> Seq a -> Seq a
dropWhile = (a -> Bool) -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => (a -> Bool) -> s a -> s a
dropWhileUsingLview
splitWhile :: forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
splitWhile = (a -> Bool) -> Seq a -> (Seq a, Seq a)
forall (s :: * -> *) a.
Sequence s =>
(a -> Bool) -> s a -> (s a, s a)
splitWhileUsingLview


-- instances

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

instance App.Alternative Seq where
  empty :: forall a. Seq a
empty = Seq a
forall a. Seq a
empty
  <|> :: forall a. Seq a -> Seq a -> Seq 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 = a -> Seq a
forall a. a -> Seq a
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
     b -> Seq b
forall a. a -> Seq a
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 = a -> Seq a
forall a. a -> Seq a
singleton
  Seq a
xs >>= :: forall a b. Seq a -> (a -> Seq b) -> Seq b
>>= a -> Seq b
k = (a -> Seq b) -> Seq a -> Seq b
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 = Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
append
  mzero :: forall a. Seq a
mzero = Seq a
forall a. Seq a
empty

-- instance Eq (Seq a) is derived

instance Ord a => Ord (Seq a) where
  compare :: Seq a -> Seq a -> Ordering
compare = Seq a -> Seq a -> Ordering
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 = Int -> Seq a -> ShowS
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 = Int -> ReadS (Seq a)
forall a (s :: * -> *). (Read a, Sequence s) => Int -> ReadS (s a)
readsPrecUsingFromList

instance Arbitrary a => Arbitrary (Seq a) where
  arbitrary :: Gen (Seq a)
arbitrary = Gen [a]
forall a. Arbitrary a => Gen a
arbitrary Gen [a] -> ([a] -> Gen (Seq a)) -> Gen (Seq a)
forall a b. Gen a -> (a -> Gen b) -> Gen b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (Seq a -> Gen (Seq a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return (Seq a -> Gen (Seq a)) -> ([a] -> Seq a) -> [a] -> Gen (Seq a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Seq a
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 = [a] -> Gen b -> Gen b
forall b. [a] -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary (Seq a -> [a]
forall a. Seq a -> [a]
toList Seq a
xs)

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