-- |
--   Module      :  Data.Edison.Seq.BinaryRandList
--   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)
--
--   Binary Random-Access lists.  All functions have the standard running
--   times from "Data.Edison.Seq" except the following:
--
--  * lcons, lhead, ltail*, lview*, rhead*, size, lookup*, update, adjust, drop   @O( log n )@
--
--  * copy, inBounds   @O( i )@
--
--  * append, reverseOnto  @O( n1 + log n2 )@
--
--  * take, splitAt  @O( i + log n )@
--
--  * subseq         @O( log n + len )@
--
--  * zip            @O( min( n1, n2 ) + log max( n1, n2 ) )@
--
--    /References:/
--
--  * Chris Okasaki. /Purely Functional Data Structures/. 1998.
--    Section 10.1.2.

module Data.Edison.Seq.BinaryRandList (
    -- * 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 Data.Maybe

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

-- signatures for exported functions
moduleName     :: String
empty          :: Seq a
singleton      :: a -> Seq a
lcons          :: a -> Seq a -> Seq a
rcons          :: a -> Seq a -> Seq a
append         :: Seq a -> Seq a -> Seq a
lview          :: (Fail.MonadFail m) => Seq a -> m (a, Seq a)
lhead          :: Seq a -> a
lheadM         :: (Fail.MonadFail m) => Seq a -> m a
ltail          :: Seq a -> Seq a
ltailM         :: (Fail.MonadFail m) => Seq a -> m (Seq a)
rview          :: (Fail.MonadFail m) => Seq a -> m (a, Seq a)
rhead          :: Seq a -> a
rheadM         :: (Fail.MonadFail m) => Seq a -> m a
rtail          :: Seq a -> Seq a
rtailM         :: (Fail.MonadFail m) => Seq a -> m (Seq a)
null           :: Seq a -> Bool
size           :: Seq a -> Int
concat         :: Seq (Seq a) -> Seq a
reverse        :: Seq a -> Seq a
reverseOnto    :: Seq a -> Seq a -> Seq a
fromList       :: [a] -> Seq a
toList         :: Seq a -> [a]
map            :: (a -> b) -> Seq a -> Seq b
concatMap      :: (a -> Seq b) -> Seq a -> Seq b
fold           :: (a -> b -> b) -> b -> Seq a -> b
fold'          :: (a -> b -> b) -> b -> Seq a -> b
fold1          :: (a -> a -> a) -> Seq a -> a
fold1'         :: (a -> a -> a) -> Seq a -> a
foldr          :: (a -> b -> b) -> b -> Seq a -> b
foldl          :: (b -> a -> b) -> b -> Seq a -> b
foldr1         :: (a -> a -> a) -> Seq a -> a
foldl1         :: (a -> a -> a) -> Seq a -> a
reducer        :: (a -> a -> a) -> a -> Seq a -> a
reducel        :: (a -> a -> a) -> a -> Seq a -> a
reduce1        :: (a -> a -> a) -> Seq a -> a
foldr'         :: (a -> b -> b) -> b -> Seq a -> b
foldl'         :: (b -> a -> b) -> b -> Seq a -> b
foldr1'        :: (a -> a -> a) -> Seq a -> a
foldl1'        :: (a -> a -> a) -> Seq a -> a
reducer'       :: (a -> a -> a) -> a -> Seq a -> a
reducel'       :: (a -> a -> a) -> a -> Seq a -> a
reduce1'       :: (a -> a -> a) -> Seq a -> a
copy           :: Int -> a -> Seq a
inBounds       :: Int -> Seq a -> Bool
lookup         :: Int -> Seq a -> a
lookupM        :: (Fail.MonadFail m) => Int -> Seq a -> m a
lookupWithDefault :: a -> Int -> Seq a -> a
update         :: Int -> a -> Seq a -> Seq a
adjust         :: (a -> a) -> Int -> Seq a -> Seq a
mapWithIndex   :: (Int -> a -> b) -> Seq a -> Seq b
foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b
foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b
foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Seq a -> b
foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Seq a -> b
take           :: Int -> Seq a -> Seq a
drop           :: Int -> Seq a -> Seq a
splitAt        :: Int -> Seq a -> (Seq a, Seq a)
subseq         :: Int -> Int -> Seq a -> Seq a
filter         :: (a -> Bool) -> Seq a -> Seq a
partition      :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
takeWhile      :: (a -> Bool) -> Seq a -> Seq a
dropWhile      :: (a -> Bool) -> Seq a -> Seq a
splitWhile     :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
zip            :: Seq a -> Seq b -> Seq (a,b)
zip3           :: Seq a -> Seq b -> Seq c -> Seq (a,b,c)
zipWith        :: (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith3       :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
unzip          :: Seq (a,b) -> (Seq a, Seq b)
unzip3         :: Seq (a,b,c) -> (Seq a, Seq b, Seq c)
unzipWith      :: (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith3     :: (a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
strict         :: Seq a -> Seq a
strictWith     :: (a -> b) -> Seq a -> Seq a
structuralInvariant :: Seq a -> Bool

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


data Seq a = E | Even (Seq (a,a)) | Odd a (Seq (a,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)

-- not exported, rewrite as bit ops?
--even n = (n `mod` 2) == 0
--odd n  = (n `mod` 2) <> 0
half :: (Integral a) => a -> a
half :: forall a. Integral a => a -> a
half a
n = a
n a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2

mkEven :: Seq (a, a) -> Seq a
mkEven :: forall a. Seq (a, a) -> Seq a
mkEven Seq (a, a)
E = Seq a
forall a. Seq a
E
mkEven Seq (a, a)
ps = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
Even Seq (a, a)
ps

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, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x Seq (a, a)
forall a. Seq a
E

lcons :: forall a. a -> Seq a -> Seq a
lcons a
x Seq a
E = a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x Seq (a, a)
forall a. Seq a
E
lcons a
x (Even Seq (a, a)
ps) = a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x Seq (a, a)
ps
lcons a
x (Odd a
y Seq (a, a)
ps) = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
Even ((a, a) -> Seq (a, a) -> Seq (a, a)
forall a. a -> Seq a -> Seq a
lcons (a
x,a
y) Seq (a, a)
ps)

append :: forall a. Seq a -> Seq a -> Seq a
append Seq a
xs Seq a
E = Seq a
xs
append Seq a
xs ys :: Seq a
ys@(Even Seq (a, a)
pys) =
  case Seq a
xs of
    Seq a
E -> Seq a
ys
    Even Seq (a, a)
pxs -> Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
Even (Seq (a, a) -> Seq (a, a) -> Seq (a, a)
forall a. Seq a -> Seq a -> Seq a
append Seq (a, a)
pxs Seq (a, a)
pys)
    Odd a
x Seq (a, a)
pxs -> a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x (Seq (a, a) -> Seq (a, a) -> Seq (a, a)
forall a. Seq a -> Seq a -> Seq a
append Seq (a, a)
pxs Seq (a, a)
pys)
append Seq a
xs ys :: Seq a
ys@(Odd a
_ Seq (a, a)
_) = (a -> Seq a -> Seq a) -> Seq a -> Seq a -> Seq a
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a
lcons Seq a
ys Seq a
xs

copy :: forall a. Int -> a -> Seq a
copy Int
n a
x
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = Seq a
forall a. Seq a
E
    | Bool
otherwise = Int -> a -> Seq a
forall a. Int -> a -> Seq a
cp Int
n a
x
  where cp :: Int -> a -> Seq a
        cp :: forall a. Int -> a -> Seq a
cp Int
n a
x
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
n = a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x (Int -> (a, a) -> Seq (a, a)
forall a. Int -> a -> Seq a
cp (Int -> Int
forall a. Integral a => a -> a
half Int
n) (a
x,a
x))
          | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Seq a
forall a. Seq a
E
          | Bool
otherwise = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
Even (Int -> (a, a) -> Seq (a, a)
forall a. Int -> a -> Seq a
cp (Int -> Int
forall a. Integral a => a -> a
half Int
n) (a
x,a
x))

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
"BinaryRandList.lview: empty sequence"
lview (Even Seq (a, a)
ps) = case Seq (a, a) -> Maybe ((a, a), Seq (a, a))
forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview Seq (a, a)
ps of
                    Just ((a
x,a
y), Seq (a, a)
ps') -> (a, Seq a) -> m (a, Seq a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
y Seq (a, a)
ps')
                    Maybe ((a, a), Seq (a, a))
Nothing -> String -> m (a, Seq a)
forall a. HasCallStack => String -> a
error String
"BinaryRandList.lview: bug!"
lview (Odd a
x Seq (a, a)
ps) = (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, a) -> Seq a
forall a. Seq (a, a) -> Seq a
mkEven Seq (a, a)
ps)

lhead :: forall a. Seq a -> a
lhead Seq a
E = String -> a
forall a. HasCallStack => String -> a
error String
"BinaryRandList.lhead: empty sequence"
lhead (Even Seq (a, a)
ps) = (a, a) -> a
forall a b. (a, b) -> a
fst (Seq (a, a) -> (a, a)
forall a. Seq a -> a
lhead Seq (a, a)
ps)
lhead (Odd a
x Seq (a, 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
"BinaryRandList.lheadM: empty sequence"
lheadM (Even Seq (a, a)
ps) = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, a) -> a
forall a b. (a, b) -> a
fst (Seq (a, a) -> (a, a)
forall a. Seq a -> a
lhead Seq (a, a)
ps))
lheadM (Odd a
x Seq (a, 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
"BinaryRandList.ltail: empty sequence"
ltail (Even Seq (a, a)
ps) = case Seq (a, a) -> Maybe ((a, a), Seq (a, a))
forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview Seq (a, a)
ps of
                    Just ((a
_,a
y), Seq (a, a)
ps') -> a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
y Seq (a, a)
ps'
                    Maybe ((a, a), Seq (a, a))
Nothing -> String -> Seq a
forall a. HasCallStack => String -> a
error String
"BinaryRandList.ltail: bug!"
ltail (Odd a
_ Seq (a, a)
ps) = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
mkEven Seq (a, a)
ps

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
"BinaryRandList.ltailM: empty sequence"
ltailM (Even Seq (a, a)
ps) = case Seq (a, a) -> Maybe ((a, a), Seq (a, a))
forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
lview Seq (a, a)
ps of
                      Just ((a
_,a
y), Seq (a, a)
ps') -> Seq a -> m (Seq a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
y Seq (a, a)
ps')
                      Maybe ((a, a), Seq (a, a))
Nothing -> String -> m (Seq a)
forall a. HasCallStack => String -> a
error String
"BinaryRandList.ltailM: bug!"
ltailM (Odd a
_ Seq (a, a)
ps) = Seq a -> m (Seq a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
mkEven Seq (a, a)
ps)

rhead :: forall a. Seq a -> a
rhead Seq a
E = String -> a
forall a. HasCallStack => String -> a
error String
"BinaryRandList.rhead: empty sequence"
rhead (Even Seq (a, a)
ps) = (a, a) -> a
forall a b. (a, b) -> b
snd (Seq (a, a) -> (a, a)
forall a. Seq a -> a
rhead Seq (a, a)
ps)
rhead (Odd a
x Seq (a, a)
E) = a
x
rhead (Odd a
_ Seq (a, a)
ps) = (a, a) -> a
forall a b. (a, b) -> b
snd (Seq (a, a) -> (a, a)
forall a. Seq a -> a
rhead Seq (a, a)
ps)

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
"BinaryRandList.rheadM: empty sequence"
rheadM (Even Seq (a, a)
ps) = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, a) -> a
forall a b. (a, b) -> b
snd (Seq (a, a) -> (a, a)
forall a. Seq a -> a
rhead Seq (a, a)
ps))
rheadM (Odd a
x Seq (a, a)
E) = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
x
rheadM (Odd a
_ Seq (a, a)
ps) = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, a) -> a
forall a b. (a, b) -> b
snd (Seq (a, a) -> (a, a)
forall a. Seq a -> a
rhead Seq (a, a)
ps))


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 (Even Seq (a, a)
ps) = Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Seq (a, a) -> Int
forall a. Seq a -> Int
size Seq (a, a)
ps
size (Odd a
_ Seq (a, a)
ps) = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Seq (a, a) -> Int
forall a. Seq a -> Int
size Seq (a, a)
ps

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 (Even Seq (a, a)
ps)  = Seq (b, b) -> Seq b
forall a. Seq (a, a) -> Seq a
Even (((a, a) -> (b, b)) -> Seq (a, a) -> Seq (b, b)
forall a b. (a -> b) -> Seq a -> Seq b
map (\(a
x,a
y) -> (a -> b
f a
x,a -> b
f a
y)) Seq (a, a)
ps)
map a -> b
f (Odd a
x Seq (a, a)
ps) = b -> Seq (b, b) -> Seq b
forall a. a -> Seq (a, a) -> Seq a
Odd (a -> b
f a
x) (((a, a) -> (b, b)) -> Seq (a, a) -> Seq (b, b)
forall a b. (a -> b) -> Seq a -> Seq b
map (\(a
y,a
z) -> (a -> b
f a
y,a -> b
f a
z)) Seq (a, a)
ps)

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
foldr
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
foldr'
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
e Seq a
E = b
e
foldr a -> b -> b
f b
e (Even Seq (a, a)
ps)  = ((a, a) -> b -> b) -> b -> Seq (a, a) -> b
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr (\(a
x,a
y) b
e -> a -> b -> b
f a
x (a -> b -> b
f a
y b
e)) b
e Seq (a, a)
ps
foldr a -> b -> b
f b
e (Odd a
x Seq (a, a)
ps) = a -> b -> b
f a
x (((a, a) -> b -> b) -> b -> Seq (a, a) -> b
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr (\(a
x,a
y) b
e -> a -> b -> b
f a
x (a -> b -> b
f a
y b
e)) b
e Seq (a, a)
ps)

foldr' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr' a -> b -> b
_ b
e Seq a
E = b
e
foldr' a -> b -> b
f b
e (Even Seq (a, a)
ps)  = ((a, a) -> b -> b) -> b -> Seq (a, a) -> b
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr' (\(a
x,a
y) b
e -> a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! a -> b -> b
f a
y (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! b
e) b
e Seq (a, a)
ps
foldr' a -> b -> b
f b
e (Odd a
x Seq (a, a)
ps) = a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! (((a, a) -> b -> b) -> b -> Seq (a, a) -> b
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr' (\(a
x,a
y) b
e -> a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! a -> b -> b
f a
y (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! b
e) b
e Seq (a, a)
ps)

foldl :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl b -> a -> b
_ b
e Seq a
E = b
e
foldl b -> a -> b
f b
e (Even Seq (a, a)
ps)  = (b -> (a, a) -> b) -> b -> Seq (a, a) -> b
forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl (\b
e (a
x,a
y) -> b -> a -> b
f (b -> a -> b
f b
e a
x) a
y) b
e Seq (a, a)
ps
foldl b -> a -> b
f b
e (Odd a
x Seq (a, a)
ps) = (b -> (a, a) -> b) -> b -> Seq (a, a) -> b
forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl (\b
e (a
x,a
y) -> b -> a -> b
f (b -> a -> b
f b
e a
x) a
y) (b -> a -> b
f b
e a
x) Seq (a, a)
ps

foldl' :: forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl' b -> a -> b
_ b
e Seq a
E = b
e
foldl' b -> a -> b
f b
e (Even Seq (a, a)
ps)  = (b -> (a, a) -> b) -> b -> Seq (a, a) -> b
forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl' (\b
e (a
x,a
y) -> b -> a -> b
f (b -> a -> b
f b
e a
x) a
y) b
e Seq (a, a)
ps
foldl' b -> a -> b
f b
e (Odd a
x Seq (a, a)
ps) = b
e b -> b -> b
forall a b. a -> b -> b
`seq` (b -> (a, a) -> b) -> b -> Seq (a, a) -> b
forall b a. (b -> a -> b) -> b -> Seq a -> b
foldl' (\b
e (a
x,a
y) -> b
e b -> b -> b
forall a b. a -> b -> b
`seq` (\b
z -> b -> a -> b
f b
z a
y) (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! (b -> a -> b
f b
e a
x)) (b -> a -> b
f b
e a
x) Seq (a, a)
ps

reduce1 :: forall a. (a -> a -> a) -> Seq a -> a
reduce1 a -> a -> a
_ Seq a
E = String -> a
forall a. HasCallStack => String -> a
error String
"BinaryRandList.reduce1: empty seq"
reduce1 a -> a -> a
f (Even Seq (a, a)
ps)  = (a -> a -> a) -> Seq a -> a
forall a. (a -> a -> a) -> Seq a -> a
reduce1 a -> a -> a
f (((a, a) -> a) -> Seq (a, a) -> Seq a
forall a b. (a -> b) -> Seq a -> Seq b
map ((a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
f) Seq (a, a)
ps)
reduce1 a -> a -> a
_ (Odd a
x Seq (a, a)
E)  = a
x
reduce1 a -> a -> a
f (Odd a
x Seq (a, a)
ps) = a -> a -> a
f a
x ((a -> a -> a) -> Seq a -> a
forall a. (a -> a -> a) -> Seq a -> a
reduce1 a -> a -> a
f (((a, a) -> a) -> Seq (a, a) -> Seq a
forall a b. (a -> b) -> Seq a -> Seq b
map ((a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
f) Seq (a, a)
ps))

reduce1' :: forall a. (a -> a -> a) -> Seq a -> a
reduce1' a -> a -> a
_ Seq a
E = String -> a
forall a. HasCallStack => String -> a
error String
"BinaryRandList.reduce1': empty seq"
reduce1' a -> a -> a
f (Even Seq (a, a)
ps)  = (a -> a -> a) -> Seq a -> a
forall a. (a -> a -> a) -> Seq a -> a
reduce1' a -> a -> a
f (((a, a) -> a) -> Seq (a, a) -> Seq a
forall a b. (a -> b) -> Seq a -> Seq b
map ((a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
f) Seq (a, a)
ps)
reduce1' a -> a -> a
_ (Odd a
x Seq (a, a)
E)  = a
x
reduce1' a -> a -> a
f (Odd a
x Seq (a, a)
ps) = (a -> a -> a
f (a -> a -> a) -> a -> a -> a
forall a b. (a -> b) -> a -> b
$! a
x) (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> Seq a -> a
forall a. (a -> a -> a) -> Seq a -> a
reduce1' a -> a -> a
f (((a, a) -> a) -> Seq (a, a) -> Seq a
forall a b. (a -> b) -> Seq a -> Seq b
map ((a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
f) Seq (a, a)
ps))


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 :: forall a. Seq a -> Int -> Bool
inb Seq a
E Int
_ = Bool
False
        inb (Even Seq (a, a)
ps) Int
i = Seq (a, a) -> Int -> Bool
forall a. Seq a -> Int -> Bool
inb Seq (a, a)
ps (Int -> Int
forall a. Integral a => a -> a
half Int
i)
        inb (Odd a
_ Seq (a, a)
ps) Int
i = (Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0) Bool -> Bool -> Bool
|| Seq (a, a) -> Int -> Bool
forall a. Seq a -> Int -> Bool
inb Seq (a, a)
ps (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> 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
"BinaryRandList.lookup: bad subscript"
    | Bool
otherwise = m a -> Seq a -> Int -> (a -> m a) -> m a
forall b a. b -> Seq a -> Int -> (a -> b) -> b
lookFun m a
forall {a}. m a
nothing Seq a
xs Int
i a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return
    where
        nothing :: m a
nothing = String -> m a
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"BinaryRandList.lookup: not found"

lookupWithDefault :: forall a. a -> Int -> Seq a -> a
lookupWithDefault a
d Int
i Seq a
xs
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = a
d
    | Bool
otherwise = a -> Seq a -> Int -> (a -> a) -> a
forall b a. b -> Seq a -> Int -> (a -> b) -> b
lookFun a
d Seq a
xs Int
i a -> a
forall a. a -> a
id

-- not exported
lookFun :: b -> Seq a -> Int -> (a -> b) -> b
lookFun :: forall b a. b -> Seq a -> Int -> (a -> b) -> b
lookFun b
d Seq a
E Int
_ a -> b
_ = b
d
lookFun b
d (Even Seq (a, a)
ps) Int
i a -> b
f
  | Int -> Bool
forall a. Integral a => a -> Bool
even Int
i = b -> Seq (a, a) -> Int -> ((a, a) -> b) -> b
forall b a. b -> Seq a -> Int -> (a -> b) -> b
lookFun b
d Seq (a, a)
ps (Int -> Int
forall a. Integral a => a -> a
half Int
i) (a -> b
f (a -> b) -> ((a, a) -> a) -> (a, a) -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> a
forall a b. (a, b) -> a
fst)
  | Bool
otherwise = b -> Seq (a, a) -> Int -> ((a, a) -> b) -> b
forall b a. b -> Seq a -> Int -> (a -> b) -> b
lookFun b
d Seq (a, a)
ps (Int -> Int
forall a. Integral a => a -> a
half Int
i) (a -> b
f (a -> b) -> ((a, a) -> a) -> (a, a) -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> a
forall a b. (a, b) -> b
snd)
lookFun b
d (Odd a
x Seq (a, a)
ps) Int
i a -> b
f
  | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i = b -> Seq (a, a) -> Int -> ((a, a) -> b) -> b
forall b a. b -> Seq a -> Int -> (a -> b) -> b
lookFun b
d Seq (a, a)
ps (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) (a -> b
f (a -> b) -> ((a, a) -> a) -> (a, a) -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> a
forall a b. (a, b) -> a
fst)
  | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = a -> b
f a
x
  | Bool
otherwise = b -> Seq (a, a) -> Int -> ((a, a) -> b) -> b
forall b a. b -> Seq a -> Int -> (a -> b) -> b
lookFun b
d Seq (a, a)
ps (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) (a -> b
f (a -> b) -> ((a, a) -> a) -> (a, a) -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> a
forall a b. (a, b) -> b
snd)

adjust :: forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust a -> a
f Int
i Seq a
xs
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = Seq a
xs
    | Bool
otherwise = (a -> a) -> Int -> Seq a -> Seq a
forall a. (a -> a) -> Int -> Seq a -> Seq a
adj a -> a
f Int
i Seq a
xs
  where adj :: (a -> a) -> Int -> Seq a -> Seq a
        adj :: forall a. (a -> a) -> Int -> Seq a -> Seq a
adj a -> a
_ Int
_ Seq a
E = Seq a
forall a. Seq a
E
        adj a -> a
f Int
i (Even Seq (a, a)
ps)
          | Int -> Bool
forall a. Integral a => a -> Bool
even Int
i = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
Even (((a, a) -> (a, a)) -> Int -> Seq (a, a) -> Seq (a, a)
forall a. (a -> a) -> Int -> Seq a -> Seq a
adj ((a -> a) -> (a, a) -> (a, a)
forall t t2 t1. (t -> t2) -> (t, t1) -> (t2, t1)
mapFst a -> a
f) (Int -> Int
forall a. Integral a => a -> a
half Int
i) Seq (a, a)
ps)
          | Bool
otherwise = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
Even (((a, a) -> (a, a)) -> Int -> Seq (a, a) -> Seq (a, a)
forall a. (a -> a) -> Int -> Seq a -> Seq a
adj ((a -> a) -> (a, a) -> (a, a)
forall t1 t2 t. (t1 -> t2) -> (t, t1) -> (t, t2)
mapSnd a -> a
f) (Int -> Int
forall a. Integral a => a -> a
half Int
i) Seq (a, a)
ps)
        adj a -> a
f Int
i (Odd a
x Seq (a, a)
ps)
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i = a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x (((a, a) -> (a, a)) -> Int -> Seq (a, a) -> Seq (a, a)
forall a. (a -> a) -> Int -> Seq a -> Seq a
adj ((a -> a) -> (a, a) -> (a, a)
forall t t2 t1. (t -> t2) -> (t, t1) -> (t2, t1)
mapFst a -> a
f) (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) Seq (a, a)
ps)
          | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd (a -> a
f a
x) Seq (a, a)
ps
          | Bool
otherwise = a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x (((a, a) -> (a, a)) -> Int -> Seq (a, a) -> Seq (a, a)
forall a. (a -> a) -> Int -> Seq a -> Seq a
adj ((a -> a) -> (a, a) -> (a, a)
forall t1 t2 t. (t1 -> t2) -> (t, t1) -> (t, t2)
mapSnd a -> a
f) (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) Seq (a, a)
ps)

-- not exported
mapFst :: (t -> t2) -> (t, t1) -> (t2, t1)
mapFst :: forall t t2 t1. (t -> t2) -> (t, t1) -> (t2, t1)
mapFst t -> t2
f (t
x,t1
y) = (t -> t2
f t
x,t1
y)
mapSnd :: (t1 -> t2) -> (t, t1) -> (t, t2)
mapSnd :: forall t1 t2 t. (t1 -> t2) -> (t, t1) -> (t, t2)
mapSnd t1 -> t2
f (t
x,t1
y) = (t
x,t1 -> t2
f t1
y)

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
tak Int
n Seq a
xs
  where tak :: Int -> Seq a -> Seq a
        tak :: forall a. Int -> Seq a -> Seq a
tak Int
0 Seq a
_ = Seq a
forall a. Seq a
E
        tak Int
_ Seq a
E = Seq a
forall a. Seq a
E
        tak Int
i (Even Seq (a, a)
ps)
          | Int -> Bool
forall a. Integral a => a -> Bool
even Int
i = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
Even (Int -> Seq (a, a) -> Seq (a, a)
forall a. Int -> Seq a -> Seq a
tak (Int -> Int
forall a. Integral a => a -> a
half Int
i) Seq (a, a)
ps)
        tak Int
i (Odd a
x Seq (a, a)
ps)
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i = a -> Seq (a, a) -> Seq a
forall a. a -> Seq (a, a) -> Seq a
Odd a
x (Int -> Seq (a, a) -> Seq (a, a)
forall a. Int -> Seq a -> Seq a
tak (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) Seq (a, a)
ps)
        tak Int
i Seq a
xs = Int -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => Int -> s a -> s a
takeUsingLists Int
i Seq a
xs

-- drop is O(log^2 n) instead of O(log 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
drp Int
n Seq a
xs
  where drp :: Int -> Seq a -> Seq a
        drp :: forall a. Int -> Seq a -> Seq a
drp Int
0 Seq a
xs = Seq a
xs
        drp Int
_ Seq a
E = Seq a
forall a. Seq a
E
        drp Int
i (Even Seq (a, a)
ps)
          | Int -> Bool
forall a. Integral a => a -> Bool
even Int
i = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
mkEven (Int -> Seq (a, a) -> Seq (a, a)
forall a. Int -> Seq a -> Seq a
drp (Int -> Int
forall a. Integral a => a -> a
half Int
i) Seq (a, a)
ps)
          | Bool
otherwise = Seq a -> Maybe (Seq a) -> Seq a
forall a. a -> Maybe a -> a
fromMaybe Seq a
forall a. Seq a
empty (Seq a -> Maybe (Seq a)
forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
ltailM (Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
mkEven (Int -> Seq (a, a) -> Seq (a, a)
forall a. Int -> Seq a -> Seq a
drp (Int -> Int
forall a. Integral a => a -> a
half Int
i) Seq (a, a)
ps)))
        drp Int
i (Odd a
_ Seq (a, a)
ps)
          | Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i = Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
mkEven (Int -> Seq (a, a) -> Seq (a, a)
forall a. Int -> Seq a -> Seq a
drp (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) Seq (a, a)
ps)
          | Bool
otherwise = Seq a -> Maybe (Seq a) -> Seq a
forall a. a -> Maybe a -> a
fromMaybe Seq a
forall a. Seq a
empty (Seq a -> Maybe (Seq a)
forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
ltailM (Seq (a, a) -> Seq a
forall a. Seq (a, a) -> Seq a
mkEven (Int -> Seq (a, a) -> Seq (a, a)
forall a. Int -> Seq a -> Seq a
drp (Int -> Int
forall a. Integral a => a -> a
half (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) Seq (a, a)
ps)))


strict :: forall a. Seq a -> Seq a
strict l :: Seq a
l@Seq a
E = Seq a
l
strict l :: Seq a
l@(Even Seq (a, a)
l') = Seq (a, a) -> Seq (a, a)
forall a. Seq a -> Seq a
strict Seq (a, a)
l' Seq (a, a) -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` Seq a
l
strict l :: Seq a
l@(Odd a
_ Seq (a, a)
l') = Seq (a, a) -> Seq (a, a)
forall a. Seq a -> Seq a
strict Seq (a, a)
l' Seq (a, a) -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` Seq a
l

strictWith :: forall a b. (a -> b) -> Seq a -> Seq a
strictWith a -> b
_ l :: Seq a
l@Seq a
E = Seq a
l
strictWith a -> b
f l :: Seq a
l@(Even Seq (a, a)
l')  = ((a, a) -> b) -> Seq (a, a) -> Seq (a, a)
forall a b. (a -> b) -> Seq a -> Seq a
strictWith (\ (a
x,a
y) -> a -> b
f a
x b -> b -> b
forall a b. a -> b -> b
`seq` a -> b
f a
y) Seq (a, a)
l' Seq (a, a) -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` Seq a
l
strictWith a -> b
f l :: Seq a
l@(Odd a
x Seq (a, a)
_') = a -> b
f a
x b -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` ((a, a) -> b) -> Seq (a, a) -> Seq (a, a)
forall a b. (a -> b) -> Seq a -> Seq a
strictWith (\ (a
x,a
y) -> a -> b
f a
x b -> b -> b
forall a b. a -> b -> b
`seq` a -> b
f a
y) (Seq (a, a) -> Seq (a, a)) -> Seq a -> Seq a
forall a b. a -> b -> b
`seq` Seq a
l


-- structural invariants are enforced by the type system
structuralInvariant :: forall a. Seq a -> Bool
structuralInvariant = Bool -> Seq a -> Bool
forall a b. a -> b -> a
const Bool
True

-- the remaining functions all use defaults

rcons :: forall a. a -> Seq a -> Seq a
rcons = a -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
rconsUsingFoldr
rview :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (a, Seq a)
rview = Seq a -> m (a, Seq a)
forall (m :: * -> *) (s :: * -> *) a.
(MonadFail m, Sequence s) =>
s a -> m (a, s a)
rviewDefault
rtail :: forall a. Seq a -> Seq a
rtail = Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => s a -> s a
rtailUsingLview
rtailM :: forall (m :: * -> *) a. MonadFail m => Seq a -> m (Seq a)
rtailM = Seq a -> m (Seq a)
forall (m :: * -> *) (s :: * -> *) a.
(MonadFail m, Sequence s) =>
s a -> m (s a)
rtailMUsingLview
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
reverse :: forall a. Seq a -> Seq a
reverse = Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => s a -> s a
reverseUsingReverseOnto
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
reverseOntoUsingFoldl
fromList :: forall a. [a] -> Seq a
fromList = [a] -> Seq a
forall (s :: * -> *) a. Sequence s => [a] -> s a
fromListUsingCons
toList :: forall a. Seq a -> [a]
toList = Seq a -> [a]
forall (s :: * -> *) a. Sequence s => s a -> [a]
toListUsingFoldr
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
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
foldr1UsingLview
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'UsingLview
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
foldl1UsingFoldl
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
foldl1'UsingFoldl'
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
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
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
reducel'UsingReduce1'
update :: forall a. Int -> a -> Seq a -> Seq a
update = Int -> a -> Seq a -> Seq a
forall (s :: * -> *) a. Sequence s => Int -> a -> s a -> s a
updateUsingAdjust
mapWithIndex :: forall a b. (Int -> a -> b) -> Seq a -> Seq b
mapWithIndex = (Int -> a -> b) -> Seq a -> Seq b
forall (s :: * -> *) a b.
Sequence s =>
(Int -> a -> b) -> s a -> s b
mapWithIndexUsingLists
foldrWithIndex :: forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
foldrWithIndex = (Int -> a -> b -> b) -> b -> Seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(Int -> a -> b -> b) -> b -> s a -> b
foldrWithIndexUsingLists
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
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
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
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
filterUsingFoldr
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)
partitionUsingFoldr
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
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

-- for zips, could optimize by calculating which one is shorter and
-- retaining its shape

zip :: forall a b. Seq a -> Seq b -> Seq (a, b)
zip = Seq a -> Seq b -> Seq (a, b)
forall (s :: * -> *) a b. Sequence s => s a -> s b -> s (a, b)
zipUsingLists
zip3 :: forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
zip3 = Seq a -> Seq b -> Seq c -> Seq (a, b, c)
forall (s :: * -> *) a b c.
Sequence s =>
s a -> s b -> s c -> s (a, b, c)
zip3UsingLists
zipWith :: forall a b c. (a -> b -> c) -> Seq a -> Seq b -> Seq c
zipWith = (a -> b -> c) -> Seq a -> Seq b -> Seq c
forall (s :: * -> *) a b c.
Sequence s =>
(a -> b -> c) -> s a -> s b -> s c
zipWithUsingLists
zipWith3 :: forall a b c d.
(a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
zipWith3 = (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
forall (s :: * -> *) a b c d.
Sequence s =>
(a -> b -> c -> d) -> s a -> s b -> s c -> s d
zipWith3UsingLists
unzip :: forall a b. Seq (a, b) -> (Seq a, Seq b)
unzip = Seq (a, b) -> (Seq a, Seq b)
forall (s :: * -> *) a b. Sequence s => s (a, b) -> (s a, s b)
unzipUsingLists
unzip3 :: forall a b c. Seq (a, b, c) -> (Seq a, Seq b, Seq c)
unzip3 = Seq (a, b, c) -> (Seq a, Seq b, Seq c)
forall (s :: * -> *) a b c.
Sequence s =>
s (a, b, c) -> (s a, s b, s c)
unzip3UsingLists
unzipWith :: forall a b c. (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
unzipWith = (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c)
forall (s :: * -> *) a b c.
Sequence s =>
(a -> b) -> (a -> c) -> s a -> (s b, s c)
unzipWithUsingLists
unzipWith3 :: forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
unzipWith3 = (a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d)
forall (s :: * -> *) a b c d.
Sequence s =>
(a -> b) -> (a -> c) -> (a -> d) -> s a -> (s b, s c, s d)
unzipWith3UsingLists

-- instances

instance S.Sequence Seq where
  {lcons :: forall a. a -> Seq a -> Seq a
lcons = 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 = do [a]
xs <- Gen [a]
forall a. Arbitrary a => Gen a
arbitrary
                 Seq a -> Gen (Seq a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> Seq a
forall a. [a] -> Seq a
fromList [a]
xs)

instance CoArbitrary a => CoArbitrary (Seq a) where
  coarbitrary :: forall b. Seq a -> Gen b -> Gen b
coarbitrary Seq a
E = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
  coarbitrary (Even Seq (a, a)
ps) = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
1 (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq (a, a) -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. Seq (a, a) -> Gen b -> Gen b
coarbitrary Seq (a, a)
ps
  coarbitrary (Odd a
x Seq (a, a)
ps) = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
2 (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Gen b -> Gen b
forall b. a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary a
x (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq (a, a) -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. Seq (a, a) -> Gen b -> Gen b
coarbitrary Seq (a, a)
ps


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.<>)