{-# LANGUAGE CPP #-}
{-# OPTIONS_HADDOCK hide #-}
-- #hide
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Sequence
-- Copyright   :  (c) Ross Paterson 2005
-- License     :  BSD-style
-- Maintainer  :  ross@soi.city.ac.uk
-- Stability   :  experimental
-- Portability :  portable
--
-- General purpose finite sequences.
-- Apart from being finite and having strict operations, sequences
-- also differ from lists in supporting a wider variety of operations
-- efficiently.
--
-- An amortized running time is given for each operation, with /n/ referring
-- to the length of the sequence and /i/ being the integral index used by
-- some operations.  These bounds hold even in a persistent (shared) setting.
--
-- The implementation uses 2-3 finger trees annotated with sizes,
-- as described in section 4.2 of
--
--    * Ralf Hinze and Ross Paterson,
--      \"Finger trees: a simple general-purpose data structure\",
--      submitted to /Journal of Functional Programming/.
--      <http://www.soi.city.ac.uk/~ross/papers/FingerTree.html>
--
-----------------------------------------------------------------------------

module Graphics.UI.Gtk.ModelView.Sequence (
        Seq,
        -- * Construction
        empty,          -- :: Seq a
        singleton,      -- :: a -> Seq a
        (<|),           -- :: a -> Seq a -> Seq a
        (|>),           -- :: Seq a -> a -> Seq a
        (><),           -- :: Seq a -> Seq a -> Seq a
        -- * Deconstruction
        null,           -- :: Seq a -> Bool
        -- ** Views
        ViewL(..),
        viewl,          -- :: Seq a -> ViewL a
        ViewR(..),
        viewr,          -- :: Seq a -> ViewR a
        -- ** Indexing
        length,         -- :: Seq a -> Int
        index,          -- :: Seq a -> Int -> a
        adjust,         -- :: (a -> a) -> Int -> Seq a -> Seq a
        update,         -- :: Int -> a -> Seq a -> Seq a
        take,           -- :: Int -> Seq a -> Seq a
        drop,           -- :: Int -> Seq a -> Seq a
        splitAt,        -- :: Int -> Seq a -> (Seq a, Seq a)
        -- * Lists
        fromList,       -- :: [a] -> Seq a
        toList,         -- :: Seq a -> [a]
        -- * Folds
        -- ** Right associative
        foldr,          -- :: (a -> b -> b) -> b -> Seq a -> b
        foldr1,         -- :: (a -> a -> a) -> Seq a -> a
        foldr',         -- :: (a -> b -> b) -> b -> Seq a -> b
        foldrM,         -- :: Monad m => (a -> b -> m b) -> b -> Seq a -> m b
        -- ** Left associative
        foldl,          -- :: (a -> b -> a) -> a -> Seq b -> a
        foldl1,         -- :: (a -> a -> a) -> Seq a -> a
        foldl',         -- :: (a -> b -> a) -> a -> Seq b -> a
        foldlM,         -- :: Monad m => (a -> b -> m a) -> a -> Seq b -> m a
        -- * Transformations
        reverse,        -- :: Seq a -> Seq a
#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

------------------------------------------------------------------------
-- Random access sequences
------------------------------------------------------------------------

-- | General-purpose finite sequences.
newtype Seq a = Seq (FingerTree (Elem a))

instance Functor Seq where
        fmap :: (a -> b) -> Seq a -> Seq b
fmap a -> b
f (Seq FingerTree (Elem a)
xs) = FingerTree (Elem b) -> Seq b
forall a. FingerTree (Elem a) -> Seq a
Seq ((Elem a -> Elem b) -> FingerTree (Elem a) -> FingerTree (Elem b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> Elem a -> Elem b
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 = Seq a -> Int
forall a. Seq a -> Int
length Seq a
xs Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Seq a -> Int
forall a. Seq a -> Int
length Seq a
ys Bool -> Bool -> Bool
&& Seq a -> [a]
forall a. Seq a -> [a]
toList Seq a
xs [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Seq a -> [a]
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 = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Seq a -> [a]
forall a. Seq a -> [a]
toList Seq a
xs) (Seq a -> [a]
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
'<' ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
                (String -> [ShowS] -> String) -> [ShowS] -> ShowS
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((ShowS -> ShowS) -> String -> [ShowS] -> String
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr ShowS -> ShowS
forall a b. (a -> b) -> a -> b
($)) (ShowS -> [ShowS] -> [ShowS]
forall a. a -> [a] -> [a]
intersperse (Char -> ShowS
showChar Char
',')
                                                ((a -> ShowS) -> [a] -> [ShowS]
forall a b. (a -> b) -> [a] -> [b]
map a -> ShowS
forall a. Show a => a -> ShowS
shows (Seq a -> [a]
forall a. Seq a -> [a]
toList Seq a
xs))) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
                Char -> ShowS
showChar Char
'>'
#endif

-- Finger trees

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)         = a -> Int
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 :: (a -> b) -> FingerTree a -> FingerTree b
fmap a -> b
_ FingerTree a
Empty = FingerTree b
forall a. FingerTree a
Empty
        fmap a -> b
f (Single a
x) = b -> FingerTree b
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) =
                Int -> Digit b -> FingerTree (Node b) -> Digit b -> FingerTree b
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
v ((a -> b) -> Digit a -> Digit b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Digit a
pr) ((Node a -> Node b) -> FingerTree (Node a) -> FingerTree (Node b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> Node a -> Node b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) FingerTree (Node a)
m) ((a -> b) -> Digit a -> Digit b
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 :: Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep Digit a
pr FingerTree (Node a)
m Digit a
sf    =  Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Digit a -> Int
forall a. Sized a => a -> Int
size Digit a
pr Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FingerTree (Node a) -> Int
forall a. Sized a => a -> Int
size FingerTree (Node a)
m Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Digit a -> Int
forall a. Sized a => a -> Int
size Digit a
sf) Digit a
pr FingerTree (Node a)
m Digit a
sf

-- Digits

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 :: (a -> b) -> Digit a -> Digit b
fmap a -> b
f (One a
a) = b -> Digit b
forall a. a -> Digit a
One (a -> b
f a
a)
        fmap a -> b
f (Two a
a a
b) = b -> b -> Digit 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) = b -> b -> b -> Digit b
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) = b -> b -> b -> b -> Digit b
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 = (Int -> a -> Int) -> Int -> Digit a -> Int
forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit (\ Int
i a
x -> Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
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 :: Digit a -> FingerTree a
digitToTree (One a
a) = a -> FingerTree a
forall a. a -> FingerTree a
Single a
a
digitToTree (Two a
a a
b) = Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (a -> Digit a
forall a. a -> Digit a
One a
a) FingerTree (Node a)
forall a. FingerTree a
Empty (a -> Digit a
forall a. a -> Digit a
One a
b)
digitToTree (Three a
a a
b a
c) = Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b) FingerTree (Node a)
forall a. FingerTree a
Empty (a -> Digit a
forall a. a -> Digit a
One a
c)
digitToTree (Four a
a a
b a
c a
d) = Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b) FingerTree (Node a)
forall a. FingerTree a
Empty (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
c a
d)

-- Nodes

data Node a
        = Node2 {-# UNPACK #-} !Int a a
        | Node3 {-# UNPACK #-} !Int a a a
#if TESTING
        deriving Show
#endif

instance Functor (Node) where
        fmap :: (a -> b) -> Node a -> Node b
fmap a -> b
f (Node2 Int
v a
a a
b) = Int -> b -> b -> Node 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) = Int -> b -> b -> b -> Node b
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 :: a -> a -> Node a
node2 a
a a
b       =  Int -> a -> a -> Node a
forall a. Int -> a -> a -> Node a
Node2 (a -> Int
forall a. Sized a => a -> Int
size a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b) a
a a
b

{-# INLINE node3 #-}
node3           :: Sized a => a -> a -> a -> Node a
node3 :: a -> a -> a -> Node a
node3 a
a a
b a
c     =  Int -> a -> a -> a -> Node a
forall a. Int -> a -> a -> a -> Node a
Node3 (a -> Int
forall a. Sized a => a -> Int
size a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
c) a
a a
b a
c

nodeToDigit :: Node a -> Digit a
nodeToDigit :: Node a -> Digit a
nodeToDigit (Node2 Int
_ a
a a
b) = a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b
nodeToDigit (Node3 Int
_ a
a a
b a
c) = a -> a -> a -> Digit a
forall a. a -> a -> a -> Digit a
Three a
a a
b a
c

-- Elements

newtype Elem a  =  Elem { Elem a -> a
getElem :: a }

instance Sized (Elem a) where
        size :: Elem a -> Int
size Elem a
_ = Int
1

instance Functor Elem where
        fmap :: (a -> b) -> Elem a -> Elem b
fmap a -> b
f (Elem a
x) = b -> Elem b
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

------------------------------------------------------------------------
-- Construction
------------------------------------------------------------------------

-- | /O(1)/. The empty sequence.
empty           :: Seq a
empty :: Seq a
empty           =  FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
forall a. FingerTree a
Empty

-- | /O(1)/. A singleton sequence.
singleton       :: a -> Seq a
singleton :: a -> Seq a
singleton a
x     =  FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq (Elem a -> FingerTree (Elem a)
forall a. a -> FingerTree a
Single (a -> Elem a
forall a. a -> Elem a
Elem a
x))

-- | /O(1)/. Add an element to the left end of a sequence.
-- Mnemonic: a triangle with the single element at the pointy end.
(<|)            :: a -> Seq a -> Seq a
a
x <| :: a -> Seq a -> Seq a
<| Seq FingerTree (Elem a)
xs     =  FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq (a -> Elem a
forall a. a -> Elem a
Elem a
x Elem a -> FingerTree (Elem a) -> FingerTree (Elem a)
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 :: a -> FingerTree a -> FingerTree a
consTree a
a FingerTree a
Empty        = a -> FingerTree a
forall a. a -> FingerTree a
Single a
a
consTree a
a (Single a
b)   = Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (a -> Digit a
forall a. a -> Digit a
One a
a) FingerTree (Node a)
forall a. FingerTree a
Empty (a -> Digit a
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 FingerTree (Node a) -> FingerTree a -> FingerTree a
`seq`
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (a -> Int
forall a. Sized a => a -> Int
size a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b) (a -> a -> a -> Node a
forall a. Sized a => a -> a -> a -> Node a
node3 a
c a
d a
e Node a -> FingerTree (Node a) -> FingerTree (Node a)
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) =
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (a -> Int
forall a. Sized a => a -> Int
size a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (a -> a -> a -> a -> Digit a
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) =
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (a -> Int
forall a. Sized a => a -> Int
size a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (a -> a -> a -> Digit a
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) =
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (a -> Int
forall a. Sized a => a -> Int
size a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b) FingerTree (Node a)
m Digit a
sf

-- | /O(1)/. Add an element to the right end of a sequence.
-- Mnemonic: a triangle with the single element at the pointy end.
(|>)            :: Seq a -> a -> Seq a
Seq FingerTree (Elem a)
xs |> :: Seq a -> a -> Seq a
|> a
x     =  FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq (FingerTree (Elem a)
xs FingerTree (Elem a) -> Elem a -> FingerTree (Elem a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` a -> Elem a
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 :: FingerTree a -> a -> FingerTree a
snocTree FingerTree a
Empty a
a        =  a -> FingerTree a
forall a. a -> FingerTree a
Single a
a
snocTree (Single a
a) a
b   =  Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (a -> Digit a
forall a. a -> Digit a
One a
a) FingerTree (Node a)
forall a. FingerTree a
Empty (a -> Digit a
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 FingerTree (Node a) -> FingerTree a -> FingerTree a
`seq`
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
e) Digit a
pr (FingerTree (Node a)
m FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` a -> a -> a -> Node a
forall a. Sized a => a -> a -> a -> Node a
node3 a
a a
b a
c) (a -> a -> Digit a
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 =
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
d) Digit a
pr FingerTree (Node a)
m (a -> a -> a -> a -> Digit a
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 =
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
c) Digit a
pr FingerTree (Node a)
m (a -> a -> a -> Digit a
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 =
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b) Digit a
pr FingerTree (Node a)
m (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b)

-- | /O(log(min(n1,n2)))/. Concatenate two sequences.
(><)            :: Seq a -> Seq a -> Seq a
Seq FingerTree (Elem a)
xs >< :: Seq a -> Seq a -> Seq a
>< Seq FingerTree (Elem a)
ys = FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq (FingerTree (Elem a) -> FingerTree (Elem a) -> FingerTree (Elem a)
forall a.
FingerTree (Elem a) -> FingerTree (Elem a) -> FingerTree (Elem a)
appendTree0 FingerTree (Elem a)
xs FingerTree (Elem a)
ys)

-- The appendTree/addDigits gunk below is machine generated

appendTree0 :: FingerTree (Elem a) -> FingerTree (Elem a) -> FingerTree (Elem a)
appendTree0 :: 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 Elem a -> FingerTree (Elem a) -> FingerTree (Elem a)
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 FingerTree (Elem a) -> Elem a -> FingerTree (Elem a)
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) =
        Int
-> Digit (Elem a)
-> FingerTree (Node (Elem a))
-> Digit (Elem a)
-> FingerTree (Elem a)
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s2) Digit (Elem a)
pr1 (FingerTree (Node (Elem a))
-> Digit (Elem a)
-> Digit (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
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 :: 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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> Node a
node2 Elem a
a Elem a
b) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> Node a
node2 Elem a
a Elem a
b) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> Node a
node2 Elem a
a Elem a
b) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> Node a
node2 Elem a
d Elem a
e) (Elem a -> Elem a -> Node (Elem a)
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 =
        FingerTree (Node (Elem a))
-> Node (Elem a)
-> Node (Elem a)
-> Node (Elem a)
-> FingerTree (Node (Elem a))
-> FingerTree (Node (Elem a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Elem a))
m1 (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
a Elem a
b Elem a
c) (Elem a -> Elem a -> Elem a -> Node (Elem a)
forall a. Sized a => a -> a -> a -> Node a
node3 Elem a
d Elem a
e Elem a
f) (Elem a -> Elem a -> Node (Elem a)
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 :: 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 Node a -> FingerTree (Node a) -> FingerTree (Node 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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
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 Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a Node a -> FingerTree (Node a) -> FingerTree (Node 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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a FingerTree (Node a) -> Node a -> FingerTree (Node 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) =
        Int
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> Digit (Node a)
-> FingerTree (Node a)
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 :: 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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree1 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
a Node a
b) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
a Node a
b) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 :: 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 Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b Node a -> FingerTree (Node a) -> FingerTree (Node a)
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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a FingerTree (Node a) -> Node a -> FingerTree (Node 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 Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b Node a -> FingerTree (Node a) -> FingerTree (Node a)
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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b FingerTree (Node a) -> Node a -> FingerTree (Node a)
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) =
        Int
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> Digit (Node a)
-> FingerTree (Node a)
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
b Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 :: 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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
a Node a
b) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (Node a -> Node a -> Node (Node a)
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 :: 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 Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c Node a -> FingerTree (Node a) -> FingerTree (Node a)
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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b FingerTree (Node a) -> Node a -> FingerTree (Node a)
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 Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c Node a -> FingerTree (Node a) -> FingerTree (Node a)
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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
c FingerTree (Node a) -> Node a -> FingerTree (Node a)
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) =
        Int
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> Digit (Node a)
-> FingerTree (Node a)
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
b Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
c Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (FingerTree (Node (Node a))
-> Digit (Node a)
-> Node a
-> Node a
-> Node a
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 :: 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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (Node a -> Node a -> Node (Node a)
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 :: 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 Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
d Node a -> FingerTree (Node a) -> FingerTree (Node a)
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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
c FingerTree (Node a) -> Node a -> FingerTree (Node a)
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 Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
a Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
b Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
c Node a -> FingerTree (Node a) -> FingerTree (Node a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
`consTree` Node a
d Node a -> FingerTree (Node a) -> FingerTree (Node a)
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 FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
a FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
b FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
c FingerTree (Node a) -> Node a -> FingerTree (Node a)
forall a. Sized a => FingerTree a -> a -> FingerTree a
`snocTree` Node a
d FingerTree (Node a) -> Node a -> FingerTree (Node a)
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) =
        Int
-> Digit (Node a)
-> FingerTree (Node (Node a))
-> Digit (Node a)
-> FingerTree (Node a)
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
b Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
c Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Node a -> Int
forall a. Sized a => a -> Int
size Node a
d Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s2) Digit (Node a)
pr1 (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))
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 :: 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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a -> Node a -> FingerTree (Node a) -> FingerTree (Node a)
appendTree2 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
d Node a
e) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
forall a.
FingerTree (Node a)
-> Node a
-> Node a
-> Node a
-> FingerTree (Node a)
-> FingerTree (Node a)
appendTree3 FingerTree (Node (Node a))
m1 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> Node a
node2 Node a
g Node a
h) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (Node a -> Node a -> Node (Node a)
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 =
        FingerTree (Node (Node a))
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> Node (Node a)
-> FingerTree (Node (Node a))
-> FingerTree (Node (Node a))
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 (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
a Node a
b Node a
c) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
d Node a
e Node a
f) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
g Node a
h Node a
i) (Node a -> Node a -> Node a -> Node (Node a)
forall a. Sized a => a -> a -> a -> Node a
node3 Node a
j Node a
k Node a
l) FingerTree (Node (Node a))
m2

------------------------------------------------------------------------
-- Deconstruction
------------------------------------------------------------------------

-- | /O(1)/. Is this the empty sequence?
null            :: Seq a -> Bool
null :: Seq a -> Bool
null (Seq FingerTree (Elem a)
Empty) = Bool
True
null Seq a
_          =  Bool
False

-- | /O(1)/. The number of elements in the sequence.
length          :: Seq a -> Int
length :: Seq a -> Int
length (Seq FingerTree (Elem a)
xs) =  FingerTree (Elem a) -> Int
forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs

-- Views

data Maybe2 a b = Nothing2 | Just2 a b

-- | View of the left end of a sequence.
data ViewL a
        = EmptyL        -- ^ empty sequence
        | a :< Seq a    -- ^ leftmost element and the rest of the sequence
#ifndef __HADDOCK__
        deriving (ViewL a -> ViewL a -> Bool
(ViewL a -> ViewL a -> Bool)
-> (ViewL a -> ViewL a -> Bool) -> Eq (ViewL a)
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
[ViewL a] -> ShowS
ViewL a -> String
(Int -> ViewL a -> ShowS)
-> (ViewL a -> String) -> ([ViewL a] -> ShowS) -> Show (ViewL a)
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 :: (a -> b) -> ViewL a -> ViewL b
fmap a -> b
_ ViewL a
EmptyL           = ViewL b
forall a. ViewL a
EmptyL
        fmap a -> b
f (a
x :< Seq a
xs)        = a -> b
f a
x b -> Seq b -> ViewL b
forall a. a -> Seq a -> ViewL a
:< (a -> b) -> Seq a -> Seq b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Seq a
xs

-- | /O(1)/. Analyse the left end of a sequence.
viewl           ::  Seq a -> ViewL a
viewl :: Seq a -> ViewL a
viewl (Seq FingerTree (Elem a)
xs)  =  case FingerTree (Elem a) -> Maybe2 (Elem a) (FingerTree (Elem a))
forall a. Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree (Elem a)
xs of
        Maybe2 (Elem a) (FingerTree (Elem a))
Nothing2 -> ViewL a
forall a. ViewL a
EmptyL
        Just2 (Elem a
x) FingerTree (Elem a)
xs' -> a
x a -> Seq a -> ViewL a
forall a. a -> Seq a -> ViewL a
:< FingerTree (Elem a) -> Seq 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 :: FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree a
Empty                 = Maybe2 a (FingerTree a)
forall a b. Maybe2 a b
Nothing2
viewLTree (Single a
a)            = a -> FingerTree a -> Maybe2 a (FingerTree a)
forall a b. a -> b -> Maybe2 a b
Just2 a
a FingerTree a
forall a. FingerTree a
Empty
viewLTree (Deep Int
s (One a
a) FingerTree (Node a)
m Digit a
sf) = a -> FingerTree a -> Maybe2 a (FingerTree a)
forall a b. a -> b -> Maybe2 a b
Just2 a
a (case FingerTree (Node a) -> Maybe2 (Node a) (FingerTree (Node a))
forall a. Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree (Node a)
m of
        Maybe2 (Node a) (FingerTree (Node a))
Nothing2        -> Digit a -> FingerTree a
forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
sf
        Just2 Node a
b FingerTree (Node a)
m'      -> Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
a) (Node a -> Digit 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) =
        a -> FingerTree a -> Maybe2 a (FingerTree a)
forall a b. a -> b -> Maybe2 a b
Just2 a
a (Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
a) (a -> Digit 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) =
        a -> FingerTree a -> Maybe2 a (FingerTree a)
forall a b. a -> b -> Maybe2 a b
Just2 a
a (Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
a) (a -> a -> Digit 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) =
        a -> FingerTree a -> Maybe2 a (FingerTree a)
forall a b. a -> b -> Maybe2 a b
Just2 a
a (Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
a) (a -> a -> a -> Digit a
forall a. a -> a -> a -> Digit a
Three a
b a
c a
d) FingerTree (Node a)
m Digit a
sf)

-- | View of the right end of a sequence.
data ViewR a
        = EmptyR        -- ^ empty sequence
        | Seq a :> a    -- ^ the sequence minus the rightmost element,
                        -- and the rightmost element
#ifndef __HADDOCK__
        deriving (ViewR a -> ViewR a -> Bool
(ViewR a -> ViewR a -> Bool)
-> (ViewR a -> ViewR a -> Bool) -> Eq (ViewR a)
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
[ViewR a] -> ShowS
ViewR a -> String
(Int -> ViewR a -> ShowS)
-> (ViewR a -> String) -> ([ViewR a] -> ShowS) -> Show (ViewR a)
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 :: (a -> b) -> ViewR a -> ViewR b
fmap a -> b
_ ViewR a
EmptyR           = ViewR b
forall a. ViewR a
EmptyR
        fmap a -> b
f (Seq a
xs :> a
x)        = (a -> b) -> Seq a -> Seq b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Seq a
xs Seq b -> b -> ViewR b
forall a. Seq a -> a -> ViewR a
:> a -> b
f a
x

-- | /O(1)/. Analyse the right end of a sequence.
viewr           ::  Seq a -> ViewR a
viewr :: Seq a -> ViewR a
viewr (Seq FingerTree (Elem a)
xs)  =  case FingerTree (Elem a) -> Maybe2 (FingerTree (Elem a)) (Elem a)
forall a. Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree (Elem a)
xs of
        Maybe2 (FingerTree (Elem a)) (Elem a)
Nothing2 -> ViewR a
forall a. ViewR a
EmptyR
        Just2 FingerTree (Elem a)
xs' (Elem a
x) -> FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
xs' Seq a -> a -> ViewR a
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 :: FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree a
Empty                 = Maybe2 (FingerTree a) a
forall a b. Maybe2 a b
Nothing2
viewRTree (Single a
z)            = FingerTree a -> a -> Maybe2 (FingerTree a) a
forall a b. a -> b -> Maybe2 a b
Just2 FingerTree a
forall a. FingerTree a
Empty a
z
viewRTree (Deep Int
s Digit a
pr FingerTree (Node a)
m (One a
z)) = FingerTree a -> a -> Maybe2 (FingerTree a) a
forall a b. a -> b -> Maybe2 a b
Just2 (case FingerTree (Node a) -> Maybe2 (FingerTree (Node a)) (Node a)
forall a. Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree (Node a)
m of
        Maybe2 (FingerTree (Node a)) (Node a)
Nothing2        ->  Digit a -> FingerTree a
forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
pr
        Just2 FingerTree (Node a)
m' Node a
y      ->  Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m' (Node a -> Digit a
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)) =
        FingerTree a -> a -> Maybe2 (FingerTree a) a
forall a b. a -> b -> Maybe2 a b
Just2 (Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m (a -> Digit a
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)) =
        FingerTree a -> a -> Maybe2 (FingerTree a) a
forall a b. a -> b -> Maybe2 a b
Just2 (Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m (a -> a -> Digit a
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)) =
        FingerTree a -> a -> Maybe2 (FingerTree a) a
forall a b. a -> b -> Maybe2 a b
Just2 (Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Sized a => a -> Int
size a
z) Digit a
pr FingerTree (Node a)
m (a -> a -> a -> Digit a
forall a. a -> a -> a -> Digit a
Three a
w a
x a
y)) a
z

-- Indexing

-- | /O(log(min(i,n-i)))/. The element at the specified position
index           :: Seq a -> Int -> a
index :: Seq a -> Int -> a
index (Seq FingerTree (Elem a)
xs) Int
i
  | Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< FingerTree (Elem a) -> Int
forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs = case Int -> FingerTree (Elem a) -> Place (Elem a)
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   = String -> a
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 :: Int -> FingerTree a -> Place a
lookupTree Int
i (Single a
x) = Int -> a -> Place a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     =  Int -> Digit a -> Place a
forall a. Sized a => Int -> Digit a -> Place a
lookupDigit Int
i Digit a
pr
  | Int
vm Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      =  case Int -> FingerTree (Node a) -> Place (Node a)
forall a. Sized a => Int -> FingerTree a -> Place a
lookupTree Int
vpr FingerTree (Node a)
m of
                        Place Int
i' Node a
xs -> Int -> Node a -> Place a
forall a. Sized a => Int -> Node a -> Place a
lookupNode Int
i' Node a
xs
  | Bool
otherwise   =  Int -> Digit a -> Place a
forall a. Sized a => Int -> Digit a -> Place a
lookupDigit Int
vm Digit a
sf
  where vpr :: Int
vpr     =  Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Digit a -> Int
forall a. Sized a => a -> Int
size Digit a
pr
        vm :: Int
vm      =  Int
vpr Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FingerTree (Node a) -> Int
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 :: Int -> Node a -> Place a
lookupNode Int
i (Node2 Int
_ a
a a
b)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
i a
a
  | Bool
otherwise   = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
va a
b
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
lookupNode Int
i (Node3 Int
_ a
a a
b a
c)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
i a
a
  | Int
vab Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
va a
b
  | Bool
otherwise   = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
vab a
c
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
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 :: Int -> Digit a -> Place a
lookupDigit Int
i (One a
a) = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
i a
a
lookupDigit Int
i (Two a
a a
b)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
i a
a
  | Bool
otherwise   = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
va a
b
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
lookupDigit Int
i (Three a
a a
b a
c)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
i a
a
  | Int
vab Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
va a
b
  | Bool
otherwise   = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
vab a
c
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b
lookupDigit Int
i (Four a
a a
b a
c a
d)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
i a
a
  | Int
vab Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
va a
b
  | Int
vabc Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0    = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
vab a
c
  | Bool
otherwise   = Int -> a -> Place a
forall a. Int -> a -> Place a
Place Int
vabc a
d
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b
        vabc :: Int
vabc    = Int
vab Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
c

-- | /O(log(min(i,n-i)))/. Replace the element at the specified position
update          :: Int -> a -> Seq a -> Seq a
update :: Int -> a -> Seq a -> Seq a
update Int
i a
x      = (a -> a) -> Int -> Seq a -> Seq a
forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust (a -> a -> a
forall a b. a -> b -> a
const a
x) Int
i

-- | /O(log(min(i,n-i)))/. Update the element at the specified position
adjust          :: (a -> a) -> Int -> Seq a -> Seq a
adjust :: (a -> a) -> Int -> Seq a -> Seq a
adjust a -> a
f Int
i (Seq FingerTree (Elem a)
xs)
  | Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< FingerTree (Elem a) -> Int
forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs = FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq ((Int -> Elem a -> Elem a)
-> Int -> FingerTree (Elem a) -> FingerTree (Elem a)
forall a.
Sized a =>
(Int -> a -> a) -> Int -> FingerTree a -> FingerTree a
adjustTree ((Elem a -> Elem a) -> Int -> Elem a -> Elem a
forall a b. a -> b -> a
const ((a -> a) -> Elem a -> Elem a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
f)) (-Int
i) FingerTree (Elem a)
xs)
  | Bool
otherwise   = FingerTree (Elem a) -> Seq a
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 :: (Int -> a -> a) -> Int -> FingerTree a -> FingerTree a
adjustTree Int -> a -> a
f Int
i (Single a
x) = a -> FingerTree a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s ((Int -> a -> a) -> Int -> Digit a -> Digit a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s Digit a
pr ((Int -> Node a -> Node a)
-> Int -> FingerTree (Node a) -> FingerTree (Node a)
forall a.
Sized a =>
(Int -> a -> a) -> Int -> FingerTree a -> FingerTree a
adjustTree ((Int -> a -> a) -> Int -> Node a -> Node a
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   = Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s Digit a
pr FingerTree (Node a)
m ((Int -> a -> a) -> Int -> Digit a -> Digit a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Digit a -> Int
forall a. Sized a => a -> Int
size Digit a
pr
        vm :: Int
vm      = Int
vpr Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FingerTree (Node a) -> Int
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 :: (Int -> a -> a) -> Int -> Node a -> Node a
adjustNode Int -> a -> a
f Int
i (Node2 Int
s a
a a
b)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> a -> a -> Node a
forall a. Int -> a -> a -> Node a
Node2 Int
s (Int -> a -> a
f Int
i a
a) a
b
  | Bool
otherwise   = Int -> a -> a -> Node a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Int -> a -> a -> a -> Node a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Int -> a -> a -> a -> Node a
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   = Int -> a -> a -> a -> Node a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
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 :: (Int -> a -> a) -> Int -> Digit a -> Digit a
adjustDigit Int -> a -> a
f Int
i (One a
a) = a -> Digit 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = a -> a -> Digit a
forall a. a -> a -> Digit a
Two (Int -> a -> a
f Int
i a
a) a
b
  | Bool
otherwise   = a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a (Int -> a -> a
f Int
va a
b)
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = a -> a -> a -> Digit a
forall a. a -> a -> a -> Digit a
Three (Int -> a -> a
f Int
i a
a) a
b a
c
  | Int
vab Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = a -> a -> a -> Digit a
forall a. a -> a -> a -> Digit a
Three a
a (Int -> a -> a
f Int
va a
b) a
c
  | Bool
otherwise   = a -> a -> a -> Digit a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = a -> a -> a -> a -> Digit a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = a -> a -> a -> a -> Digit a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0    = a -> a -> a -> a -> Digit a
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   = a -> a -> a -> a -> Digit a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b
        vabc :: Int
vabc    = Int
vab Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
c

-- Splitting

-- | /O(log(min(i,n-i)))/. The first @i@ elements of a sequence.
take            :: Int -> Seq a -> Seq a
take :: Int -> Seq a -> Seq a
take Int
i          =  (Seq a, Seq a) -> Seq a
forall a b. (a, b) -> a
fst ((Seq a, Seq a) -> Seq a)
-> (Seq a -> (Seq a, Seq a)) -> Seq a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Seq a -> (Seq a, Seq a)
forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt Int
i

-- | /O(log(min(i,n-i)))/. Elements of sequence after the first @i@.
drop            :: Int -> Seq a -> Seq a
drop :: Int -> Seq a -> Seq a
drop Int
i          =  (Seq a, Seq a) -> Seq a
forall a b. (a, b) -> b
snd ((Seq a, Seq a) -> Seq a)
-> (Seq a -> (Seq a, Seq a)) -> Seq a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Seq a -> (Seq a, Seq a)
forall a. Int -> Seq a -> (Seq a, Seq a)
splitAt Int
i

-- | /O(log(min(i,n-i)))/. Split a sequence at a given position.
splitAt                 :: Int -> Seq a -> (Seq a, Seq a)
splitAt :: Int -> Seq a -> (Seq a, Seq a)
splitAt Int
i (Seq FingerTree (Elem a)
xs)      =  (FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
l, FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq FingerTree (Elem a)
r)
  where (FingerTree (Elem a)
l, FingerTree (Elem a)
r)          =  Int
-> FingerTree (Elem a)
-> (FingerTree (Elem a), FingerTree (Elem a))
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 :: Int
-> FingerTree (Elem a)
-> (FingerTree (Elem a), FingerTree (Elem a))
split Int
i FingerTree (Elem a)
Empty   = Int
i Int
-> (FingerTree (Elem a), FingerTree (Elem a))
-> (FingerTree (Elem a), FingerTree (Elem a))
`seq` (FingerTree (Elem a)
forall a. FingerTree a
Empty, FingerTree (Elem a)
forall a. FingerTree a
Empty)
split Int
i FingerTree (Elem a)
xs
  | FingerTree (Elem a) -> Int
forall a. Sized a => a -> Int
size FingerTree (Elem a)
xs Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
i = (FingerTree (Elem a)
l, Elem a -> FingerTree (Elem a) -> FingerTree (Elem a)
forall a. Sized a => a -> FingerTree a -> FingerTree a
consTree Elem a
x FingerTree (Elem a)
r)
  | Bool
otherwise   = (FingerTree (Elem a)
xs, FingerTree (Elem a)
forall a. FingerTree a
Empty)
  where Split FingerTree (Elem a)
l Elem a
x FingerTree (Elem a)
r = Int -> FingerTree (Elem a) -> Split (FingerTree (Elem a)) (Elem a)
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 :: Int -> FingerTree a -> Split (FingerTree a) a
splitTree Int
i (Single a
x) = Int
i Int -> Split (FingerTree a) a -> Split (FingerTree a) a
`seq` FingerTree a -> a -> FingerTree a -> Split (FingerTree a) a
forall t a. t -> a -> t -> Split t a
Split FingerTree a
forall a. FingerTree a
Empty a
x FingerTree a
forall a. FingerTree a
Empty
splitTree Int
i (Deep Int
_ Digit a
pr FingerTree (Node a)
m Digit a
sf)
  | Int
vpr Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = case Int -> Digit a -> Split (Maybe (Digit a)) a
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 -> FingerTree a -> a -> FingerTree a -> Split (FingerTree a) a
forall t a. t -> a -> t -> Split t a
Split (FingerTree a
-> (Digit a -> FingerTree a) -> Maybe (Digit a) -> FingerTree a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe FingerTree a
forall a. FingerTree a
Empty Digit a -> FingerTree a
forall a. Sized a => Digit a -> FingerTree a
digitToTree Maybe (Digit a)
l) a
x (Maybe (Digit a) -> FingerTree (Node a) -> Digit a -> FingerTree a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = case Int -> FingerTree (Node a) -> Split (FingerTree (Node a)) (Node a)
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 Int -> Node a -> Split (Maybe (Digit a)) a
forall a. Sized a => Int -> Node a -> Split (Maybe (Digit a)) a
splitNode (Int
vpr Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FingerTree (Node a) -> Int
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 -> FingerTree a -> a -> FingerTree a -> Split (FingerTree a) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> FingerTree (Node a) -> Maybe (Digit a) -> FingerTree a
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 (Maybe (Digit a) -> FingerTree (Node a) -> Digit a -> FingerTree a
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 Int -> Digit a -> Split (Maybe (Digit a)) a
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 -> FingerTree a -> a -> FingerTree a -> Split (FingerTree a) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> FingerTree (Node a) -> Maybe (Digit a) -> FingerTree a
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 (FingerTree a
-> (Digit a -> FingerTree a) -> Maybe (Digit a) -> FingerTree a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe FingerTree a
forall a. FingerTree a
Empty Digit a -> FingerTree a
forall a. Sized a => Digit a -> FingerTree a
digitToTree Maybe (Digit a)
r)
  where vpr :: Int
vpr     = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Digit a -> Int
forall a. Sized a => a -> Int
size Digit a
pr
        vm :: Int
vm      = Int
vpr Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FingerTree (Node a) -> Int
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 :: Maybe (Digit a) -> FingerTree (Node a) -> Digit a -> FingerTree a
deepL Maybe (Digit a)
Nothing FingerTree (Node a)
m Digit a
sf      = case FingerTree (Node a) -> Maybe2 (Node a) (FingerTree (Node a))
forall a. Sized a => FingerTree a -> Maybe2 a (FingerTree a)
viewLTree FingerTree (Node a)
m of
        Maybe2 (Node a) (FingerTree (Node a))
Nothing2        -> Digit a -> FingerTree a
forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
sf
        Just2 Node a
a FingerTree (Node a)
m'      -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep (Node a -> Digit a
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    = Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
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 :: Digit a -> FingerTree (Node a) -> Maybe (Digit a) -> FingerTree a
deepR Digit a
pr FingerTree (Node a)
m Maybe (Digit a)
Nothing      = case FingerTree (Node a) -> Maybe2 (FingerTree (Node a)) (Node a)
forall a. Sized a => FingerTree a -> Maybe2 (FingerTree a) a
viewRTree FingerTree (Node a)
m of
        Maybe2 (FingerTree (Node a)) (Node a)
Nothing2        -> Digit a -> FingerTree a
forall a. Sized a => Digit a -> FingerTree a
digitToTree Digit a
pr
        Just2 FingerTree (Node a)
m' Node a
a      -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Sized a =>
Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
deep Digit a
pr FingerTree (Node a)
m' (Node a -> Digit a
forall a. Node a -> Digit a
nodeToDigit Node a
a)
deepR Digit a
pr FingerTree (Node a)
m (Just Digit a
sf)    = Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
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 :: Int -> Node a -> Split (Maybe (Digit a)) a
splitNode Int
i (Node2 Int
_ a
a a
b)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split Maybe (Digit a)
forall a. Maybe a
Nothing a
a (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
b))
  | Bool
otherwise   = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
a)) a
b Maybe (Digit a)
forall a. Maybe a
Nothing
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
splitNode Int
i (Node3 Int
_ a
a a
b a
c)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split Maybe (Digit a)
forall a. Maybe a
Nothing a
a (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
b a
c))
  | Int
vab Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
a)) a
b (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
c))
  | Bool
otherwise   = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b)) a
c Maybe (Digit a)
forall a. Maybe a
Nothing
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
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 :: Int -> Digit a -> Split (Maybe (Digit a)) a
splitDigit Int
i (One a
a) = Int
i Int -> Split (Maybe (Digit a)) a -> Split (Maybe (Digit a)) a
`seq` Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split Maybe (Digit a)
forall a. Maybe a
Nothing a
a Maybe (Digit a)
forall a. Maybe a
Nothing
splitDigit Int
i (Two a
a a
b)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split Maybe (Digit a)
forall a. Maybe a
Nothing a
a (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
b))
  | Bool
otherwise   = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
a)) a
b Maybe (Digit a)
forall a. Maybe a
Nothing
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
splitDigit Int
i (Three a
a a
b a
c)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split Maybe (Digit a)
forall a. Maybe a
Nothing a
a (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
b a
c))
  | Int
vab Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
a)) a
b (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
c))
  | Bool
otherwise   = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b)) a
c Maybe (Digit a)
forall a. Maybe a
Nothing
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b
splitDigit Int
i (Four a
a a
b a
c a
d)
  | Int
va Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0      = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split Maybe (Digit a)
forall a. Maybe a
Nothing a
a (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> a -> Digit a
forall a. a -> a -> a -> Digit a
Three a
b a
c a
d))
  | Int
vab Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
a)) a
b (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
c a
d))
  | Int
vabc Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0    = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> Digit a
forall a. a -> a -> Digit a
Two a
a a
b)) a
c (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> Digit a
forall a. a -> Digit a
One a
d))
  | Bool
otherwise   = Maybe (Digit a)
-> a -> Maybe (Digit a) -> Split (Maybe (Digit a)) a
forall t a. t -> a -> t -> Split t a
Split (Digit a -> Maybe (Digit a)
forall a. a -> Maybe a
Just (a -> a -> a -> Digit a
forall a. a -> a -> a -> Digit a
Three a
a a
b a
c)) a
d Maybe (Digit a)
forall a. Maybe a
Nothing
  where va :: Int
va      = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
a
        vab :: Int
vab     = Int
va Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
b
        vabc :: Int
vabc    = Int
vab Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall a. Sized a => a -> Int
size a
c

------------------------------------------------------------------------
-- Lists
------------------------------------------------------------------------

-- | /O(n)/. Create a sequence from a finite list of elements.
fromList        :: [a] -> Seq a
fromList :: [a] -> Seq a
fromList        =  (Seq a -> a -> Seq a) -> Seq a -> [a] -> Seq a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Data.List.foldl' Seq a -> a -> Seq a
forall a. Seq a -> a -> Seq a
(|>) Seq a
forall a. Seq a
empty

-- | /O(n)/. List of elements of the sequence.
toList          :: Seq a -> [a]
toList :: Seq a -> [a]
toList          =  (a -> [a] -> [a]) -> [a] -> Seq a -> [a]
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr (:) []

------------------------------------------------------------------------
-- Folds
------------------------------------------------------------------------

-- | /O(n*t)/. Fold over the elements of a sequence,
-- associating to the right.
foldr :: (a -> b -> b) -> b -> Seq a -> b
foldr :: (a -> b -> b) -> b -> Seq a -> b
foldr a -> b -> b
f b
z (Seq FingerTree (Elem a)
xs) = (Elem a -> b -> b) -> b -> FingerTree (Elem a) -> b
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 :: (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) =
        (a -> b -> b) -> b -> Digit a -> b
forall a b. (a -> b -> b) -> b -> Digit a -> b
foldrDigit a -> b -> b
f ((Node a -> b -> b) -> b -> FingerTree (Node a) -> b
forall a b. (a -> b -> b) -> b -> FingerTree a -> b
foldrTree ((b -> Node a -> b) -> Node a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> b) -> b -> Node a -> b
forall a b. (a -> b -> b) -> b -> Node a -> b
foldrNode a -> b -> b
f)) ((a -> b -> b) -> b -> Digit a -> b
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 :: (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 :: (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))

-- | /O(n*t)/. A variant of 'foldr' that has no base case,
-- and thus may only be applied to non-empty sequences.
foldr1 :: (a -> a -> a) -> Seq a -> a
foldr1 :: (a -> a -> a) -> Seq a -> a
foldr1 a -> a -> a
f (Seq FingerTree (Elem a)
xs) = Elem a -> a
forall a. Elem a -> a
getElem ((Elem a -> Elem a -> Elem a) -> FingerTree (Elem a) -> Elem a
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) = a -> Elem a
forall a. a -> Elem a
Elem (a -> a -> a
f a
x a
y)

foldr1Tree :: (a -> a -> a) -> FingerTree a -> a
foldr1Tree :: (a -> a -> a) -> FingerTree a -> a
foldr1Tree a -> a -> a
_ FingerTree a
Empty = String -> a
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) =
        (a -> a -> a) -> a -> Digit a -> a
forall a b. (a -> b -> b) -> b -> Digit a -> b
foldrDigit a -> a -> a
f ((Node a -> a -> a) -> a -> FingerTree (Node a) -> a
forall a b. (a -> b -> b) -> b -> FingerTree a -> b
foldrTree ((a -> Node a -> a) -> Node a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> a -> a) -> a -> Node a -> a
forall a b. (a -> b -> b) -> b -> Node a -> b
foldrNode a -> a -> a
f)) ((a -> a -> a) -> Digit a -> a
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 :: (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))

-- | /O(n*t)/. Fold over the elements of a sequence,
-- associating to the left.
foldl :: (a -> b -> a) -> a -> Seq b -> a
foldl :: (a -> b -> a) -> a -> Seq b -> a
foldl a -> b -> a
f a
z (Seq FingerTree (Elem b)
xs) = (a -> Elem b -> a) -> a -> FingerTree (Elem b) -> a
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 :: (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) =
        (a -> b -> a) -> a -> Digit b -> a
forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit a -> b -> a
f ((a -> Node b -> a) -> a -> FingerTree (Node b) -> a
forall a b. (a -> b -> a) -> a -> FingerTree b -> a
foldlTree ((a -> b -> a) -> a -> Node b -> a
forall a b. (a -> b -> a) -> a -> Node b -> a
foldlNode a -> b -> a
f) ((a -> b -> a) -> a -> Digit b -> a
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 :: (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 :: (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

-- | /O(n*t)/. A variant of 'foldl' that has no base case,
-- and thus may only be applied to non-empty sequences.
foldl1 :: (a -> a -> a) -> Seq a -> a
foldl1 :: (a -> a -> a) -> Seq a -> a
foldl1 a -> a -> a
f (Seq FingerTree (Elem a)
xs) = Elem a -> a
forall a. Elem a -> a
getElem ((Elem a -> Elem a -> Elem a) -> FingerTree (Elem a) -> Elem a
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) = a -> Elem a
forall a. a -> Elem a
Elem (a -> a -> a
f a
x a
y)

foldl1Tree :: (a -> a -> a) -> FingerTree a -> a
foldl1Tree :: (a -> a -> a) -> FingerTree a -> a
foldl1Tree a -> a -> a
_ FingerTree a
Empty = String -> a
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) =
        (a -> a -> a) -> a -> Digit a -> a
forall a b. (a -> b -> a) -> a -> Digit b -> a
foldlDigit a -> a -> a
f ((a -> Node a -> a) -> a -> FingerTree (Node a) -> a
forall a b. (a -> b -> a) -> a -> FingerTree b -> a
foldlTree ((a -> a -> a) -> a -> Node a -> a
forall a b. (a -> b -> a) -> a -> Node b -> a
foldlNode a -> a -> a
f) ((a -> a -> a) -> Digit a -> a
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 :: (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

------------------------------------------------------------------------
-- Derived folds
------------------------------------------------------------------------

-- | /O(n*t)/. Fold over the elements of a sequence,
-- associating to the right, but strictly.
foldr' :: (a -> b -> b) -> b -> Seq a -> b
foldr' :: (a -> b -> b) -> b -> Seq a -> b
foldr' a -> b -> b
f b
z Seq a
xs = ((b -> b) -> a -> b -> b) -> (b -> b) -> Seq a -> b -> b
forall a b. (a -> b -> a) -> a -> Seq b -> a
foldl (b -> b) -> a -> b -> b
forall b. (b -> b) -> a -> b -> b
f' b -> b
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 (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! a -> b -> b
f a
x b
z

-- | /O(n*t)/. Monadic fold over the elements of a sequence,
-- associating to the right, i.e. from right to left.
foldrM :: Monad m => (a -> b -> m b) -> b -> Seq a -> m b
foldrM :: (a -> b -> m b) -> b -> Seq a -> m b
foldrM a -> b -> m b
f b
z Seq a
xs = ((b -> m b) -> a -> b -> m b) -> (b -> m b) -> Seq a -> b -> m b
forall a b. (a -> b -> a) -> a -> Seq b -> a
foldl (b -> m b) -> a -> b -> m b
forall b. (b -> m b) -> a -> b -> m b
f' b -> m b
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 m b -> (b -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= b -> m b
k

-- | /O(n*t)/. Fold over the elements of a sequence,
-- associating to the right, but strictly.
foldl' :: (a -> b -> a) -> a -> Seq b -> a
foldl' :: (a -> b -> a) -> a -> Seq b -> a
foldl' a -> b -> a
f a
z Seq b
xs = (b -> (a -> a) -> a -> a) -> (a -> a) -> Seq b -> a -> a
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr b -> (a -> a) -> a -> a
forall b. b -> (a -> b) -> a -> b
f' a -> a
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 (a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
$! a -> b -> a
f a
z b
x

-- | /O(n*t)/. Monadic fold over the elements of a sequence,
-- associating to the left, i.e. from left to right.
foldlM :: Monad m => (a -> b -> m a) -> a -> Seq b -> m a
foldlM :: (a -> b -> m a) -> a -> Seq b -> m a
foldlM a -> b -> m a
f a
z Seq b
xs = (b -> (a -> m a) -> a -> m a) -> (a -> m a) -> Seq b -> a -> m a
forall a b. (a -> b -> b) -> b -> Seq a -> b
foldr b -> (a -> m a) -> a -> m a
forall b. b -> (a -> m b) -> a -> m b
f' a -> m a
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 m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> m b
k

------------------------------------------------------------------------
-- Reverse
------------------------------------------------------------------------

-- | /O(n)/. The reverse of a sequence.
reverse :: Seq a -> Seq a
reverse :: Seq a -> Seq a
reverse (Seq FingerTree (Elem a)
xs) = FingerTree (Elem a) -> Seq a
forall a. FingerTree (Elem a) -> Seq a
Seq ((Elem a -> Elem a) -> FingerTree (Elem a) -> FingerTree (Elem a)
forall a. (a -> a) -> FingerTree a -> FingerTree a
reverseTree Elem a -> Elem a
forall a. a -> a
id FingerTree (Elem a)
xs)

reverseTree :: (a -> a) -> FingerTree a -> FingerTree a
reverseTree :: (a -> a) -> FingerTree a -> FingerTree a
reverseTree a -> a
_ FingerTree a
Empty = FingerTree a
forall a. FingerTree a
Empty
reverseTree a -> a
f (Single a
x) = a -> FingerTree a
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) =
        Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
forall a.
Int -> Digit a -> FingerTree (Node a) -> Digit a -> FingerTree a
Deep Int
s ((a -> a) -> Digit a -> Digit a
forall a. (a -> a) -> Digit a -> Digit a
reverseDigit a -> a
f Digit a
sf)
                ((Node a -> Node a) -> FingerTree (Node a) -> FingerTree (Node a)
forall a. (a -> a) -> FingerTree a -> FingerTree a
reverseTree ((a -> a) -> Node a -> Node a
forall a. (a -> a) -> Node a -> Node a
reverseNode a -> a
f) FingerTree (Node a)
m)
                ((a -> a) -> Digit a -> Digit a
forall a. (a -> a) -> Digit a -> Digit a
reverseDigit a -> a
f Digit a
pr)

reverseDigit :: (a -> a) -> Digit a -> Digit a
reverseDigit :: (a -> a) -> Digit a -> Digit a
reverseDigit a -> a
f (One a
a) = a -> Digit a
forall a. a -> Digit a
One (a -> a
f a
a)
reverseDigit a -> a
f (Two a
a a
b) = a -> a -> Digit a
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) = a -> a -> a -> Digit a
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) = a -> a -> a -> a -> Digit a
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 :: (a -> a) -> Node a -> Node a
reverseNode a -> a
f (Node2 Int
s a
a a
b) = Int -> a -> a -> Node a
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) = Int -> a -> a -> a -> Node a
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

------------------------------------------------------------------------
-- QuickCheck
------------------------------------------------------------------------

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

------------------------------------------------------------------------
-- Valid trees
------------------------------------------------------------------------

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