{-# LANGUAGE PatternGuards, BangPatterns, TypeFamilies #-}
{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif
module Data.Stream.Future.Skew
( Future(..)
, (<|)
, length
, tail
, last
, uncons
, index
, drop
, dropWhile
, indexed
, from
, break
, span
, split
, splitW
, replicate
, insert
, insertBy
, update
, adjust
, toFuture
, singleton
) where
import Control.Applicative hiding (empty)
import Control.Comonad
import Data.Functor.Alt
import Data.Functor.Extend
#if MIN_VERSION_base(4,8,0)
import Prelude hiding (tail, drop, dropWhile, last, span, repeat, replicate, break)
import Data.Foldable (toList)
#else
import Data.Foldable
import Data.Traversable (Traversable, traverse)
import Prelude hiding (null, tail, drop, dropWhile, length, foldr, last, span, repeat, replicate, break)
#endif
#if !(MIN_VERSION_base(4,11,0))
import Data.Semigroup hiding (Last)
#endif
import Data.Semigroup.Foldable
import Data.Semigroup.Traversable
#if MIN_VERSION_base(4,7,0)
import qualified GHC.Exts as Exts
#endif
infixr 5 :<, <|
data Complete a
= Tip a
| Bin {-# UNPACK #-} !Int a !(Complete a) !(Complete a)
deriving Int -> Complete a -> ShowS
forall a. Show a => Int -> Complete a -> ShowS
forall a. Show a => [Complete a] -> ShowS
forall a. Show a => Complete a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Complete a] -> ShowS
$cshowList :: forall a. Show a => [Complete a] -> ShowS
show :: Complete a -> String
$cshow :: forall a. Show a => Complete a -> String
showsPrec :: Int -> Complete a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Complete a -> ShowS
Show
instance Functor Complete where
fmap :: forall a b. (a -> b) -> Complete a -> Complete b
fmap a -> b
f (Tip a
a) = forall a. a -> Complete a
Tip (a -> b
f a
a)
fmap a -> b
f (Bin Int
w a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
w (a -> b
f a
a) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
l) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
r)
instance Extend Complete where
extended :: forall a b. (Complete a -> b) -> Complete a -> Complete b
extended = forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend
instance Comonad Complete where
extend :: forall a b. (Complete a -> b) -> Complete a -> Complete b
extend Complete a -> b
f w :: Complete a
w@Tip {} = forall a. a -> Complete a
Tip (Complete a -> b
f Complete a
w)
extend Complete a -> b
f w :: Complete a
w@(Bin Int
n a
_ Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (Complete a -> b
f Complete a
w) (forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Complete a -> b
f Complete a
l) (forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Complete a -> b
f Complete a
r)
extract :: forall a. Complete a -> a
extract (Tip a
a) = a
a
extract (Bin Int
_ a
a Complete a
_ Complete a
_) = a
a
instance Foldable Complete where
foldMap :: forall m a. Monoid m => (a -> m) -> Complete a -> m
foldMap a -> m
f (Tip a
a) = a -> m
f a
a
foldMap a -> m
f (Bin Int
_ a
a Complete a
l Complete a
r) = a -> m
f a
a forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
l forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
r
foldr :: forall a b. (a -> b -> b) -> b -> Complete a -> b
foldr a -> b -> b
f b
z (Tip a
a) = a -> b -> b
f a
a b
z
foldr a -> b -> b
f b
z (Bin Int
_ a
a Complete a
l Complete a
r) = a -> b -> b
f a
a (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z Complete a
r) Complete a
l)
#if MIN_VERSION_base(4,8,0)
length :: forall a. Complete a -> Int
length Tip{} = Int
1
length (Bin Int
n a
_ Complete a
_ Complete a
_) = Int
n
null :: forall a. Complete a -> Bool
null Complete a
_ = Bool
False
#endif
instance Foldable1 Complete where
foldMap1 :: forall m a. Semigroup m => (a -> m) -> Complete a -> m
foldMap1 a -> m
f (Tip a
a) = a -> m
f a
a
foldMap1 a -> m
f (Bin Int
_ a
a Complete a
l Complete a
r) = a -> m
f a
a forall a. Semigroup a => a -> a -> a
<> forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
l forall a. Semigroup a => a -> a -> a
<> forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
r
instance Traversable Complete where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse a -> f b
f (Tip a
a) = forall a. a -> Complete a
Tip forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a
traverse a -> f b
f (Bin Int
n a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
l forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
r
instance Traversable1 Complete where
traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse1 a -> f b
f (Tip a
a) = forall a. a -> Complete a
Tip forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a
traverse1 a -> f b
f (Bin Int
n a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
l forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
r
bin :: a -> Complete a -> Complete a -> Complete a
bin :: forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
l Complete a
r = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin (Int
1 forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
l forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
r) a
a Complete a
l Complete a
r
{-# INLINE bin #-}
weight :: Complete a -> Int
weight :: forall a. Complete a -> Int
weight Tip{} = Int
1
weight (Bin Int
w a
_ Complete a
_ Complete a
_) = Int
w
{-# INLINE weight #-}
data Future a
= Last !(Complete a)
| !(Complete a) :< Future a
instance Show a => Show (Future a) where
showsPrec :: Int -> Future a -> ShowS
showsPrec Int
d Future a
as = Bool -> ShowS -> ShowS
showParen (Int
d forall a. Ord a => a -> a -> Bool
>= Int
10) forall a b. (a -> b) -> a -> b
$
String -> ShowS
showString String
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (forall (t :: * -> *) a. Foldable t => t a -> [a]
toList Future a
as)
instance Functor Future where
fmap :: forall a b. (a -> b) -> Future a -> Future b
fmap a -> b
f (Complete a
t :< Future a
ts) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
t forall a. Complete a -> Future a -> Future a
:< forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Future a
ts
fmap a -> b
f (Last Complete a
t) = forall a. Complete a -> Future a
Last (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
t)
instance Extend Future where
extended :: forall a b. (Future a -> b) -> Future a -> Future b
extended = forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend
instance Comonad Future where
extend :: forall a b. (Future a -> b) -> Future a -> Future b
extend Future a -> b
g (Last Complete a
t) = forall a. Complete a -> Future a
Last (forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
t forall a. Complete a -> Future a
Last)
extend Future a -> b
g (Complete a
t :< Future a
ts) = forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
t (forall a. Complete a -> Future a -> Future a
:< Future a
ts) forall a. Complete a -> Future a -> Future a
:< forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Future a -> b
g Future a
ts
extract :: forall a. Future a -> a
extract (Complete a
a :< Future a
_) = forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a
extract (Last Complete a
a) = forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a
extendTree :: (Future a -> b) -> Complete a -> (Complete a -> Future a) -> Complete b
extendTree :: forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g w :: Complete a
w@Tip{} Complete a -> Future a
f = forall a. a -> Complete a
Tip (Future a -> b
g (Complete a -> Future a
f Complete a
w))
extendTree Future a -> b
g w :: Complete a
w@(Bin Int
n a
_ Complete a
l Complete a
r) Complete a -> Future a
f = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (Future a -> b
g (Complete a -> Future a
f Complete a
w)) (forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
l (forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r)) (forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
r Complete a -> Future a
f)
instance Apply Future where
Last (Tip a -> b
f) <.> :: forall a b. Future (a -> b) -> Future a -> Future b
<.> Future a
as = forall a. a -> Future a
singleton (a -> b
f (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as))
Future (a -> b)
fs <.> Last (Tip a
a) = forall a. a -> Future a
singleton (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future (a -> b)
fs a
a)
Last (Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf) <.> Last (Bin Int
_ a
a Complete a
la Complete a
ra) = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete (a -> b)
rf forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
ra )
Last (Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf) <.> Bin Int
_ a
a Complete a
la Complete a
ra :< Future a
as = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete (a -> b)
rf forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< Complete a
ra forall a. Complete a -> Future a -> Future a
:< Future a
as)
Last (Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf) <.> Tip a
a :< Future a
as = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete (a -> b)
rf forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Future a
as )
Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf :< Future (a -> b)
fs <.> Last (Bin Int
_ a
a Complete a
la Complete a
ra) = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
ra )
Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf :< Future (a -> b)
fs <.> Tip a
a :< Future a
as = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Future a
as )
Bin Int
_ a -> b
f Complete (a -> b)
lf Complete (a -> b)
rf :< Future (a -> b)
fs <.> Bin Int
_ a
a Complete a
la Complete a
ra :< Future a
as = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< Complete a
ra forall a. Complete a -> Future a -> Future a
:< Future a
as)
Tip a -> b
f :< Future (a -> b)
fs <.> Tip a
a :< Future a
as = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Future a
as )
Tip a -> b
f :< Future (a -> b)
fs <.> Bin Int
_ a
a Complete a
la Complete a
ra :< Future a
as = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< Complete a
ra forall a. Complete a -> Future a -> Future a
:< Future a
as)
Tip a -> b
f :< Future (a -> b)
fs <.> Last (Bin Int
_ a
a Complete a
la Complete a
ra) = a -> b
f a
a forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
ra )
instance ComonadApply Future where
<@> :: forall a b. Future (a -> b) -> Future a -> Future b
(<@>) = forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
(<.>)
instance Applicative Future where
pure :: forall a. a -> Future a
pure a
a0 = forall a. a -> Complete a -> Future a
go a
a0 (forall a. a -> Complete a
Tip a
a0) where
go :: a -> Complete a -> Future a
go :: forall a. a -> Complete a -> Future a
go a
a Complete a
as | Complete a
ass <- forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
as Complete a
as = Complete a
as forall a. Complete a -> Future a -> Future a
:< forall a. a -> Complete a -> Future a
go a
a Complete a
ass
<*> :: forall a b. Future (a -> b) -> Future a -> Future b
(<*>) = forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
(<.>)
instance Alt Future where
Future a
as <!> :: forall a. Future a -> Future a -> Future a
<!> Future a
bs = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) Future a
bs Future a
as
instance Foldable Future where
foldMap :: forall m a. Monoid m => (a -> m) -> Future a -> m
foldMap a -> m
f (Complete a
t :< Future a
ts) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
t forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Future a
ts
foldMap a -> m
f (Last Complete a
t) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
t
foldr :: forall a b. (a -> b -> b) -> b -> Future a -> b
foldr a -> b -> b
f b
z (Complete a
t :< Future a
ts) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z Future a
ts) Complete a
t
foldr a -> b -> b
f b
z (Last Complete a
t) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z Complete a
t
#if MIN_VERSION_base(4,8,0)
length :: forall a. Future a -> Int
length (Last Complete a
t) = forall a. Complete a -> Int
weight Complete a
t
length (Complete a
t :< Future a
ts) = forall a. Complete a -> Int
weight Complete a
t forall a. Num a => a -> a -> a
+ forall (t :: * -> *) a. Foldable t => t a -> Int
length Future a
ts
null :: forall a. Future a -> Bool
null Future a
_ = Bool
False
#endif
instance Foldable1 Future where
foldMap1 :: forall m a. Semigroup m => (a -> m) -> Future a -> m
foldMap1 a -> m
f (Complete a
t :< Future a
ts) = forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
t forall a. Semigroup a => a -> a -> a
<> forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Future a
ts
foldMap1 a -> m
f (Last Complete a
t) = forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
t
instance Traversable Future where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Future a -> f (Future b)
traverse a -> f b
f (Complete a
t :< Future a
ts) = forall a. Complete a -> Future a -> Future a
(:<) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
t forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Future a
ts
traverse a -> f b
f (Last Complete a
t) = forall a. Complete a -> Future a
Last forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Complete a
t
instance Traversable1 Future where
traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Future a -> f (Future b)
traverse1 a -> f b
f (Complete a
t :< Future a
ts) = forall a. Complete a -> Future a -> Future a
(:<) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
t forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Future a
ts
traverse1 a -> f b
f (Last Complete a
t) = forall a. Complete a -> Future a
Last forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Complete a
t
replicate :: Int -> a -> Future a
replicate :: forall a. Int -> a -> Future a
replicate Int
n a
a
| Int
n forall a. Ord a => a -> a -> Bool
<= Int
0 = forall a. HasCallStack => String -> a
error String
"replicate: non-positive argument"
| Bool
otherwise = forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go Int
1 Int
n a
a (forall a. a -> Complete a
Tip a
a) (\ Int
_ Future a
r -> Future a
r)
where
go :: Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go :: forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go !Int
i !Int
j b
b Complete b
tb Int -> Future b -> r
k
| Int
j forall a. Ord a => a -> a -> Bool
>= Int
i2p1 = forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go Int
i2p1 Int
j b
b (forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
i2p1 b
b Complete b
tb Complete b
tb) Int -> Future b -> r
k'
| Int
j forall a. Ord a => a -> a -> Bool
>= Int
i2 = Int -> Future b -> r
k (Int
j forall a. Num a => a -> a -> a
- Int
i2) (Complete b
tb forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete b
tb)
| Bool
otherwise = Int -> Future b -> r
k (Int
j forall a. Num a => a -> a -> a
- Int
i) (forall a. Complete a -> Future a
Last Complete b
tb)
where
i2 :: Int
i2 = Int
i forall a. Num a => a -> a -> a
* Int
2
i2p1 :: Int
i2p1 = Int
i2 forall a. Num a => a -> a -> a
+ Int
1
k' :: Int -> Future b -> r
k' Int
r Future b
xs
| Int
r forall a. Ord a => a -> a -> Bool
>= Int
i2 = Int -> Future b -> r
k (Int
r forall a. Num a => a -> a -> a
- Int
i2) (Complete b
tb forall a. Complete a -> Future a -> Future a
:< Complete b
tb forall a. Complete a -> Future a -> Future a
:< Future b
xs)
| Int
r forall a. Ord a => a -> a -> Bool
>= Int
i = Int -> Future b -> r
k (Int
r forall a. Num a => a -> a -> a
- Int
i) (Complete b
tb forall a. Complete a -> Future a -> Future a
:< Future b
xs)
| Bool
otherwise = Int -> Future b -> r
k Int
r Future b
xs
{-# INLINE replicate #-}
mapWithIndex :: (Int -> a -> b) -> Future a -> Future b
mapWithIndex :: forall a b. (Int -> a -> b) -> Future a -> Future b
mapWithIndex Int -> a -> b
f0 Future a
as0 = forall {a} {a}. (Int -> a -> a) -> Int -> Future a -> Future a
spine Int -> a -> b
f0 Int
0 Future a
as0
where
spine :: (Int -> a -> a) -> Int -> Future a -> Future a
spine Int -> a -> a
f Int
m (Last Complete a
as) = forall a. Complete a -> Future a
Last (forall {a} {a}. (Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f Int
m Complete a
as)
spine Int -> a -> a
f Int
m (Complete a
a :< Future a
as) = forall {a} {a}. (Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f Int
m Complete a
a forall a. Complete a -> Future a -> Future a
:< (Int -> a -> a) -> Int -> Future a -> Future a
spine Int -> a -> a
f (Int
m forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
a) Future a
as
tree :: (Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f Int
m (Tip a
a) = forall a. a -> Complete a
Tip (Int -> a -> a
f Int
m a
a)
tree Int -> a -> a
f Int
m (Bin Int
n a
a Complete a
l Complete a
r) = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (Int -> a -> a
f Int
m a
a) ((Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f (Int
m forall a. Num a => a -> a -> a
+ Int
1) Complete a
l) ((Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f (Int
m forall a. Num a => a -> a -> a
+ Int
1 forall a. Num a => a -> a -> a
+ forall a. Complete a -> Int
weight Complete a
l) Complete a
r)
indexed :: Future a -> Future (Int, a)
indexed :: forall a. Future a -> Future (Int, a)
indexed = forall a b. (Int -> a -> b) -> Future a -> Future b
mapWithIndex (,)
{-# INLINE indexed #-}
from :: Num a => a -> Future a
from :: forall a. Num a => a -> Future a
from a
a = forall a b. (Int -> a -> b) -> Future a -> Future b
mapWithIndex (forall a. Num a => a -> a -> a
(+) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) (forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a)
{-# INLINE from #-}
singleton :: a -> Future a
singleton :: forall a. a -> Future a
singleton a
a = forall a. Complete a -> Future a
Last (forall a. a -> Complete a
Tip a
a)
{-# INLINE singleton #-}
#if !(MIN_VERSION_base(4,8,0))
length :: Future a -> Int
length (Last t) = weight t
length (t :< ts) = weight t + length ts
#endif
(<|) :: a -> Future a -> Future a
a
a <| :: forall a. a -> Future a -> Future a
<| (Complete a
l :< Last Complete a
r)
| forall a. Complete a -> Int
weight Complete a
l forall a. Eq a => a -> a -> Bool
== forall a. Complete a -> Int
weight Complete a
r = forall a. Complete a -> Future a
Last (forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
l Complete a
r)
a
a <| (Complete a
l :< Complete a
r :< Future a
as)
| forall a. Complete a -> Int
weight Complete a
l forall a. Eq a => a -> a -> Bool
== forall a. Complete a -> Int
weight Complete a
r = forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
l Complete a
r forall a. Complete a -> Future a -> Future a
:< Future a
as
a
a <| Future a
as = forall a. a -> Complete a
Tip a
a forall a. Complete a -> Future a -> Future a
:< Future a
as
{-# INLINE (<|) #-}
tail :: Future a -> Maybe (Future a)
tail :: forall a. Future a -> Maybe (Future a)
tail (Tip{} :< Future a
ts) = forall a. a -> Maybe a
Just Future a
ts
tail (Bin Int
_ a
_ Complete a
l Complete a
r :< Future a
ts) = forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< Complete a
r forall a. Complete a -> Future a -> Future a
:< Future a
ts)
tail (Last Tip{}) = forall a. Maybe a
Nothing
tail (Last (Bin Int
_ a
_ Complete a
l Complete a
r)) = forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
r)
{-# INLINE tail #-}
last :: Future a -> a
last :: forall a. Future a -> a
last (Complete a
_ :< Future a
as) = forall a. Future a -> a
last Future a
as
last (Last Complete a
as) = forall a. Complete a -> a
go Complete a
as
where go :: Complete a -> a
go (Tip a
a) = a
a
go (Bin Int
_ a
_ Complete a
_ Complete a
r) = Complete a -> a
go Complete a
r
uncons :: Future a -> (a, Maybe (Future a))
uncons :: forall a. Future a -> (a, Maybe (Future a))
uncons (Last (Tip a
a)) = (a
a, forall a. Maybe a
Nothing)
uncons (Last (Bin Int
_ a
a Complete a
l Complete a
r)) = (a
a, forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< forall a. Complete a -> Future a
Last Complete a
r))
uncons (Tip a
a :< Future a
as) = (a
a, forall a. a -> Maybe a
Just Future a
as)
uncons (Bin Int
_ a
a Complete a
l Complete a
r :< Future a
as) = (a
a, forall a. a -> Maybe a
Just (Complete a
l forall a. Complete a -> Future a -> Future a
:< Complete a
r forall a. Complete a -> Future a -> Future a
:< Future a
as))
{-# INLINE uncons #-}
index :: Int -> Future a -> a
index :: forall a. Int -> Future a -> a
index Int
i (Last Complete a
t)
| Int
i forall a. Ord a => a -> a -> Bool
< forall a. Complete a -> Int
weight Complete a
t = forall a. Int -> Complete a -> a
indexComplete Int
i Complete a
t
| Bool
otherwise = forall a. HasCallStack => String -> a
error String
"index: out of range"
index Int
i (Complete a
t :< Future a
ts)
| Int
i forall a. Ord a => a -> a -> Bool
< Int
w = forall a. Int -> Complete a -> a
indexComplete Int
i Complete a
t
| Bool
otherwise = forall a. Int -> Future a -> a
index (Int
i forall a. Num a => a -> a -> a
- Int
w) Future a
ts
where w :: Int
w = forall a. Complete a -> Int
weight Complete a
t
indexComplete :: Int -> Complete a -> a
indexComplete :: forall a. Int -> Complete a -> a
indexComplete Int
0 (Tip a
a) = a
a
indexComplete Int
i (Bin Int
w a
a Complete a
l Complete a
r)
| Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = a
a
| Int
i forall a. Ord a => a -> a -> Bool
<= Int
w' = forall a. Int -> Complete a -> a
indexComplete (Int
iforall a. Num a => a -> a -> a
-Int
1) Complete a
l
| Bool
otherwise = forall a. Int -> Complete a -> a
indexComplete (Int
iforall a. Num a => a -> a -> a
-Int
1forall a. Num a => a -> a -> a
-Int
w') Complete a
r
where w' :: Int
w' = forall a. Integral a => a -> a -> a
div Int
w Int
2
indexComplete Int
_ Complete a
_ = forall a. HasCallStack => String -> a
error String
"index: index out of range"
drop :: Int -> Future a -> Maybe (Future a)
drop :: forall a. Int -> Future a -> Maybe (Future a)
drop Int
0 Future a
ts = forall a. a -> Maybe a
Just Future a
ts
drop Int
i (Complete a
t :< Future a
ts) = case forall a. Ord a => a -> a -> Ordering
compare Int
i Int
w of
Ordering
LT -> forall a. a -> Maybe a
Just (forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
i Complete a
t (forall a. Complete a -> Future a -> Future a
:< Future a
ts))
Ordering
EQ -> forall a. a -> Maybe a
Just Future a
ts
Ordering
GT -> forall a. Int -> Future a -> Maybe (Future a)
drop (Int
i forall a. Num a => a -> a -> a
- Int
w) Future a
ts
where w :: Int
w = forall a. Complete a -> Int
weight Complete a
t
drop Int
i (Last Complete a
t)
| Int
i forall a. Ord a => a -> a -> Bool
< Int
w = forall a. a -> Maybe a
Just (forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
i Complete a
t forall a. Complete a -> Future a
Last)
| Bool
otherwise = forall a. Maybe a
Nothing
where w :: Int
w = forall a. Complete a -> Int
weight Complete a
t
dropComplete :: Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete :: forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
0 Complete a
t Complete a -> Future a
f = Complete a -> Future a
f Complete a
t
dropComplete Int
1 (Bin Int
_ a
_ Complete a
l Complete a
r) Complete a -> Future a
f = Complete a
l forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r
dropComplete Int
i (Bin Int
w a
_ Complete a
l Complete a
r) Complete a -> Future a
f = case forall a. Ord a => a -> a -> Ordering
compare (Int
i forall a. Num a => a -> a -> a
- Int
1) Int
w' of
Ordering
LT -> forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete (Int
iforall a. Num a => a -> a -> a
-Int
1) Complete a
l (forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r)
Ordering
EQ -> Complete a -> Future a
f Complete a
r
Ordering
GT -> forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete (Int
iforall a. Num a => a -> a -> a
-Int
1forall a. Num a => a -> a -> a
-Int
w') Complete a
r Complete a -> Future a
f
where w' :: Int
w' = forall a. Integral a => a -> a -> a
div Int
w Int
2
dropComplete Int
_ Complete a
_ Complete a -> Future a
_ = forall a. HasCallStack => String -> a
error String
"drop: index out of range"
dropWhile :: (a -> Bool) -> Future a -> Maybe (Future a)
dropWhile :: forall a. (a -> Bool) -> Future a -> Maybe (Future a)
dropWhile a -> Bool
p Future a
as
| a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as) = forall a. Future a -> Maybe (Future a)
tail Future a
as forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. (a -> Bool) -> Future a -> Maybe (Future a)
dropWhile a -> Bool
p
| Bool
otherwise = forall a. a -> Maybe a
Just Future a
as
span :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span :: forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span a -> Bool
p Future a
aas = case forall a. Future a -> (a, Maybe (Future a))
uncons Future a
aas of
(a
a, Just Future a
as) | a -> Bool
p a
a, ([a]
ts, Maybe (Future a)
fs) <- forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span a -> Bool
p Future a
as -> (a
aforall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
(a
a, Maybe (Future a)
Nothing) | a -> Bool
p a
a -> ([a
a], forall a. Maybe a
Nothing)
(a
_, Maybe (Future a)
_) -> ([], forall a. a -> Maybe a
Just Future a
aas)
break :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))
break :: forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
break a -> Bool
p = forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)
split :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split :: forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split a -> Bool
p l :: Future a
l@(Last Complete a
a)
| a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a) = ([], forall a. a -> Maybe a
Just Future a
l)
| Bool
otherwise = forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
a forall a. Complete a -> Future a
Last
split a -> Bool
p (Complete a
a :< Future a
as)
| a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as) = forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
a (forall a. Complete a -> Future a -> Future a
:< Future a
as)
| ([a]
ts, Maybe (Future a)
fs) <- forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split a -> Bool
p Future a
as = (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
a, Maybe (Future a)
fs)
splitComplete :: (a -> Bool) -> Complete a -> (Complete a -> Future a) -> ([a], Maybe (Future a))
splitComplete :: forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p t :: Complete a
t@(Tip a
a) Complete a -> Future a
f
| a -> Bool
p a
a = ([], forall a. a -> Maybe a
Just (Complete a -> Future a
f Complete a
t))
| Bool
otherwise = ([a
a], forall a. Maybe a
Nothing)
splitComplete a -> Bool
p t :: Complete a
t@(Bin Int
_ a
a Complete a
l Complete a
r) Complete a -> Future a
f
| a -> Bool
p a
a = ([], forall a. a -> Maybe a
Just (Complete a -> Future a
f Complete a
t))
| a -> Bool
p (forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
r), ([a]
ts, Maybe (Future a)
fs) <- forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
l (forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r) = (a
aforall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
| ([a]
ts, Maybe (Future a)
fs) <- forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
r Complete a -> Future a
f = (a
aforall a. a -> [a] -> [a]
:forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
l, Maybe (Future a)
fs)
splitW :: (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
splitW :: forall a. (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
splitW Future a -> Bool
p l :: Future a
l@(Last Complete a
a)
| Future a -> Bool
p Future a
l = ([], forall a. a -> Maybe a
Just Future a
l)
| Bool
otherwise = forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
a forall a. Complete a -> Future a
Last
splitW Future a -> Bool
p (Complete a
a :< Future a
as)
| Future a -> Bool
p Future a
as = forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
a (forall a. Complete a -> Future a -> Future a
:< Future a
as)
| ([a]
ts, Maybe (Future a)
fs) <- forall a. (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
splitW Future a -> Bool
p Future a
as = (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
a, Maybe (Future a)
fs)
splitCompleteW :: (Future a -> Bool) -> Complete a -> (Complete a -> Future a) -> ([a], Maybe (Future a))
splitCompleteW :: forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p t :: Complete a
t@(Tip a
a) Complete a -> Future a
f
| Future a
w <- Complete a -> Future a
f Complete a
t, Future a -> Bool
p Future a
w = ([], forall a. a -> Maybe a
Just Future a
w)
| Bool
otherwise = ([a
a], forall a. Maybe a
Nothing)
splitCompleteW Future a -> Bool
p t :: Complete a
t@(Bin Int
_ a
a Complete a
l Complete a
r) Complete a -> Future a
f
| Future a
w <- Complete a -> Future a
f Complete a
t, Future a -> Bool
p Future a
w = ([], forall a. a -> Maybe a
Just Future a
w)
| Future a
w <- Complete a -> Future a
f Complete a
r, Future a -> Bool
p Future a
w, ([a]
ts, Maybe (Future a)
fs) <- forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
l (forall a. Complete a -> Future a -> Future a
:< Future a
w) = (a
aforall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
| ([a]
ts, Maybe (Future a)
fs) <- forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
r Complete a -> Future a
f = (a
aforall a. a -> [a] -> [a]
:forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
l, Maybe (Future a)
fs)
#if MIN_VERSION_base(4,7,0)
instance Exts.IsList (Future a) where
type Item (Future a) = a
toList :: Future a -> [Item (Future a)]
toList = forall (t :: * -> *) a. Foldable t => t a -> [a]
Data.Foldable.toList
fromList :: [Item (Future a)] -> Future a
fromList [] = forall a. HasCallStack => String -> a
error String
"fromList: empty list"
fromList (Item (Future a)
x:[Item (Future a)]
xs) = forall {t}. t -> [t] -> Future t
go Item (Future a)
x [Item (Future a)]
xs
where go :: t -> [t] -> Future t
go t
a [] = forall a. a -> Future a
singleton t
a
go t
a (t
b:[t]
bs) = t
a forall a. a -> Future a -> Future a
<| t -> [t] -> Future t
go t
b [t]
bs
#else
fromList :: [a] -> Future a
fromList [] = error "fromList: empty list"
fromList (x:xs) = go x xs
where go a [] = singleton a
go a (b:bs) = a <| go b bs
#endif
toFuture :: [a] -> Maybe (Future a)
toFuture :: forall a. [a] -> Maybe (Future a)
toFuture [] = forall a. Maybe a
Nothing
#if MIN_VERSION_base(4,7,0)
toFuture [a]
xs = forall a. a -> Maybe a
Just (forall l. IsList l => [Item l] -> l
Exts.fromList [a]
xs)
#else
toFuture xs = Just (fromList xs)
#endif
insert :: Ord a => a -> Future a -> Future a
insert :: forall a. Ord a => a -> Future a -> Future a
insert a
a Future a
as = case forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split (a
aforall a. Ord a => a -> a -> Bool
<=) Future a
as of
([a]
_, Maybe (Future a)
Nothing) -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (forall a. a -> Future a
singleton a
a) Future a
as
([a]
ts, Just Future a
as') -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (a
a forall a. a -> Future a -> Future a
<| Future a
as') [a]
ts
insertBy :: (a -> a -> Ordering) -> a -> Future a -> Future a
insertBy :: forall a. (a -> a -> Ordering) -> a -> Future a -> Future a
insertBy a -> a -> Ordering
cmp a
a Future a
as = case forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split (\a
b -> a -> a -> Ordering
cmp a
a a
b forall a. Ord a => a -> a -> Bool
<= Ordering
EQ) Future a
as of
([a]
_, Maybe (Future a)
Nothing) -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (forall a. a -> Future a
singleton a
a) Future a
as
([a]
ts, Just Future a
as') -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Future a -> Future a
(<|) (a
a forall a. a -> Future a -> Future a
<| Future a
as') [a]
ts
adjust :: Int -> (a -> a) -> Future a -> Future a
adjust :: forall a. Int -> (a -> a) -> Future a -> Future a
adjust !Int
n a -> a
f d :: Future a
d@(Last Complete a
a)
| Int
n forall a. Ord a => a -> a -> Bool
< forall a. Complete a -> Int
weight Complete a
a = forall a. Complete a -> Future a
Last (forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete Int
n a -> a
f Complete a
a)
| Bool
otherwise = Future a
d
adjust !Int
n a -> a
f (Complete a
a :< Future a
as)
| Int
n forall a. Ord a => a -> a -> Bool
< Int
w = forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete Int
n a -> a
f Complete a
a forall a. Complete a -> Future a -> Future a
:< Future a
as
| Bool
otherwise = Complete a
a forall a. Complete a -> Future a -> Future a
:< forall a. Int -> (a -> a) -> Future a -> Future a
adjust (Int
n forall a. Num a => a -> a -> a
- Int
w) a -> a
f Future a
as
where w :: Int
w = forall a. Complete a -> Int
weight Complete a
a
adjustComplete :: Int -> (a -> a) -> Complete a -> Complete a
adjustComplete :: forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete Int
0 a -> a
f (Tip a
a) = forall a. a -> Complete a
Tip (a -> a
f a
a)
adjustComplete Int
_ a -> a
_ t :: Complete a
t@Tip{} = Complete a
t
adjustComplete Int
n a -> a
f (Bin Int
m a
a Complete a
l Complete a
r)
| Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m (a -> a
f a
a) Complete a
l Complete a
r
| Int
n forall a. Ord a => a -> a -> Bool
< Int
w = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m a
a (forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete (Int
n forall a. Num a => a -> a -> a
- Int
1) a -> a
f Complete a
l) Complete a
r
| Bool
otherwise = forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m a
a Complete a
l (forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete (Int
n forall a. Num a => a -> a -> a
- Int
1 forall a. Num a => a -> a -> a
- Int
w) a -> a
f Complete a
r)
where w :: Int
w = forall a. Complete a -> Int
weight Complete a
l
update :: Int -> a -> Future a -> Future a
update :: forall a. Int -> a -> Future a -> Future a
update Int
n = forall a. Int -> (a -> a) -> Future a -> Future a
adjust Int
n forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const