{-# LANGUAGE CPP #-}
{-# OPTIONS_HADDOCK hide #-}
module Graphics.UI.Gtk.ModelView.Sequence (
Seq,
empty,
singleton,
(<|),
(|>),
(><),
null,
ViewL(..),
viewl,
ViewR(..),
viewr,
length,
index,
adjust,
update,
take,
drop,
splitAt,
fromList,
toList,
foldr,
foldr1,
foldr',
foldrM,
foldl,
foldl1,
foldl',
foldlM,
reverse,
#if TESTING
valid,
#endif
) where
import Prelude hiding (
null, length, take, drop, splitAt, foldl, foldl1, foldr, foldr1,
reverse)
import qualified Prelude (foldr)
import Data.List (intersperse)
import qualified Data.List (foldl')
#if TESTING
import Control.Monad (liftM, liftM2, liftM3, liftM4)
import Test.QuickCheck
#endif
infixr 5 `consTree`
infixl 5 `snocTree`
infixr 5 ><
infixr 5 <|, :<
infixl 5 |>, :>
class Sized a where
size :: a -> Int
newtype Seq a = Seq (FingerTree (Elem a))
instance Functor Seq where
fmap :: forall a b. (a -> b) -> Seq a -> Seq b
fmap a -> b
f (Seq FingerTree (Elem a)
xs) = forall a. FingerTree (Elem a) -> Seq a
Seq (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) FingerTree (Elem a)
xs)
instance Eq a => Eq (Seq a) where
Seq a
xs == :: Seq a -> Seq a -> Bool
== Seq a
ys = forall a. Seq a -> Int
length Seq a
xs forall a. Eq a => a -> a -> Bool
== forall a. Seq a -> Int
length Seq a
ys Bool -> Bool -> Bool
&& forall a. Seq a -> [a]
toList Seq a
xs forall a. Eq a => a -> a -> Bool
== forall a. Seq a -> [a]
toList Seq a
ys
instance Ord a => Ord (Seq a) where
compare :: Seq a -> Seq a -> Ordering
compare Seq a
xs Seq a
ys = forall a. Ord a => a -> a -> Ordering
compare (forall a. Seq a -> [a]
toList Seq a
xs) (forall a. Seq a -> [a]
toList Seq a
ys)
#if TESTING
instance (Show a) => Show (Seq a) where
showsPrec p (Seq x) = showsPrec p x
#else
instance Show a => Show (Seq a) where
showsPrec :: Int -> Seq a -> ShowS
showsPrec Int
_ Seq a
xs = Char -> ShowS
showChar Char
'<' forall b c a. (b -> c) -> (a -> b) -> a -> c
.
forall a b c. (a -> b -> c) -> b -> a -> c
flip (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr forall a b. (a -> b) -> a -> b
($)) (forall a. a -> [a] -> [a]
intersperse (Char -> ShowS
showChar Char
',')
(forall a b. (a -> b) -> [a] -> [b]
map forall a. Show a => a -> ShowS
shows (forall a. Seq a -> [a]
toList Seq a
xs))) forall b c a. (b -> c) -> (a -> b) -> a -> c
.
Char -> ShowS
showChar Char
'>'
#endif
data FingerTree a
= Empty
| Single a
| Deep {-# UNPACK #-} !Int !(Digit a) (FingerTree (Node a)) !(Digit a)
#if TESTING
deriving Show
#endif
instance Sized a => Sized (FingerTree a) where
size :: FingerTree a -> Int
size FingerTree a
Empty = Int
0
size (Single a
x) = forall a. Sized a => a -> Int
size a
x
size (Deep Int
v Digit a
_ FingerTree (Node a)
_ Digit a
_) = Int
v
instance Functor FingerTree where
fmap :: forall a b. (a -> b) -> FingerTree a -> FingerTree b
fmap a -> b
_ FingerTree a
Empty = forall a. FingerTree a
Empty
fmap a -> b
f (Single a
x) = forall a. a -> FingerTree a
Single (a -> b
f a
x)
fmap a -> b
f (Deep Int
v Digit a
pr FingerTree (Node a)
m Digit a
sf) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
v (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Digit a
pr) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) FingerTree (Node a)
m) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Digit a
sf)
{-# INLINE deep #-}
deep :: Sized a => Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep :: forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep Digit a
pr FingerTree (Node a)
m Digit a
sf = forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (forall a. Sized a => a -> Int
size Digit a
pr forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size FingerTree (Node a)
m forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Digit a
sf) Digit a
pr FingerTree (Node a)
m Digit a
sf
data Digit a
= One a
| Two a a
| Three a a a
| Four a a a a
#if TESTING
deriving Show
#endif
instance Functor Digit where
fmap :: forall a b. (a -> b) -> Digit a -> Digit b
fmap a -> b
f (One a
a) = forall a. a -> Digit a
One (a -> b
f a
a)
fmap a -> b
f (Two a
a a
b) = forall a. a -> a -> Digit a
Two (a -> b
f a
a) (a -> b
f a
b)
fmap a -> b
f (Three a
a a
b a
c) = forall a. a -> a -> a -> Digit a
Three (a -> b
f a
a) (a -> b
f a
b) (a -> b
f a
c)
fmap a -> b
f (Four a
a a
b a
c a
d) = forall a. a -> a -> a -> a -> Digit a
Four (a -> b
f a
a) (a -> b
f a
b) (a -> b
f a
c) (a -> b
f a
d)
instance Sized a => Sized (Digit a) where
size :: Digit a -> Int
size Digit a
xs = forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit (\ Int
i a
x -> Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
x) Int
0 Digit a
xs
{-# SPECIALIZE digitToTree :: Digit (Elem a) -> FingerTree (Elem a) #-}
{-# SPECIALIZE digitToTree :: Digit (Node a) -> FingerTree (Node a) #-}
digitToTree :: Sized a => Digit a -> FingerTree a
digitToTree :: forall a. Sized a => Digit a -> FingerTree a
digitToTree (One a
a) = forall a. a -> FingerTree a
Single a
a
digitToTree (Two a
a a
b) = forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (forall a. a -> Digit a
One a
a) forall a. FingerTree a
Empty (forall a. a -> Digit a
One a
b)
digitToTree (Three a
a a
b a
c) = forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (forall a. a -> a -> Digit a
Two a
a a
b) forall a. FingerTree a
Empty (forall a. a -> Digit a
One a
c)
digitToTree (Four a
a a
b a
c a
d) = forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (forall a. a -> a -> Digit a
Two a
a a
b) forall a. FingerTree a
Empty (forall a. a -> a -> Digit a
Two a
c a
d)
data Node a
= Node2 {-# UNPACK #-} !Int a a
| Node3 {-# UNPACK #-} !Int a a a
#if TESTING
deriving Show
#endif
instance Functor (Node) where
fmap :: forall a b. (a -> b) -> Node a -> Node b
fmap a -> b
f (Node2 Int
v a
a a
b) = forall a. Int -> a -> a -> Node a
Node2 Int
v (a -> b
f a
a) (a -> b
f a
b)
fmap a -> b
f (Node3 Int
v a
a a
b a
c) = forall a. Int -> a -> a -> a -> Node a
Node3 Int
v (a -> b
f a
a) (a -> b
f a
b) (a -> b
f a
c)
instance Sized (Node a) where
size :: Node a -> Int
size (Node2 Int
v a
_ a
_) = Int
v
size (Node3 Int
v a
_ a
_ a
_) = Int
v
{-# INLINE node2 #-}
node2 :: Sized a => a -> a -> Node a
node2 :: forall a. Sized a => a -> a -> Node a
node2 a
a a
b = forall a. Int -> a -> a -> Node a
Node2 (forall a. Sized a => a -> Int
size a
a forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b) a
a a
b
{-# INLINE node3 #-}
node3 :: Sized a => a -> a -> a -> Node a
node3 :: forall a. Sized a => a -> a -> a -> Node a
node3 a
a a
b a
c = forall a. Int -> a -> a -> a -> Node a
Node3 (forall a. Sized a => a -> Int
size a
a forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
c) a
a a
b a
c
nodeToDigit :: Node a -> Digit a
nodeToDigit :: forall a. Node a -> Digit a
nodeToDigit (Node2 Int
_ a
a a
b) = forall a. a -> a -> Digit a
Two a
a a
b
nodeToDigit (Node3 Int
_ a
a a
b a
c) = forall a. a -> a -> a -> Digit a
Three a
a a
b a
c
newtype Elem a = Elem { forall a. Elem a -> a
getElem :: a }
instance Sized (Elem a) where
size :: Elem a -> Int
size Elem a
_ = Int
1
instance Functor Elem where
fmap :: forall a b. (a -> b) -> Elem a -> Elem b
fmap a -> b
f (Elem a
x) = forall a. a -> Elem a
Elem (a -> b
f a
x)
#ifdef TESTING
instance (Show a) => Show (Elem a) where
showsPrec p (Elem x) = showsPrec p x
#endif
empty :: Seq a
empty :: forall a. Seq a
empty = forall a. FingerTree (Elem a) -> Seq a
Seq forall a. FingerTree a
Empty
singleton :: a -> Seq a
singleton :: forall a. a -> Seq a
singleton a
x = forall a. FingerTree (Elem a) -> Seq a
Seq (forall a. a -> FingerTree a
Single (forall a. a -> Elem a
Elem a
x))
(<|) :: a -> Seq a -> Seq a
a
x <| :: forall a. a -> Seq a -> Seq a
<| Seq FingerTree (Elem a)
xs = forall a. FingerTree (Elem a) -> Seq a
Seq (forall a. a -> Elem a
Elem a
x forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Elem a)
xs)
{-# SPECIALIZE consTree :: Elem a -> FingerTree (Elem a) -> FingerTree (Elem a) #-}
{-# SPECIALIZE consTree :: Node a -> FingerTree (Node a) -> FingerTree (Node a) #-}
consTree :: Sized a => a -> FingerTree a -> FingerTree a
consTree :: forall a. Sized a => a -> FingerTree a -> FingerTree a
consTree a
a FingerTree a
Empty = forall a. a -> FingerTree a
Single a
a
consTree a
a (Single a
b) = forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (forall a. a -> Digit a
One a
a) forall a. FingerTree a
Empty (forall a. a -> Digit a
One a
b)
consTree a
a (Deep Int
s (Four a
b a
c a
d a
e) FingerTree (Node a)
m Digit a
sf) = FingerTree (Node a)
m seq :: forall a b. a -> b -> b
`seq`
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (forall a. Sized a => a -> Int
size a
a forall a. Num a => a -> a -> a
+ Int
s) (forall a. a -> a -> Digit a
Two a
a a
b) (forall a. Sized a => a -> a -> a -> Node a
node3 a
c a
d a
e forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
m) Digit a
sf
consTree a
a (Deep Int
s (Three a
b a
c a
d) FingerTree (Node a)
m Digit a
sf) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (forall a. Sized a => a -> Int
size a
a forall a. Num a => a -> a -> a
+ Int
s) (forall a. a -> a -> a -> a -> Digit a
Four a
a a
b a
c a
d) FingerTree (Node a)
m Digit a
sf
consTree a
a (Deep Int
s (Two a
b a
c) FingerTree (Node a)
m Digit a
sf) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (forall a. Sized a => a -> Int
size a
a forall a. Num a => a -> a -> a
+ Int
s) (forall a. a -> a -> a -> Digit a
Three a
a a
b a
c) FingerTree (Node a)
m Digit a
sf
consTree a
a (Deep Int
s (One a
b) FingerTree (Node a)
m Digit a
sf) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (forall a. Sized a => a -> Int
size a
a forall a. Num a => a -> a -> a
+ Int
s) (forall a. a -> a -> Digit a
Two a
a a
b) FingerTree (Node a)
m Digit a
sf
(|>) :: Seq a -> a -> Seq a
Seq FingerTree (Elem a)
xs |> :: forall a. Seq a -> a -> Seq a
|> a
x = forall a. FingerTree (Elem a) -> Seq a
Seq (FingerTree (Elem a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` forall a. a -> Elem a
Elem a
x)
{-# SPECIALIZE snocTree :: FingerTree (Elem a) -> Elem a -> FingerTree (Elem a) #-}
{-# SPECIALIZE snocTree :: FingerTree (Node a) -> Node a -> FingerTree (Node a) #-}
snocTree :: Sized a => FingerTree a -> a -> FingerTree a
snocTree :: forall a. Sized a => FingerTree a -> a -> FingerTree a
snocTree FingerTree a
Empty a
a = forall a. a -> FingerTree a
Single a
a
snocTree (Single a
a) a
b = forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (forall a. a -> Digit a
One a
a) forall a. FingerTree a
Empty (forall a. a -> Digit a
One a
b)
snocTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (Four a
a a
b a
c a
d)) a
e = FingerTree (Node a)
m seq :: forall a b. a -> b -> b
`seq`
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
e) Digit a
pr (FingerTree (Node a)
m forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` forall a. Sized a => a -> a -> a -> Node a
node3 a
a a
b a
c) (forall a. a -> a -> Digit a
Two a
d a
e)
snocTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (Three a
a a
b a
c)) a
d =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
d) Digit a
pr FingerTree (Node a)
m (forall a. a -> a -> a -> a -> Digit a
Four a
a a
b a
c a
d)
snocTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (Two a
a a
b)) a
c =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
c) Digit a
pr FingerTree (Node a)
m (forall a. a -> a -> a -> Digit a
Three a
a a
b a
c)
snocTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (One a
a)) a
b =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b) Digit a
pr FingerTree (Node a)
m (forall a. a -> a -> Digit a
Two a
a a
b)
(><) :: Seq a -> Seq a -> Seq a
Seq FingerTree (Elem a)
xs >< :: forall a. Seq a -> Seq a -> Seq a
>< Seq FingerTree (Elem a)
ys = forall a. FingerTree (Elem a) -> Seq a
Seq (forall a.
FingerTree (Elem a) -> FingerTree (Elem a) -> FingerTree (Elem a)
appendTree0 FingerTree (Elem a)
xs FingerTree (Elem a)
ys)
appendTree0 :: FingerTree (Elem a) -> FingerTree (Elem a) -> FingerTree (Elem a)
appendTree0 :: forall a.
FingerTree (Elem a) -> FingerTree (Elem a) -> FingerTree (Elem a)
appendTree0 FingerTree (Elem a)
Empty FingerTree (Elem a)
xs =
FingerTree (Elem a)
xs
appendTree0 FingerTree (Elem a)
xs FingerTree (Elem a)
Empty =
FingerTree (Elem a)
xs
appendTree0 (Single Elem a
x) FingerTree (Elem a)
xs =
Elem a
x forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Elem a)
xs
appendTree0 FingerTree (Elem a)
xs (Single Elem a
x) =
FingerTree (Elem a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Elem a
x
appendTree0 (Deep Int
s1 Digit (Elem a)
pr1 FingerTree (Node (Elem a))
m1 Digit (Elem a)
sf1) (Deep Int
s2 Digit (Elem a)
pr2 FingerTree (Node (Elem a))
m2 Digit (Elem a)
sf2) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 forall a. Num a => a -> a -> a
+ Int
s2) Digit (Elem a)
pr1 (forall a.
FingerTree (Node (Elem a))
-> Digit (Elem a)
-> Digit (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
addDigits0 FingerTree (Node (Elem a))
m1 Digit (Elem a)
sf1 Digit (Elem a)
pr2 FingerTree (Node (Elem a))
m2) Digit (Elem a)
sf2
addDigits0 :: FingerTree (Node (Elem a)) -> Digit (Elem a) -> Digit (Elem a) -> FingerTree (Node (Elem a)) -> FingerTree (Node (Elem a))
addDigits0 :: forall a.
FingerTree (Node (Elem a))
-> Digit (Elem a)
-> Digit (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
addDigits0 FingerTree (Node (Elem a))
m1 (One Elem a
a) (One Elem a
b) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> Node a
node2 Elem a
a Elem a
b) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (One Elem a
a) (Two Elem a
b Elem a
c) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (One Elem a
a) (Three Elem a
b Elem a
c Elem a
d) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> Node a
node2 Elem a
a Elem a
b) (forall a. Sized a => a -> a -> Node a
node2 Elem a
c Elem a
d) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (One Elem a
a) (Four Elem a
b Elem a
c Elem a
d Elem a
e) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Two Elem a
a Elem a
b) (One Elem a
c) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Two Elem a
a Elem a
b) (Two Elem a
c Elem a
d) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> Node a
node2 Elem a
a Elem a
b) (forall a. Sized a => a -> a -> Node a
node2 Elem a
c Elem a
d) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Two Elem a
a Elem a
b) (Three Elem a
c Elem a
d Elem a
e) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Two Elem a
a Elem a
b) (Four Elem a
c Elem a
d Elem a
e Elem a
f) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
d Elem a
e Elem a
f) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Three Elem a
a Elem a
b Elem a
c) (One Elem a
d) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> Node a
node2 Elem a
a Elem a
b) (forall a. Sized a => a -> a -> Node a
node2 Elem a
c Elem a
d) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Three Elem a
a Elem a
b Elem a
c) (Two Elem a
d Elem a
e) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Three Elem a
a Elem a
b Elem a
c) (Three Elem a
d Elem a
e Elem a
f) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
d Elem a
e Elem a
f) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Three Elem a
a Elem a
b Elem a
c) (Four Elem a
d Elem a
e Elem a
f Elem a
g) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) (forall a. Sized a => a -> a -> Node a
node2 Elem a
f Elem a
g) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Four Elem a
a Elem a
b Elem a
c Elem a
d) (One Elem a
e) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Four Elem a
a Elem a
b Elem a
c Elem a
d) (Two Elem a
e Elem a
f) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
d Elem a
e Elem a
f) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Four Elem a
a Elem a
b Elem a
c Elem a
d) (Three Elem a
e Elem a
f Elem a
g) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) (forall a. Sized a => a -> a -> Node a
node2 Elem a
f Elem a
g) FingerTree (Node (Elem a))
m2
addDigits0 FingerTree (Node (Elem a))
m1 (Four Elem a
a Elem a
b Elem a
c Elem a
d) (Four Elem a
e Elem a
f Elem a
g Elem a
h) FingerTree (Node (Elem a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Elem a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
d Elem a
e Elem a
f) (forall a. Sized a => a -> a -> Node a
node2 Elem a
g Elem a
h) FingerTree (Node (Elem a))
m2
appendTree1 :: FingerTree (Node a) -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 :: forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node a)
Empty Node a
a FingerTree (Node a)
xs =
Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree1 FingerTree (Node a)
xs Node a
a FingerTree (Node a)
Empty =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a
appendTree1 (Single Node a
x) Node a
a FingerTree (Node a)
xs =
Node a
x forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree1 FingerTree (Node a)
xs Node a
a (Single Node a
x) =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
x
appendTree1 (Deep Int
s1 Digit (Node a)
pr1 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1) Node a
a (Deep Int
s2 Digit (Node a)
pr2 FingerTree (Node (Node a))
m2 Digit (Node a)
sf2) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
a forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits1 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1 Node a
a Digit (Node a)
pr2 FingerTree (Node (Node a))
m2) Digit (Node a)
sf2
addDigits1 :: FingerTree (Node (Node a)) -> Digit (Node a) -> Node a -> Digit (Node a) -> FingerTree (Node (Node a)) -> FingerTree (Node (Node a))
addDigits1 :: forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits1 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b (One Node a
c) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b (Two Node a
c Node a
d) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> Node a
node2 Node a
a Node a
b) (forall a. Sized a => a -> a -> Node a
node2 Node a
c Node a
d) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b (Three Node a
c Node a
d Node a
e) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b (Four Node a
c Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c (One Node a
d) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> Node a
node2 Node a
a Node a
b) (forall a. Sized a => a -> a -> Node a
node2 Node a
c Node a
d) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c (Two Node a
d Node a
e) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c (Three Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c (Four Node a
d Node a
e Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d (One Node a
e) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d (Two Node a
e Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d (Three Node a
e Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d (Four Node a
e Node a
f Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e (One Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e (Two Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e (Three Node a
f Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits1 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e (Four Node a
f Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
appendTree2 :: FingerTree (Node a) -> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 :: forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node a)
Empty Node a
a Node a
b FingerTree (Node a)
xs =
Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree2 FingerTree (Node a)
xs Node a
a Node a
b FingerTree (Node a)
Empty =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b
appendTree2 (Single Node a
x) Node a
a Node a
b FingerTree (Node a)
xs =
Node a
x forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree2 FingerTree (Node a)
xs Node a
a Node a
b (Single Node a
x) =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
x
appendTree2 (Deep Int
s1 Digit (Node a)
pr1 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1) Node a
a Node a
b (Deep Int
s2 Digit (Node a)
pr2 FingerTree (Node (Node a))
m2 Digit (Node a)
sf2) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
a forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
b forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits2 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1 Node a
a Node a
b Digit (Node a)
pr2 FingerTree (Node (Node a))
m2) Digit (Node a)
sf2
addDigits2 :: FingerTree (Node (Node a)) -> Digit (Node a) -> Node a -> Node a -> Digit (Node a) -> FingerTree (Node (Node a)) -> FingerTree (Node (Node a))
addDigits2 :: forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits2 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c (One Node a
d) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> Node a
node2 Node a
a Node a
b) (forall a. Sized a => a -> a -> Node a
node2 Node a
c Node a
d) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c (Two Node a
d Node a
e) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c (Three Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c (Four Node a
d Node a
e Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d (One Node a
e) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d (Two Node a
e Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d (Three Node a
e Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d (Four Node a
e Node a
f Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e (One Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e (Two Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e (Three Node a
f Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e (Four Node a
f Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f (One Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f (Two Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f (Three Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits2 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f (Four Node a
g Node a
h Node a
i Node a
j) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (forall a. Sized a => a -> a -> Node a
node2 Node a
i Node a
j) FingerTree (Node (Node a))
m2
appendTree3 :: FingerTree (Node a) -> Node a -> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree3 :: forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node a)
Empty Node a
a Node a
b Node a
c FingerTree (Node a)
xs =
Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree3 FingerTree (Node a)
xs Node a
a Node a
b Node a
c FingerTree (Node a)
Empty =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
c
appendTree3 (Single Node a
x) Node a
a Node a
b Node a
c FingerTree (Node a)
xs =
Node a
x forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree3 FingerTree (Node a)
xs Node a
a Node a
b Node a
c (Single Node a
x) =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
c forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
x
appendTree3 (Deep Int
s1 Digit (Node a)
pr1 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1) Node a
a Node a
b Node a
c (Deep Int
s2 Digit (Node a)
pr2 FingerTree (Node (Node a))
m2 Digit (Node a)
sf2) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
a forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
b forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
c forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits3 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1 Node a
a Node a
b Node a
c Digit (Node a)
pr2 FingerTree (Node (Node a))
m2) Digit (Node a)
sf2
addDigits3 :: FingerTree (Node (Node a)) -> Digit (Node a) -> Node a -> Node a -> Node a -> Digit (Node a) -> FingerTree (Node (Node a)) -> FingerTree (Node (Node a))
addDigits3 :: forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits3 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d (One Node a
e) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d (Two Node a
e Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d (Three Node a
e Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d (Four Node a
e Node a
f Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e (One Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e (Two Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e (Three Node a
f Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e (Four Node a
f Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f (One Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f (Two Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f (Three Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f (Four Node a
g Node a
h Node a
i Node a
j) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (forall a. Sized a => a -> a -> Node a
node2 Node a
i Node a
j) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g (One Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g (Two Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g (Three Node a
h Node a
i Node a
j) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (forall a. Sized a => a -> a -> Node a
node2 Node a
i Node a
j) FingerTree (Node (Node a))
m2
addDigits3 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g (Four Node a
h Node a
i Node a
j Node a
k) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (forall a. Sized a => a -> a -> Node a
node2 Node a
j Node a
k) FingerTree (Node (Node a))
m2
appendTree4 :: FingerTree (Node a) -> Node a -> Node a -> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree4 :: forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node a)
Empty Node a
a Node a
b Node a
c Node a
d FingerTree (Node a)
xs =
Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
d forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree4 FingerTree (Node a)
xs Node a
a Node a
b Node a
c Node a
d FingerTree (Node a)
Empty =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
c forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
d
appendTree4 (Single Node a
x) Node a
a Node a
b Node a
c Node a
d FingerTree (Node a)
xs =
Node a
x forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
d forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` FingerTree (Node a)
xs
appendTree4 FingerTree (Node a)
xs Node a
a Node a
b Node a
c Node a
d (Single Node a
x) =
FingerTree (Node a)
xs forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
c forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
d forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
x
appendTree4 (Deep Int
s1 Digit (Node a)
pr1 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1) Node a
a Node a
b Node a
c Node a
d (Deep Int
s2 Digit (Node a)
pr2 FingerTree (Node (Node a))
m2 Digit (Node a)
sf2) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
a forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
b forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
c forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Node a
d forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits4 FingerTree (Node (Node a))
m1 Digit (Node a)
sf1 Node a
a Node a
b Node a
c Node a
d Digit (Node a)
pr2 FingerTree (Node (Node a))
m2) Digit (Node a)
sf2
addDigits4 :: FingerTree (Node (Node a)) -> Digit (Node a) -> Node a -> Node a -> Node a -> Node a -> Digit (Node a) -> FingerTree (Node (Node a)) -> FingerTree (Node (Node a))
addDigits4 :: forall a.
FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
addDigits4 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d Node a
e (One Node a
f) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d Node a
e (Two Node a
f Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d Node a
e (Three Node a
f Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (One Node a
a) Node a
b Node a
c Node a
d Node a
e (Four Node a
f Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e Node a
f (One Node a
g) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (forall a. Sized a => a -> a -> Node a
node2 Node a
f Node a
g) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e Node a
f (Two Node a
g Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e Node a
f (Three Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Two Node a
a Node a
b) Node a
c Node a
d Node a
e Node a
f (Four Node a
g Node a
h Node a
i Node a
j) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (forall a. Sized a => a -> a -> Node a
node2 Node a
i Node a
j) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f Node a
g (One Node a
h) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f Node a
g (Two Node a
h Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f Node a
g (Three Node a
h Node a
i Node a
j) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (forall a. Sized a => a -> a -> Node a
node2 Node a
i Node a
j) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Three Node a
a Node a
b Node a
c) Node a
d Node a
e Node a
f Node a
g (Four Node a
h Node a
i Node a
j Node a
k) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (forall a. Sized a => a -> a -> Node a
node2 Node a
j Node a
k) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g Node a
h (One Node a
i) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g Node a
h (Two Node a
i Node a
j) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (forall a. Sized a => a -> a -> Node a
node2 Node a
i Node a
j) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g Node a
h (Three Node a
i Node a
j Node a
k) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (forall a. Sized a => a -> a -> Node a
node2 Node a
j Node a
k) FingerTree (Node (Node a))
m2
addDigits4 FingerTree (Node (Node a))
m1 (Four Node a
a Node a
b Node a
c Node a
d) Node a
e Node a
f Node a
g Node a
h (Four Node a
i Node a
j Node a
k Node a
l) FingerTree (Node (Node a))
m2 =
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree4 FingerTree (Node (Node a))
m1 (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (forall a. Sized a => a -> a -> a -> Node a
node3 Node a
j Node a
k Node a
l) FingerTree (Node (Node a))
m2
null :: Seq a -> Bool
null :: forall a. Seq a -> Bool
null (Seq FingerTree (Elem a)
Empty) = Bool
True
null Seq a
_ = Bool
False
length :: Seq a -> Int
length :: forall a. Seq a -> Int
length (Seq FingerTree (Elem a)
xs) = forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs
data Maybe2 a b = Nothing2 | Just2 a b
data ViewL a
= EmptyL
| a :< Seq a
#ifndef __HADDOCK__
deriving (ViewL a -> ViewL a -> Bool
forall a. Eq a => ViewL a -> ViewL a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ViewL a -> ViewL a -> Bool
$c/= :: forall a. Eq a => ViewL a -> ViewL a -> Bool
== :: ViewL a -> ViewL a -> Bool
$c== :: forall a. Eq a => ViewL a -> ViewL a -> Bool
Eq, Int -> ViewL a -> ShowS
forall a. Show a => Int -> ViewL a -> ShowS
forall a. Show a => [ViewL a] -> ShowS
forall a. Show a => ViewL a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ViewL a] -> ShowS
$cshowList :: forall a. Show a => [ViewL a] -> ShowS
show :: ViewL a -> String
$cshow :: forall a. Show a => ViewL a -> String
showsPrec :: Int -> ViewL a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> ViewL a -> ShowS
Show)
#else
instance Eq a => Eq (ViewL a)
instance Show a => Show (ViewL a)
#endif
instance Functor ViewL where
fmap :: forall a b. (a -> b) -> ViewL a -> ViewL b
fmap a -> b
_ ViewL a
EmptyL = forall a. ViewL a
EmptyL
fmap a -> b
f (a
x :< Seq a
xs) = a -> b
f a
x forall a. a -> Seq a -> ViewL a
:< forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Seq a
xs
viewl :: Seq a -> ViewL a
viewl :: forall a. Seq a -> ViewL a
viewl (Seq FingerTree (Elem a)
xs) = case forall a. Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree (Elem a)
xs of
Maybe2 (Elem a) (FingerTree (Elem a))
Nothing2 -> forall a. ViewL a
EmptyL
Just2 (Elem a
x) FingerTree (Elem a)
xs' -> a
x forall a. a -> Seq a -> ViewL a
:< forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
xs'
{-# SPECIALIZE viewLTree :: FingerTree (Elem a) -> Maybe2 (Elem a) (FingerTree (Elem a)) #-}
{-# SPECIALIZE viewLTree :: FingerTree (Node a) -> Maybe2 (Node a) (FingerTree (Node a)) #-}
viewLTree :: Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree :: forall a. Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree a
Empty = forall a b. Maybe2 a b
Nothing2
viewLTree (Single a
a) = forall a b. a -> b -> Maybe2 a b
Just2 a
a forall a. FingerTree a
Empty
viewLTree (Deep Int
s (One a
a) FingerTree (Node a)
m Digit a
sf) = forall a b. a -> b -> Maybe2 a b
Just2 a
a (case forall a. Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree (Node a)
m of
Maybe2 (Node a) (FingerTree (Node a))
Nothing2 -> forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
sf
Just2 Node a
b FingerTree (Node a)
m' -> forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
a) (forall a. Node a -> Digit a
nodeToDigit Node a
b) FingerTree (Node a)
m' Digit a
sf)
viewLTree (Deep Int
s (Two a
a a
b) FingerTree (Node a)
m Digit a
sf) =
forall a b. a -> b -> Maybe2 a b
Just2 a
a (forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
a) (forall a. a -> Digit a
One a
b) FingerTree (Node a)
m Digit a
sf)
viewLTree (Deep Int
s (Three a
a a
b a
c) FingerTree (Node a)
m Digit a
sf) =
forall a b. a -> b -> Maybe2 a b
Just2 a
a (forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
a) (forall a. a -> a -> Digit a
Two a
b a
c) FingerTree (Node a)
m Digit a
sf)
viewLTree (Deep Int
s (Four a
a a
b a
c a
d) FingerTree (Node a)
m Digit a
sf) =
forall a b. a -> b -> Maybe2 a b
Just2 a
a (forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
a) (forall a. a -> a -> a -> Digit a
Three a
b a
c a
d) FingerTree (Node a)
m Digit a
sf)
data ViewR a
= EmptyR
| Seq a :> a
#ifndef __HADDOCK__
deriving (ViewR a -> ViewR a -> Bool
forall a. Eq a => ViewR a -> ViewR a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ViewR a -> ViewR a -> Bool
$c/= :: forall a. Eq a => ViewR a -> ViewR a -> Bool
== :: ViewR a -> ViewR a -> Bool
$c== :: forall a. Eq a => ViewR a -> ViewR a -> Bool
Eq, Int -> ViewR a -> ShowS
forall a. Show a => Int -> ViewR a -> ShowS
forall a. Show a => [ViewR a] -> ShowS
forall a. Show a => ViewR a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ViewR a] -> ShowS
$cshowList :: forall a. Show a => [ViewR a] -> ShowS
show :: ViewR a -> String
$cshow :: forall a. Show a => ViewR a -> String
showsPrec :: Int -> ViewR a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> ViewR a -> ShowS
Show)
#else
instance Eq a => Eq (ViewR a)
instance Show a => Show (ViewR a)
#endif
instance Functor ViewR where
fmap :: forall a b. (a -> b) -> ViewR a -> ViewR b
fmap a -> b
_ ViewR a
EmptyR = forall a. ViewR a
EmptyR
fmap a -> b
f (Seq a
xs :> a
x) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Seq a
xs forall a. Seq a -> a -> ViewR a
:> a -> b
f a
x
viewr :: Seq a -> ViewR a
viewr :: forall a. Seq a -> ViewR a
viewr (Seq FingerTree (Elem a)
xs) = case forall a. Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree (Elem a)
xs of
Maybe2 (FingerTree (Elem a)) (Elem a)
Nothing2 -> forall a. ViewR a
EmptyR
Just2 FingerTree (Elem a)
xs' (Elem a
x) -> forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
xs' forall a. Seq a -> a -> ViewR a
:> a
x
{-# SPECIALIZE viewRTree :: FingerTree (Elem a) -> Maybe2 (FingerTree (Elem a)) (Elem a) #-}
{-# SPECIALIZE viewRTree :: FingerTree (Node a) -> Maybe2 (FingerTree (Node a)) (Node a) #-}
viewRTree :: Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree :: forall a. Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree a
Empty = forall a b. Maybe2 a b
Nothing2
viewRTree (Single a
z) = forall a b. a -> b -> Maybe2 a b
Just2 forall a. FingerTree a
Empty a
z
viewRTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (One a
z)) = forall a b. a -> b -> Maybe2 a b
Just2 (case forall a. Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree (Node a)
m of
Maybe2 (FingerTree (Node a)) (Node a)
Nothing2 -> forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
pr
Just2 FingerTree (Node a)
m' Node a
y -> forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m' (forall a. Node a -> Digit a
nodeToDigit Node a
y)) a
z
viewRTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (Two a
y a
z)) =
forall a b. a -> b -> Maybe2 a b
Just2 (forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m (forall a. a -> Digit a
One a
y)) a
z
viewRTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (Three a
x a
y a
z)) =
forall a b. a -> b -> Maybe2 a b
Just2 (forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m (forall a. a -> a -> Digit a
Two a
x a
y)) a
z
viewRTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (Four a
w a
x a
y a
z)) =
forall a b. a -> b -> Maybe2 a b
Just2 (forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s forall a. Num a => a -> a -> a
- forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m (forall a. a -> a -> a -> Digit a
Three a
w a
x a
y)) a
z
index :: Seq a -> Int -> a
index :: forall a. Seq a -> Int -> a
index (Seq FingerTree (Elem a)
xs) Int
i
| Int
0 forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i forall a. Ord a => a -> a -> Bool
< forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs = case forall a. Sized a => Int -> FingerTree a -> Place a
lookupTree (-Int
i) FingerTree (Elem a)
xs of
Place Int
_ (Elem a
x) -> a
x
| Bool
otherwise = forall a. HasCallStack => String -> a
error String
"index out of bounds"
data Place a = Place {-# UNPACK #-} !Int a
#if TESTING
deriving Show
#endif
{-# SPECIALIZE lookupTree :: Int -> FingerTree (Elem a) -> Place (Elem a) #-}
{-# SPECIALIZE lookupTree :: Int -> FingerTree (Node a) -> Place (Node a) #-}
lookupTree :: Sized a => Int -> FingerTree a -> Place a
lookupTree :: forall a. Sized a => Int -> FingerTree a -> Place a
lookupTree Int
i (Single a
x) = forall a. Int -> a -> Place a
Place Int
i a
x
lookupTree Int
i (Deep Int
_ Digit a
pr FingerTree (Node a)
m Digit a
sf)
| Int
vpr forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Sized a => Int -> Digit a -> Place a
lookupDigit Int
i Digit a
pr
| Int
vm forall a. Ord a => a -> a -> Bool
> Int
0 = case forall a. Sized a => Int -> FingerTree a -> Place a
lookupTree Int
vpr FingerTree (Node a)
m of
Place Int
i' Node a
xs -> forall a. Sized a => Int -> Node a -> Place a
lookupNode Int
i' Node a
xs
| Bool
otherwise = forall a. Sized a => Int -> Digit a -> Place a
lookupDigit Int
vm Digit a
sf
where vpr :: Int
vpr = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Digit a
pr
vm :: Int
vm = Int
vpr forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size FingerTree (Node a)
m
{-# SPECIALIZE lookupNode :: Int -> Node (Elem a) -> Place (Elem a) #-}
{-# SPECIALIZE lookupNode :: Int -> Node (Node a) -> Place (Node a) #-}
lookupNode :: Sized a => Int -> Node a -> Place a
lookupNode :: forall a. Sized a => Int -> Node a -> Place a
lookupNode Int
i (Node2 Int
_ a
a a
b)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
i a
a
| Bool
otherwise = forall a. Int -> a -> Place a
Place Int
va a
b
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
lookupNode Int
i (Node3 Int
_ a
a a
b a
c)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
i a
a
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
va a
b
| Bool
otherwise = forall a. Int -> a -> Place a
Place Int
vab a
c
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
{-# SPECIALIZE lookupDigit :: Int -> Digit (Elem a) -> Place (Elem a) #-}
{-# SPECIALIZE lookupDigit :: Int -> Digit (Node a) -> Place (Node a) #-}
lookupDigit :: Sized a => Int -> Digit a -> Place a
lookupDigit :: forall a. Sized a => Int -> Digit a -> Place a
lookupDigit Int
i (One a
a) = forall a. Int -> a -> Place a
Place Int
i a
a
lookupDigit Int
i (Two a
a a
b)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
i a
a
| Bool
otherwise = forall a. Int -> a -> Place a
Place Int
va a
b
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
lookupDigit Int
i (Three a
a a
b a
c)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
i a
a
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
va a
b
| Bool
otherwise = forall a. Int -> a -> Place a
Place Int
vab a
c
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
lookupDigit Int
i (Four a
a a
b a
c a
d)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
i a
a
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
va a
b
| Int
vabc forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> Place a
Place Int
vab a
c
| Bool
otherwise = forall a. Int -> a -> Place a
Place Int
vabc a
d
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
vabc :: Int
vabc = Int
vab forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
c
update :: Int -> a -> Seq a -> Seq a
update :: forall a. Int -> a -> Seq a -> Seq a
update Int
i a
x = forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust (forall a b. a -> b -> a
const a
x) Int
i
adjust :: (a -> a) -> Int -> Seq a -> Seq a
adjust :: forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust a -> a
f Int
i (Seq FingerTree (Elem a)
xs)
| Int
0 forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i forall a. Ord a => a -> a -> Bool
< forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs = forall a. FingerTree (Elem a) -> Seq a
Seq (forall a.
Sized a =>
(Int -> a -> a) -> Int -> FingerTree a -> FingerTree a
adjustTree (forall a b. a -> b -> a
const (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
f)) (-Int
i) FingerTree (Elem a)
xs)
| Bool
otherwise = forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
xs
{-# SPECIALIZE adjustTree :: (Int -> Elem a -> Elem a) -> Int -> FingerTree (Elem a) -> FingerTree (Elem a) #-}
{-# SPECIALIZE adjustTree :: (Int -> Node a -> Node a) -> Int -> FingerTree (Node a) -> FingerTree (Node a) #-}
adjustTree :: Sized a => (Int -> a -> a) ->
Int -> FingerTree a -> FingerTree a
adjustTree :: forall a.
Sized a =>
(Int -> a -> a) -> Int -> FingerTree a -> FingerTree a
adjustTree Int -> a -> a
f Int
i (Single a
x) = forall a. a -> FingerTree a
Single (Int -> a -> a
f Int
i a
x)
adjustTree Int -> a -> a
f Int
i (Deep Int
s Digit a
pr FingerTree (Node a)
m Digit a
sf)
| Int
vpr forall a. Ord a => a -> a -> Bool
> Int
0 = forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s (forall a. Sized a => (Int -> a -> a) -> Int -> Digit a -> Digit a
adjustDigit Int -> a -> a
f Int
i Digit a
pr) FingerTree (Node a)
m Digit a
sf
| Int
vm forall a. Ord a => a -> a -> Bool
> Int
0 = forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s Digit a
pr (forall a.
Sized a =>
(Int -> a -> a) -> Int -> FingerTree a -> FingerTree a
adjustTree (forall a. Sized a => (Int -> a -> a) -> Int -> Node a -> Node a
adjustNode Int -> a -> a
f) Int
vpr FingerTree (Node a)
m) Digit a
sf
| Bool
otherwise = forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s Digit a
pr FingerTree (Node a)
m (forall a. Sized a => (Int -> a -> a) -> Int -> Digit a -> Digit a
adjustDigit Int -> a -> a
f Int
vm Digit a
sf)
where vpr :: Int
vpr = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Digit a
pr
vm :: Int
vm = Int
vpr forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size FingerTree (Node a)
m
{-# SPECIALIZE adjustNode :: (Int -> Elem a -> Elem a) -> Int -> Node (Elem a) -> Node (Elem a) #-}
{-# SPECIALIZE adjustNode :: (Int -> Node a -> Node a) -> Int -> Node (Node a) -> Node (Node a) #-}
adjustNode :: Sized a => (Int -> a -> a) -> Int -> Node a -> Node a
adjustNode :: forall a. Sized a => (Int -> a -> a) -> Int -> Node a -> Node a
adjustNode Int -> a -> a
f Int
i (Node2 Int
s a
a a
b)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> a -> Node a
Node2 Int
s (Int -> a -> a
f Int
i a
a) a
b
| Bool
otherwise = forall a. Int -> a -> a -> Node a
Node2 Int
s a
a (Int -> a -> a
f Int
va a
b)
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
adjustNode Int -> a -> a
f Int
i (Node3 Int
s a
a a
b a
c)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> a -> a -> Node a
Node3 Int
s (Int -> a -> a
f Int
i a
a) a
b a
c
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> a -> a -> a -> Node a
Node3 Int
s a
a (Int -> a -> a
f Int
va a
b) a
c
| Bool
otherwise = forall a. Int -> a -> a -> a -> Node a
Node3 Int
s a
a a
b (Int -> a -> a
f Int
vab a
c)
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
{-# SPECIALIZE adjustDigit :: (Int -> Elem a -> Elem a) -> Int -> Digit (Elem a) -> Digit (Elem a) #-}
{-# SPECIALIZE adjustDigit :: (Int -> Node a -> Node a) -> Int -> Digit (Node a) -> Digit (Node a) #-}
adjustDigit :: Sized a => (Int -> a -> a) -> Int -> Digit a -> Digit a
adjustDigit :: forall a. Sized a => (Int -> a -> a) -> Int -> Digit a -> Digit a
adjustDigit Int -> a -> a
f Int
i (One a
a) = forall a. a -> Digit a
One (Int -> a -> a
f Int
i a
a)
adjustDigit Int -> a -> a
f Int
i (Two a
a a
b)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. a -> a -> Digit a
Two (Int -> a -> a
f Int
i a
a) a
b
| Bool
otherwise = forall a. a -> a -> Digit a
Two a
a (Int -> a -> a
f Int
va a
b)
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
adjustDigit Int -> a -> a
f Int
i (Three a
a a
b a
c)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. a -> a -> a -> Digit a
Three (Int -> a -> a
f Int
i a
a) a
b a
c
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. a -> a -> a -> Digit a
Three a
a (Int -> a -> a
f Int
va a
b) a
c
| Bool
otherwise = forall a. a -> a -> a -> Digit a
Three a
a a
b (Int -> a -> a
f Int
vab a
c)
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
adjustDigit Int -> a -> a
f Int
i (Four a
a a
b a
c a
d)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. a -> a -> a -> a -> Digit a
Four (Int -> a -> a
f Int
i a
a) a
b a
c a
d
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. a -> a -> a -> a -> Digit a
Four a
a (Int -> a -> a
f Int
va a
b) a
c a
d
| Int
vabc forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. a -> a -> a -> a -> Digit a
Four a
a a
b (Int -> a -> a
f Int
vab a
c) a
d
| Bool
otherwise = forall a. a -> a -> a -> a -> Digit a
Four a
a a
b a
c (Int -> a -> a
f Int
vabc a
d)
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
vabc :: Int
vabc = Int
vab forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
c
take :: Int -> Seq a -> Seq a
take :: forall a. Int -> Seq a -> Seq a
take Int
i = forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt Int
i
drop :: Int -> Seq a -> Seq a
drop :: forall a. Int -> Seq a -> Seq a
drop Int
i = forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt Int
i
splitAt :: Int -> Seq a -> (Seq a, Seq a)
splitAt :: forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt Int
i (Seq FingerTree (Elem a)
xs) = (forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
l, forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
r)
where (FingerTree (Elem a)
l, FingerTree (Elem a)
r) = forall a.
Int
-> FingerTree (Elem a)
-> (FingerTree (Elem a), FingerTree (Elem a))
split Int
i FingerTree (Elem a)
xs
split :: Int -> FingerTree (Elem a) ->
(FingerTree (Elem a), FingerTree (Elem a))
split :: forall a.
Int
-> FingerTree (Elem a)
-> (FingerTree (Elem a), FingerTree (Elem a))
split Int
i FingerTree (Elem a)
Empty = Int
i seq :: forall a b. a -> b -> b
`seq` (forall a. FingerTree a
Empty, forall a. FingerTree a
Empty)
split Int
i FingerTree (Elem a)
xs
| forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs forall a. Ord a => a -> a -> Bool
> Int
i = (FingerTree (Elem a)
l, forall a. Sized a => a -> FingerTree a -> FingerTree a
consTree Elem a
x FingerTree (Elem a)
r)
| Bool
otherwise = (FingerTree (Elem a)
xs, forall a. FingerTree a
Empty)
where Split FingerTree (Elem a)
l Elem a
x FingerTree (Elem a)
r = forall a. Sized a => Int -> FingerTree a -> Split (FingerTree a) a
splitTree (-Int
i) FingerTree (Elem a)
xs
data Split t a = Split t a t
#if TESTING
deriving Show
#endif
{-# SPECIALIZE splitTree :: Int -> FingerTree (Elem a) -> Split (FingerTree (Elem a)) (Elem a) #-}
{-# SPECIALIZE splitTree :: Int -> FingerTree (Node a) -> Split (FingerTree (Node a)) (Node a) #-}
splitTree :: Sized a => Int -> FingerTree a -> Split (FingerTree a) a
splitTree :: forall a. Sized a => Int -> FingerTree a -> Split (FingerTree a) a
splitTree Int
i (Single a
x) = Int
i seq :: forall a b. a -> b -> b
`seq` forall t a. t -> a -> t -> Split t a
Split forall a. FingerTree a
Empty a
x forall a. FingerTree a
Empty
splitTree Int
i (Deep Int
_ Digit a
pr FingerTree (Node a)
m Digit a
sf)
| Int
vpr forall a. Ord a => a -> a -> Bool
> Int
0 = case forall a. Sized a => Int -> Digit a -> Split (Maybe (Digit a)) a
splitDigit Int
i Digit a
pr of
Split Maybe (Digit a)
l a
x Maybe (Digit a)
r -> forall t a. t -> a -> t -> Split t a
Split (forall b a. b -> (a -> b) -> Maybe a -> b
maybe forall a. FingerTree a
Empty forall a. Sized a => Digit a -> FingerTree a
digitToTree Maybe (Digit a)
l) a
x (forall a.
Sized a =>
Maybe (Digit a) -> FingerTree (Node a) -> Digit a -> FingerTree a
deepL Maybe (Digit a)
r FingerTree (Node a)
m Digit a
sf)
| Int
vm forall a. Ord a => a -> a -> Bool
> Int
0 = case forall a. Sized a => Int -> FingerTree a -> Split (FingerTree a) a
splitTree Int
vpr FingerTree (Node a)
m of
Split FingerTree (Node a)
ml Node a
xs FingerTree (Node a)
mr -> case forall a. Sized a => Int -> Node a -> Split (Maybe (Digit a)) a
splitNode (Int
vpr forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size FingerTree (Node a)
ml) Node a
xs of
Split Maybe (Digit a)
l a
x Maybe (Digit a)
r -> forall t a. t -> a -> t -> Split t a
Split (forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Maybe (Digit a) -> FingerTree a
deepR Digit a
pr FingerTree (Node a)
ml Maybe (Digit a)
l) a
x (forall a.
Sized a =>
Maybe (Digit a) -> FingerTree (Node a) -> Digit a -> FingerTree a
deepL Maybe (Digit a)
r FingerTree (Node a)
mr Digit a
sf)
| Bool
otherwise = case forall a. Sized a => Int -> Digit a -> Split (Maybe (Digit a)) a
splitDigit Int
vm Digit a
sf of
Split Maybe (Digit a)
l a
x Maybe (Digit a)
r -> forall t a. t -> a -> t -> Split t a
Split (forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Maybe (Digit a) -> FingerTree a
deepR Digit a
pr FingerTree (Node a)
m Maybe (Digit a)
l) a
x (forall b a. b -> (a -> b) -> Maybe a -> b
maybe forall a. FingerTree a
Empty forall a. Sized a => Digit a -> FingerTree a
digitToTree Maybe (Digit a)
r)
where vpr :: Int
vpr = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size Digit a
pr
vm :: Int
vm = Int
vpr forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size FingerTree (Node a)
m
{-# SPECIALIZE deepL :: Maybe (Digit (Elem a)) -> FingerTree (Node (Elem a)) -> Digit (Elem a) -> FingerTree (Elem a) #-}
{-# SPECIALIZE deepL :: Maybe (Digit (Node a)) -> FingerTree (Node (Node a)) -> Digit (Node a) -> FingerTree (Node a) #-}
deepL :: Sized a => Maybe (Digit a) -> FingerTree (Node a) -> Digit a -> FingerTree a
deepL :: forall a.
Sized a =>
Maybe (Digit a) -> FingerTree (Node a) -> Digit a -> FingerTree a
deepL Maybe (Digit a)
Nothing FingerTree (Node a)
m Digit a
sf = case forall a. Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree (Node a)
m of
Maybe2 (Node a) (FingerTree (Node a))
Nothing2 -> forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
sf
Just2 Node a
a FingerTree (Node a)
m' -> forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (forall a. Node a -> Digit a
nodeToDigit Node a
a) FingerTree (Node a)
m' Digit a
sf
deepL (Just Digit a
pr) FingerTree (Node a)
m Digit a
sf = forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep Digit a
pr FingerTree (Node a)
m Digit a
sf
{-# SPECIALIZE deepR :: Digit (Elem a) -> FingerTree (Node (Elem a)) -> Maybe (Digit (Elem a)) -> FingerTree (Elem a) #-}
{-# SPECIALIZE deepR :: Digit (Node a) -> FingerTree (Node (Node a)) -> Maybe (Digit (Node a)) -> FingerTree (Node a) #-}
deepR :: Sized a => Digit a -> FingerTree (Node a) -> Maybe (Digit a) -> FingerTree a
deepR :: forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Maybe (Digit a) -> FingerTree a
deepR Digit a
pr FingerTree (Node a)
m Maybe (Digit a)
Nothing = case forall a. Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree (Node a)
m of
Maybe2 (FingerTree (Node a)) (Node a)
Nothing2 -> forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
pr
Just2 FingerTree (Node a)
m' Node a
a -> forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep Digit a
pr FingerTree (Node a)
m' (forall a. Node a -> Digit a
nodeToDigit Node a
a)
deepR Digit a
pr FingerTree (Node a)
m (Just Digit a
sf) = forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep Digit a
pr FingerTree (Node a)
m Digit a
sf
{-# SPECIALIZE splitNode :: Int -> Node (Elem a) -> Split (Maybe (Digit (Elem a))) (Elem a) #-}
{-# SPECIALIZE splitNode :: Int -> Node (Node a) -> Split (Maybe (Digit (Node a))) (Node a) #-}
splitNode :: Sized a => Int -> Node a -> Split (Maybe (Digit a)) a
splitNode :: forall a. Sized a => Int -> Node a -> Split (Maybe (Digit a)) a
splitNode Int
i (Node2 Int
_ a
a a
b)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split forall a. Maybe a
Nothing a
a (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
b))
| Bool
otherwise = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
a)) a
b forall a. Maybe a
Nothing
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
splitNode Int
i (Node3 Int
_ a
a a
b a
c)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split forall a. Maybe a
Nothing a
a (forall a. a -> Maybe a
Just (forall a. a -> a -> Digit a
Two a
b a
c))
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
a)) a
b (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
c))
| Bool
otherwise = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> a -> Digit a
Two a
a a
b)) a
c forall a. Maybe a
Nothing
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
{-# SPECIALIZE splitDigit :: Int -> Digit (Elem a) -> Split (Maybe (Digit (Elem a))) (Elem a) #-}
{-# SPECIALIZE splitDigit :: Int -> Digit (Node a) -> Split (Maybe (Digit (Node a))) (Node a) #-}
splitDigit :: Sized a => Int -> Digit a -> Split (Maybe (Digit a)) a
splitDigit :: forall a. Sized a => Int -> Digit a -> Split (Maybe (Digit a)) a
splitDigit Int
i (One a
a) = Int
i seq :: forall a b. a -> b -> b
`seq` forall t a. t -> a -> t -> Split t a
Split forall a. Maybe a
Nothing a
a forall a. Maybe a
Nothing
splitDigit Int
i (Two a
a a
b)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split forall a. Maybe a
Nothing a
a (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
b))
| Bool
otherwise = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
a)) a
b forall a. Maybe a
Nothing
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
splitDigit Int
i (Three a
a a
b a
c)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split forall a. Maybe a
Nothing a
a (forall a. a -> Maybe a
Just (forall a. a -> a -> Digit a
Two a
b a
c))
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
a)) a
b (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
c))
| Bool
otherwise = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> a -> Digit a
Two a
a a
b)) a
c forall a. Maybe a
Nothing
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
splitDigit Int
i (Four a
a a
b a
c a
d)
| Int
va forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split forall a. Maybe a
Nothing a
a (forall a. a -> Maybe a
Just (forall a. a -> a -> a -> Digit a
Three a
b a
c a
d))
| Int
vab forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
a)) a
b (forall a. a -> Maybe a
Just (forall a. a -> a -> Digit a
Two a
c a
d))
| Int
vabc forall a. Ord a => a -> a -> Bool
> Int
0 = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> a -> Digit a
Two a
a a
b)) a
c (forall a. a -> Maybe a
Just (forall a. a -> Digit a
One a
d))
| Bool
otherwise = forall t a. t -> a -> t -> Split t a
Split (forall a. a -> Maybe a
Just (forall a. a -> a -> a -> Digit a
Three a
a a
b a
c)) a
d forall a. Maybe a
Nothing
where va :: Int
va = Int
i forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
a
vab :: Int
vab = Int
va forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
b
vabc :: Int
vabc = Int
vab forall a. Num a => a -> a -> a
+ forall a. Sized a => a -> Int
size a
c
fromList :: [a] -> Seq a
fromList :: forall a. [a] -> Seq a
fromList = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Data.List.foldl' forall a. Seq a -> a -> Seq a
(|>) forall a. Seq a
empty
toList :: Seq a -> [a]
toList :: forall a. Seq a -> [a]
toList = forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr (:) []
foldr :: (a -> b -> b) -> b -> Seq a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr a -> b -> b
f b
z (Seq FingerTree (Elem a)
xs) = forall a b. (a -> b -> b) -> b -> FingerTree a -> b
foldrTree Elem a -> b -> b
f' b
z FingerTree (Elem a)
xs
where f' :: Elem a -> b -> b
f' (Elem a
x) b
y = a -> b -> b
f a
x b
y
foldrTree :: (a -> b -> b) -> b -> FingerTree a -> b
foldrTree :: forall a b. (a -> b -> b) -> b -> FingerTree a -> b
foldrTree a -> b -> b
_ b
z FingerTree a
Empty = b
z
foldrTree a -> b -> b
f b
z (Single a
x) = a
x a -> b -> b
`f` b
z
foldrTree a -> b -> b
f b
z (Deep Int
_ Digit a
pr FingerTree (Node a)
m Digit a
sf) =
forall a b. (a -> b -> b) -> b -> Digit a -> b
foldrDigit a -> b -> b
f (forall a b. (a -> b -> b) -> b -> FingerTree a -> b
foldrTree (forall a b c. (a -> b -> c) -> b -> a -> c
flip (forall a b. (a -> b -> b) -> b -> Node a -> b
foldrNode a -> b -> b
f)) (forall a b. (a -> b -> b) -> b -> Digit a -> b
foldrDigit a -> b -> b
f b
z Digit a
sf) FingerTree (Node a)
m) Digit a
pr
foldrDigit :: (a -> b -> b) -> b -> Digit a -> b
foldrDigit :: forall a b. (a -> b -> b) -> b -> Digit a -> b
foldrDigit a -> b -> b
f b
z (One a
a) = a
a a -> b -> b
`f` b
z
foldrDigit a -> b -> b
f b
z (Two a
a a
b) = a
a a -> b -> b
`f` (a
b a -> b -> b
`f` b
z)
foldrDigit a -> b -> b
f b
z (Three a
a a
b a
c) = a
a a -> b -> b
`f` (a
b a -> b -> b
`f` (a
c a -> b -> b
`f` b
z))
foldrDigit a -> b -> b
f b
z (Four a
a a
b a
c a
d) = a
a a -> b -> b
`f` (a
b a -> b -> b
`f` (a
c a -> b -> b
`f` (a
d a -> b -> b
`f` b
z)))
foldrNode :: (a -> b -> b) -> b -> Node a -> b
foldrNode :: forall a b. (a -> b -> b) -> b -> Node a -> b
foldrNode a -> b -> b
f b
z (Node2 Int
_ a
a a
b) = a
a a -> b -> b
`f` (a
b a -> b -> b
`f` b
z)
foldrNode a -> b -> b
f b
z (Node3 Int
_ a
a a
b a
c) = a
a a -> b -> b
`f` (a
b a -> b -> b
`f` (a
c a -> b -> b
`f` b
z))
foldr1 :: (a -> a -> a) -> Seq a -> a
foldr1 :: forall a. (a -> a -> a) -> Seq a -> a
foldr1 a -> a -> a
f (Seq FingerTree (Elem a)
xs) = forall a. Elem a -> a
getElem (forall a. (a -> a -> a) -> FingerTree a -> a
foldr1Tree Elem a -> Elem a -> Elem a
f' FingerTree (Elem a)
xs)
where f' :: Elem a -> Elem a -> Elem a
f' (Elem a
x) (Elem a
y) = forall a. a -> Elem a
Elem (a -> a -> a
f a
x a
y)
foldr1Tree :: (a -> a -> a) -> FingerTree a -> a
foldr1Tree :: forall a. (a -> a -> a) -> FingerTree a -> a
foldr1Tree a -> a -> a
_ FingerTree a
Empty = forall a. HasCallStack => String -> a
error String
"foldr1: empty sequence"
foldr1Tree a -> a -> a
_ (Single a
x) = a
x
foldr1Tree a -> a -> a
f (Deep Int
_ Digit a
pr FingerTree (Node a)
m Digit a
sf) =
forall a b. (a -> b -> b) -> b -> Digit a -> b
foldrDigit a -> a -> a
f (forall a b. (a -> b -> b) -> b -> FingerTree a -> b
foldrTree (forall a b c. (a -> b -> c) -> b -> a -> c
flip (forall a b. (a -> b -> b) -> b -> Node a -> b
foldrNode a -> a -> a
f)) (forall a. (a -> a -> a) -> Digit a -> a
foldr1Digit a -> a -> a
f Digit a
sf) FingerTree (Node a)
m) Digit a
pr
foldr1Digit :: (a -> a -> a) -> Digit a -> a
foldr1Digit :: forall a. (a -> a -> a) -> Digit a -> a
foldr1Digit a -> a -> a
f (One a
a) = a
a
foldr1Digit a -> a -> a
f (Two a
a a
b) = a
a a -> a -> a
`f` a
b
foldr1Digit a -> a -> a
f (Three a
a a
b a
c) = a
a a -> a -> a
`f` (a
b a -> a -> a
`f` a
c)
foldr1Digit a -> a -> a
f (Four a
a a
b a
c a
d) = a
a a -> a -> a
`f` (a
b a -> a -> a
`f` (a
c a -> a -> a
`f` a
d))
foldl :: (a -> b -> a) -> a -> Seq b -> a
foldl :: forall a b. (a -> b -> a) -> a -> Seq b -> a
foldl a -> b -> a
f a
z (Seq FingerTree (Elem b)
xs) = forall a b. (a -> b -> a) -> a -> FingerTree b -> a
foldlTree a -> Elem b -> a
f' a
z FingerTree (Elem b)
xs
where f' :: a -> Elem b -> a
f' a
x (Elem b
y) = a -> b -> a
f a
x b
y
foldlTree :: (a -> b -> a) -> a -> FingerTree b -> a
foldlTree :: forall a b. (a -> b -> a) -> a -> FingerTree b -> a
foldlTree a -> b -> a
_ a
z FingerTree b
Empty = a
z
foldlTree a -> b -> a
f a
z (Single b
x) = a
z a -> b -> a
`f` b
x
foldlTree a -> b -> a
f a
z (Deep Int
_ Digit b
pr FingerTree (Node b)
m Digit b
sf) =
forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit a -> b -> a
f (forall a b. (a -> b -> a) -> a -> FingerTree b -> a
foldlTree (forall a b. (a -> b -> a) -> a -> Node b -> a
foldlNode a -> b -> a
f) (forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit a -> b -> a
f a
z Digit b
pr) FingerTree (Node b)
m) Digit b
sf
foldlDigit :: (a -> b -> a) -> a -> Digit b -> a
foldlDigit :: forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit a -> b -> a
f a
z (One b
a) = a
z a -> b -> a
`f` b
a
foldlDigit a -> b -> a
f a
z (Two b
a b
b) = (a
z a -> b -> a
`f` b
a) a -> b -> a
`f` b
b
foldlDigit a -> b -> a
f a
z (Three b
a b
b b
c) = ((a
z a -> b -> a
`f` b
a) a -> b -> a
`f` b
b) a -> b -> a
`f` b
c
foldlDigit a -> b -> a
f a
z (Four b
a b
b b
c b
d) = (((a
z a -> b -> a
`f` b
a) a -> b -> a
`f` b
b) a -> b -> a
`f` b
c) a -> b -> a
`f` b
d
foldlNode :: (a -> b -> a) -> a -> Node b -> a
foldlNode :: forall a b. (a -> b -> a) -> a -> Node b -> a
foldlNode a -> b -> a
f a
z (Node2 Int
_ b
a b
b) = (a
z a -> b -> a
`f` b
a) a -> b -> a
`f` b
b
foldlNode a -> b -> a
f a
z (Node3 Int
_ b
a b
b b
c) = ((a
z a -> b -> a
`f` b
a) a -> b -> a
`f` b
b) a -> b -> a
`f` b
c
foldl1 :: (a -> a -> a) -> Seq a -> a
foldl1 :: forall a. (a -> a -> a) -> Seq a -> a
foldl1 a -> a -> a
f (Seq FingerTree (Elem a)
xs) = forall a. Elem a -> a
getElem (forall a. (a -> a -> a) -> FingerTree a -> a
foldl1Tree Elem a -> Elem a -> Elem a
f' FingerTree (Elem a)
xs)
where f' :: Elem a -> Elem a -> Elem a
f' (Elem a
x) (Elem a
y) = forall a. a -> Elem a
Elem (a -> a -> a
f a
x a
y)
foldl1Tree :: (a -> a -> a) -> FingerTree a -> a
foldl1Tree :: forall a. (a -> a -> a) -> FingerTree a -> a
foldl1Tree a -> a -> a
_ FingerTree a
Empty = forall a. HasCallStack => String -> a
error String
"foldl1: empty sequence"
foldl1Tree a -> a -> a
_ (Single a
x) = a
x
foldl1Tree a -> a -> a
f (Deep Int
_ Digit a
pr FingerTree (Node a)
m Digit a
sf) =
forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit a -> a -> a
f (forall a b. (a -> b -> a) -> a -> FingerTree b -> a
foldlTree (forall a b. (a -> b -> a) -> a -> Node b -> a
foldlNode a -> a -> a
f) (forall a. (a -> a -> a) -> Digit a -> a
foldl1Digit a -> a -> a
f Digit a
pr) FingerTree (Node a)
m) Digit a
sf
foldl1Digit :: (a -> a -> a) -> Digit a -> a
foldl1Digit :: forall a. (a -> a -> a) -> Digit a -> a
foldl1Digit a -> a -> a
f (One a
a) = a
a
foldl1Digit a -> a -> a
f (Two a
a a
b) = a
a a -> a -> a
`f` a
b
foldl1Digit a -> a -> a
f (Three a
a a
b a
c) = (a
a a -> a -> a
`f` a
b) a -> a -> a
`f` a
c
foldl1Digit a -> a -> a
f (Four a
a a
b a
c a
d) = ((a
a a -> a -> a
`f` a
b) a -> a -> a
`f` a
c) a -> a -> a
`f` a
d
foldr' :: (a -> b -> b) -> b -> Seq a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr' a -> b -> b
f b
z Seq a
xs = forall a b. (a -> b -> a) -> a -> Seq b -> a
foldl forall {b}. (b -> b) -> a -> b -> b
f' forall a. a -> a
id Seq a
xs b
z
where f' :: (b -> b) -> a -> b -> b
f' b -> b
k a
x b
z = b -> b
k forall a b. (a -> b) -> a -> b
$! a -> b -> b
f a
x b
z
foldrM :: Monad m => (a -> b -> m b) -> b -> Seq a -> m b
foldrM :: forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m b) -> b -> Seq a -> m b
foldrM a -> b -> m b
f b
z Seq a
xs = forall a b. (a -> b -> a) -> a -> Seq b -> a
foldl forall {b}. (b -> m b) -> a -> b -> m b
f' forall (m :: * -> *) a. Monad m => a -> m a
return Seq a
xs b
z
where f' :: (b -> m b) -> a -> b -> m b
f' b -> m b
k a
x b
z = a -> b -> m b
f a
x b
z forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= b -> m b
k
foldl' :: (a -> b -> a) -> a -> Seq b -> a
foldl' :: forall a b. (a -> b -> a) -> a -> Seq b -> a
foldl' a -> b -> a
f a
z Seq b
xs = forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr forall {b}. b -> (a -> b) -> a -> b
f' forall a. a -> a
id Seq b
xs a
z
where f' :: b -> (a -> b) -> a -> b
f' b
x a -> b
k a
z = a -> b
k forall a b. (a -> b) -> a -> b
$! a -> b -> a
f a
z b
x
foldlM :: Monad m => (a -> b -> m a) -> a -> Seq b -> m a
foldlM :: forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Seq b -> m a
foldlM a -> b -> m a
f a
z Seq b
xs = forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr forall {b}. b -> (a -> m b) -> a -> m b
f' forall (m :: * -> *) a. Monad m => a -> m a
return Seq b
xs a
z
where f' :: b -> (a -> m b) -> a -> m b
f' b
x a -> m b
k a
z = a -> b -> m a
f a
z b
x forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> m b
k
reverse :: Seq a -> Seq a
reverse :: forall a. Seq a -> Seq a
reverse (Seq FingerTree (Elem a)
xs) = forall a. FingerTree (Elem a) -> Seq a
Seq (forall a. (a -> a) -> FingerTree a -> FingerTree a
reverseTree forall a. a -> a
id FingerTree (Elem a)
xs)
reverseTree :: (a -> a) -> FingerTree a -> FingerTree a
reverseTree :: forall a. (a -> a) -> FingerTree a -> FingerTree a
reverseTree a -> a
_ FingerTree a
Empty = forall a. FingerTree a
Empty
reverseTree a -> a
f (Single a
x) = forall a. a -> FingerTree a
Single (a -> a
f a
x)
reverseTree a -> a
f (Deep Int
s Digit a
pr FingerTree (Node a)
m Digit a
sf) =
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s (forall a. (a -> a) -> Digit a -> Digit a
reverseDigit a -> a
f Digit a
sf)
(forall a. (a -> a) -> FingerTree a -> FingerTree a
reverseTree (forall a. (a -> a) -> Node a -> Node a
reverseNode a -> a
f) FingerTree (Node a)
m)
(forall a. (a -> a) -> Digit a -> Digit a
reverseDigit a -> a
f Digit a
pr)
reverseDigit :: (a -> a) -> Digit a -> Digit a
reverseDigit :: forall a. (a -> a) -> Digit a -> Digit a
reverseDigit a -> a
f (One a
a) = forall a. a -> Digit a
One (a -> a
f a
a)
reverseDigit a -> a
f (Two a
a a
b) = forall a. a -> a -> Digit a
Two (a -> a
f a
b) (a -> a
f a
a)
reverseDigit a -> a
f (Three a
a a
b a
c) = forall a. a -> a -> a -> Digit a
Three (a -> a
f a
c) (a -> a
f a
b) (a -> a
f a
a)
reverseDigit a -> a
f (Four a
a a
b a
c a
d) = forall a. a -> a -> a -> a -> Digit a
Four (a -> a
f a
d) (a -> a
f a
c) (a -> a
f a
b) (a -> a
f a
a)
reverseNode :: (a -> a) -> Node a -> Node a
reverseNode :: forall a. (a -> a) -> Node a -> Node a
reverseNode a -> a
f (Node2 Int
s a
a a
b) = forall a. Int -> a -> a -> Node a
Node2 Int
s (a -> a
f a
b) (a -> a
f a
a)
reverseNode a -> a
f (Node3 Int
s a
a a
b a
c) = forall a. Int -> a -> a -> a -> Node a
Node3 Int
s (a -> a
f a
c) (a -> a
f a
b) (a -> a
f a
a)
#if TESTING
instance Arbitrary a => Arbitrary (Seq a) where
arbitrary = liftM Seq arbitrary
coarbitrary (Seq x) = coarbitrary x
instance Arbitrary a => Arbitrary (Elem a) where
arbitrary = liftM Elem arbitrary
coarbitrary (Elem x) = coarbitrary x
instance (Arbitrary a, Sized a) => Arbitrary (FingerTree a) where
arbitrary = sized arb
where arb :: (Arbitrary a, Sized a) => Int -> Gen (FingerTree a)
arb 0 = return Empty
arb 1 = liftM Single arbitrary
arb n = liftM3 deep arbitrary (arb (n `div` 2)) arbitrary
coarbitrary Empty = variant 0
coarbitrary (Single x) = variant 1 . coarbitrary x
coarbitrary (Deep _ pr m sf) =
variant 2 . coarbitrary pr . coarbitrary m . coarbitrary sf
instance (Arbitrary a, Sized a) => Arbitrary (Node a) where
arbitrary = oneof [
liftM2 node2 arbitrary arbitrary,
liftM3 node3 arbitrary arbitrary arbitrary]
coarbitrary (Node2 _ a b) = variant 0 . coarbitrary a . coarbitrary b
coarbitrary (Node3 _ a b c) =
variant 1 . coarbitrary a . coarbitrary b . coarbitrary c
instance Arbitrary a => Arbitrary (Digit a) where
arbitrary = oneof [
liftM One arbitrary,
liftM2 Two arbitrary arbitrary,
liftM3 Three arbitrary arbitrary arbitrary,
liftM4 Four arbitrary arbitrary arbitrary arbitrary]
coarbitrary (One a) = variant 0 . coarbitrary a
coarbitrary (Two a b) = variant 1 . coarbitrary a . coarbitrary b
coarbitrary (Three a b c) =
variant 2 . coarbitrary a . coarbitrary b . coarbitrary c
coarbitrary (Four a b c d) =
variant 3 . coarbitrary a . coarbitrary b . coarbitrary c . coarbitrary d
class Valid a where
valid :: a -> Bool
instance Valid (Elem a) where
valid _ = True
instance Valid (Seq a) where
valid (Seq xs) = valid xs
instance (Sized a, Valid a) => Valid (FingerTree a) where
valid Empty = True
valid (Single x) = valid x
valid (Deep s pr m sf) =
s == size pr + size m + size sf && valid pr && valid m && valid sf
instance (Sized a, Valid a) => Valid (Node a) where
valid (Node2 s a b) = s == size a + size b && valid a && valid b
valid (Node3 s a b c) =
s == size a + size b + size c && valid a && valid b && valid c
instance Valid a => Valid (Digit a) where
valid (One a) = valid a
valid (Two a b) = valid a && valid b
valid (Three a b c) = valid a && valid b && valid c
valid (Four a b c d) = valid a && valid b && valid c && valid d
#endif