{-# LANGUAGE PatternGuards, BangPatterns, TypeFamilies #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE Trustworthy #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Stream.Future.Skew
-- Copyright   :  (C) 2008-2015 Edward Kmett,
--                (C) 2004 Dave Menendez
-- License     :  BSD-style (see the file LICENSE)
--
-- Maintainer  :  Edward Kmett <ekmett@gmail.com>
-- Stability   :  provisional
-- Portability :  portable
--
-- Anticausal streams implemented as non-empty skew binary random access lists
--
-- The Applicative zips streams, but since these are potentially infinite
-- this is stricter than would be desired. You almost always want
------------------------------------------------------------------------------


module Data.Stream.Future.Skew
    ( Future(..)
    , (<|)      -- O(1)
    , length    -- O(log n)
    , tail      -- O(1)
    , last      -- O(log n)
    , uncons    -- O(1)
    , index     -- O(log n)
    , drop      -- O(log n)
    , dropWhile -- O(n)
    , indexed
    , from
    , break
    , span
    , split     -- O(log n)
    , splitW    -- O(log n)
    , replicate -- O(log n)
    , insert    -- O(n)
    , insertBy
    , update
    , adjust    -- O(log n)
    , toFuture
    , singleton
    ) where

import Control.Applicative hiding (empty)
import Control.Comonad
import Data.Functor.Alt
import Data.Functor.Extend
import Prelude hiding (tail, drop, dropWhile, last, span, repeat, replicate, break)
import Data.Foldable (toList)
#if !(MIN_VERSION_base(4,11,0))
import Data.Semigroup hiding (Last)
#endif
import Data.Semigroup.Foldable
import Data.Semigroup.Traversable
import qualified GHC.Exts as Exts

infixr 5 :<, <|

data Complete a
    = Tip a
    | Bin {-# UNPACK #-} !Int a !(Complete a) !(Complete a)
    deriving Int -> Complete a -> ShowS
[Complete a] -> ShowS
Complete a -> String
(Int -> Complete a -> ShowS)
-> (Complete a -> String)
-> ([Complete a] -> ShowS)
-> Show (Complete a)
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
$cshowsPrec :: forall a. Show a => Int -> Complete a -> ShowS
showsPrec :: Int -> Complete a -> ShowS
$cshow :: forall a. Show a => Complete a -> String
show :: Complete a -> String
$cshowList :: forall a. Show a => [Complete a] -> ShowS
showList :: [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) = b -> Complete b
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) = Int -> b -> Complete b -> Complete b -> Complete b
forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
w (a -> b
f a
a) ((a -> b) -> Complete a -> Complete b
forall a b. (a -> b) -> Complete a -> Complete b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
l) ((a -> b) -> Complete a -> Complete b
forall a b. (a -> b) -> Complete a -> Complete b
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 = (Complete a -> b) -> Complete a -> Complete b
forall a b. (Complete a -> b) -> Complete a -> Complete b
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 {} = b -> Complete b
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) = Int -> b -> Complete b -> Complete b -> Complete b
forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (Complete a -> b
f Complete a
w) ((Complete a -> b) -> Complete a -> Complete b
forall a b. (Complete a -> b) -> Complete a -> Complete b
forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Complete a -> b
f Complete a
l) ((Complete a -> b) -> Complete a -> Complete b
forall a b. (Complete a -> b) -> Complete a -> Complete b
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 m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` (a -> m) -> Complete a -> m
forall m a. Monoid m => (a -> m) -> Complete a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
l m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` (a -> m) -> Complete a -> m
forall m a. Monoid m => (a -> m) -> Complete a -> m
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 ((a -> b -> b) -> b -> Complete a -> b
forall a b. (a -> b -> b) -> b -> Complete a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f ((a -> b -> b) -> b -> Complete a -> b
forall a b. (a -> b -> b) -> b -> Complete a -> b
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)
  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

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 m -> m -> m
forall a. Semigroup a => a -> a -> a
<> (a -> m) -> Complete a -> m
forall m a. Semigroup m => (a -> m) -> Complete a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
l m -> m -> m
forall a. Semigroup a => a -> a -> a
<> (a -> m) -> Complete a -> m
forall m a. Semigroup m => (a -> m) -> Complete a -> m
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) = b -> Complete b
forall a. a -> Complete a
Tip (b -> Complete b) -> f b -> f (Complete b)
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) = Int -> b -> Complete b -> Complete b -> Complete b
forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (b -> Complete b -> Complete b -> Complete b)
-> f b -> f (Complete b -> Complete b -> Complete b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a f (Complete b -> Complete b -> Complete b)
-> f (Complete b) -> f (Complete b -> Complete b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse a -> f b
f Complete a
l f (Complete b -> Complete b) -> f (Complete b) -> f (Complete b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Complete a -> f (Complete 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) = b -> Complete b
forall a. a -> Complete a
Tip (b -> Complete b) -> f b -> f (Complete b)
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) = Int -> b -> Complete b -> Complete b -> Complete b
forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
n (b -> Complete b -> Complete b -> Complete b)
-> f b -> f (Complete b -> Complete b -> Complete b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a f (Complete b -> Complete b -> Complete b)
-> f (Complete b) -> f (Complete b -> Complete b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse1 a -> f b
f Complete a
l f (Complete b -> Complete b) -> f (Complete b) -> f (Complete b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Complete a -> f (Complete 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 = Int -> a -> Complete a -> Complete a -> Complete a
forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin (Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Complete a -> Int
forall a. Complete a -> Int
weight Complete a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Complete a -> Int
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 #-}

-- A future is a non-empty skew binary random access list of nodes.
-- The last node, however, is allowed to contain fewer values.
data Future a
  = Last !(Complete a)
  | !(Complete a) :< Future a
--  deriving Show


instance Show a => Show (Future a) where
  showsPrec :: Int -> Future a -> ShowS
showsPrec Int
d Future a
as = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [a] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (Future a -> [a]
forall a. Future a -> [a]
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) = (a -> b) -> Complete a -> Complete b
forall a b. (a -> b) -> Complete a -> Complete b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Complete a
t Complete b -> Future b -> Future b
forall a. Complete a -> Future a -> Future a
:< (a -> b) -> Future a -> Future b
forall a b. (a -> b) -> Future a -> Future b
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) = Complete b -> Future b
forall a. Complete a -> Future a
Last ((a -> b) -> Complete a -> Complete b
forall a b. (a -> b) -> Complete a -> Complete b
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 = (Future a -> b) -> Future a -> Future b
forall a b. (Future a -> b) -> Future a -> Future b
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)  = Complete b -> Future b
forall a. Complete a -> Future a
Last ((Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
t Complete a -> Future a
forall a. Complete a -> Future a
Last)
  extend Future a -> b
g (Complete a
t :< Future a
ts) = (Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
t (Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
ts) Complete b -> Future b -> Future b
forall a. Complete a -> Future a -> Future a
:< (Future a -> b) -> Future a -> Future b
forall a b. (Future a -> b) -> Future a -> Future b
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
_) = Complete a -> a
forall a. Complete a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a
  extract (Last Complete a
a) = Complete a -> a
forall a. 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 = b -> Complete b
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 = Int -> b -> Complete b -> Complete b -> Complete b
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)) ((Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
forall a b.
(Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
extendTree Future a -> b
g Complete a
l (Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r))  ((Future a -> b)
-> Complete a -> (Complete a -> Future a) -> Complete b
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                   = b -> Future b
forall a. a -> Future a
singleton (a -> b
f (Future a -> a
forall a. Future a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as))
  Future (a -> b)
fs                   <.> Last (Tip a
a)         = b -> Future b
forall a. a -> Future a
singleton (Future (a -> b) -> a -> b
forall a. Future a -> a
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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Complete (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a
Last Complete (a -> b)
rf  Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete 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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Complete (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a
Last Complete (a -> b)
rf  Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a
ra Complete a -> Future a -> Future a
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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Complete (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a
Last Complete (a -> b)
rf  Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete 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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Complete (a -> b)
lf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Complete (a -> b)
rf Complete (a -> b) -> Future (a -> b) -> Future (a -> b)
forall a. Complete a -> Future a -> Future a
:< Future (a -> b)
fs Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a
ra Complete a -> Future a -> Future a
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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs             Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs             Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a
ra Complete a -> Future a -> Future a
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 b -> Future b -> Future b
forall a. a -> Future a -> Future a
<| (Future (a -> b)
fs             Future (a -> b) -> Future a -> Future b
forall a b. Future (a -> b) -> Future a -> Future b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Complete a
la Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete 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
(<@>) = Future (a -> b) -> Future a -> Future b
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 = a -> Complete a -> Future a
forall a. a -> Complete a -> Future a
go a
a0 (a -> Complete a
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 <- a -> Complete a -> Complete a -> Complete a
forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
as Complete a
as = Complete a
as Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< a -> Complete 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
(<*>) = Future (a -> b) -> Future a -> Future b
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 = (a -> Future a -> Future a) -> Future a -> Future a -> Future a
forall a b. (a -> b -> b) -> b -> Future a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Future a -> Future a
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) = (a -> m) -> Complete a -> m
forall m a. Monoid m => (a -> m) -> Complete a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Complete a
t m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` (a -> m) -> Future a -> m
forall m a. Monoid m => (a -> m) -> Future a -> m
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) = (a -> m) -> Complete a -> m
forall m a. Monoid m => (a -> m) -> Complete a -> m
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) = (a -> b -> b) -> b -> Complete a -> b
forall a b. (a -> b -> b) -> b -> Complete a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f ((a -> b -> b) -> b -> Future a -> b
forall a b. (a -> b -> b) -> b -> Future a -> b
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) = (a -> b -> b) -> b -> Complete a -> b
forall a b. (a -> b -> b) -> b -> Complete a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z Complete a
t
  length :: forall a. Future a -> Int
length (Last Complete a
t) = Complete a -> Int
forall a. Complete a -> Int
weight Complete a
t
  length (Complete a
t :< Future a
ts) = Complete a -> Int
forall a. Complete a -> Int
weight Complete a
t Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Future a -> Int
forall a. Future a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Future a
ts
  null :: forall a. Future a -> Bool
null Future a
_ = Bool
False

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) = (a -> m) -> Complete a -> m
forall m a. Semigroup m => (a -> m) -> Complete a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
foldMap1 a -> m
f Complete a
t m -> m -> m
forall a. Semigroup a => a -> a -> a
<> (a -> m) -> Future a -> m
forall m a. Semigroup m => (a -> m) -> Future a -> m
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) = (a -> m) -> Complete a -> m
forall m a. Semigroup m => (a -> m) -> Complete a -> m
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) = Complete b -> Future b -> Future b
forall a. Complete a -> Future a -> Future a
(:<) (Complete b -> Future b -> Future b)
-> f (Complete b) -> f (Future b -> Future b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse a -> f b
f Complete a
t f (Future b -> Future b) -> f (Future b) -> f (Future b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (a -> f b) -> Future a -> f (Future b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Future a -> f (Future b)
traverse a -> f b
f Future a
ts
  traverse a -> f b
f (Last Complete a
t) = Complete b -> Future b
forall a. Complete a -> Future a
Last (Complete b -> Future b) -> f (Complete b) -> f (Future b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Complete a -> f (Complete 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) = Complete b -> Future b -> Future b
forall a. Complete a -> Future a -> Future a
(:<) (Complete b -> Future b -> Future b)
-> f (Complete b) -> f (Future b -> Future b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse1 a -> f b
f Complete a
t f (Future b -> Future b) -> f (Future b) -> f (Future b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> (a -> f b) -> Future a -> f (Future b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Future a -> f (Future b)
traverse1 a -> f b
f Future a
ts
  traverse1 a -> f b
f (Last Complete a
t) = Complete b -> Future b
forall a. Complete a -> Future a
Last (Complete b -> Future b) -> f (Complete b) -> f (Future b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Complete a -> f (Complete b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Complete a -> f (Complete b)
traverse1 a -> f b
f Complete a
t

-- | /O(log n)/
replicate :: Int -> a -> Future a
replicate :: forall a. Int -> a -> Future a
replicate Int
n a
a
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = String -> Future a
forall a. HasCallStack => String -> a
error String
"replicate: non-positive argument"
  | Bool
otherwise = Int
-> Int
-> a
-> Complete a
-> (Int -> Future a -> Future a)
-> Future a
forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go Int
1 Int
n a
a (a -> Complete a
forall a. a -> Complete a
Tip a
a) (\ Int
_ Future a
r -> Future a
r)
  where
  -- invariants:
  -- tb is a complete tree of i nodes all equal to b
  -- 1 <= i = 2^m-1 <= j
  -- k accepts r such that 0 <= r < i
  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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
i2p1 = Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
forall b r.
Int -> Int -> b -> Complete b -> (Int -> Future b -> r) -> r
go Int
i2p1 Int
j b
b (Int -> b -> Complete b -> Complete b -> Complete 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
i2   = Int -> Future b -> r
k (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i2) (Complete b
tb Complete b -> Future b -> Future b
forall a. Complete a -> Future a -> Future a
:< Complete b -> Future b
forall a. Complete a -> Future a
Last Complete b
tb)
    | Bool
otherwise = Int -> Future b -> r
k (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) (Complete b -> Future b
forall a. Complete a -> Future a
Last Complete b
tb)
    where
      i2 :: Int
i2 = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
2
      i2p1 :: Int
i2p1 = Int
i2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
      k' :: Int -> Future b -> r
k' Int
r Future b
xs
        | Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
i2   = Int -> Future b -> r
k (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i2) (Complete b
tb Complete b -> Future b -> Future b
forall a. Complete a -> Future a -> Future a
:< Complete b
tb Complete b -> Future b -> Future b
forall a. Complete a -> Future a -> Future a
:< Future b
xs)
        | Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
i    = Int -> Future b -> r
k (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) (Complete b
tb Complete b -> Future b -> Future b
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 = (Int -> a -> b) -> Int -> Future a -> Future b
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) = Complete a -> Future a
forall a. Complete a -> Future a
Last ((Int -> a -> a) -> Int -> Complete a -> Complete a
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) = (Int -> a -> a) -> Int -> Complete a -> Complete a
forall {a} {a}. (Int -> a -> a) -> Int -> Complete a -> Complete a
tree Int -> a -> a
f Int
m Complete a
a Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< (Int -> a -> a) -> Int -> Future a -> Future a
spine Int -> a -> a
f (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Complete a -> Int
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) = a -> Complete 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) = Int -> a -> Complete a -> Complete a -> Complete a
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 Int -> Int -> Int
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Complete a -> Int
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 = (Int -> a -> (Int, a)) -> Future a -> Future (Int, a)
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 = (Int -> a -> a) -> Future a -> Future a
forall a b. (Int -> a -> b) -> Future a -> Future b
mapWithIndex (a -> a -> a
forall a. Num a => a -> a -> a
(+) (a -> a -> a) -> (Int -> a) -> Int -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral) (a -> Future a
forall a. a -> Future a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a)
{-# INLINE from #-}

-- | /O(1)/
singleton :: a -> Future a
singleton :: forall a. a -> Future a
singleton a
a = Complete a -> Future a
forall a. Complete a -> Future a
Last (a -> Complete a
forall a. a -> Complete a
Tip a
a)
{-# INLINE singleton #-}

-- | /O(1)/ cons
(<|) :: a -> Future a -> Future a
a
a <| :: forall a. a -> Future a -> Future a
<| (Complete a
l :< Last Complete a
r)
  | Complete a -> Int
forall a. Complete a -> Int
weight Complete a
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Complete a -> Int
forall a. Complete a -> Int
weight Complete a
r = Complete a -> Future a
forall a. Complete a -> Future a
Last (a -> Complete a -> Complete a -> Complete a
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)
  | Complete a -> Int
forall a. Complete a -> Int
weight Complete a
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Complete a -> Int
forall a. Complete a -> Int
weight Complete a
r = a -> Complete a -> Complete a -> Complete a
forall a. a -> Complete a -> Complete a -> Complete a
bin a
a Complete a
l Complete a
r Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
as
a
a <| Future a
as = a -> Complete a
forall a. a -> Complete a
Tip a
a Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
as
{-# INLINE (<|) #-}

-- | /O(1)/.
tail :: Future a -> Maybe (Future a)
tail :: forall a. Future a -> Maybe (Future a)
tail (Tip{} :< Future a
ts) = Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
ts
tail (Bin Int
_ a
_ Complete a
l Complete a
r :< Future a
ts) = Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Complete a
l Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a
r Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
ts)
tail (Last Tip{}) = Maybe (Future a)
forall a. Maybe a
Nothing
tail (Last (Bin Int
_ a
_ Complete a
l Complete a
r)) = Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Complete a
l Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
forall a. Complete a -> Future a
Last Complete a
r)
{-# INLINE tail #-}

-- | /O(log n)/.
last :: Future a -> a
last :: forall a. Future a -> a
last (Complete a
_ :< Future a
as) = Future a -> a
forall a. Future a -> a
last Future a
as
last (Last Complete a
as) = Complete a -> a
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

-- | /O(1)/.
uncons :: Future a -> (a, Maybe (Future a))
uncons :: forall a. Future a -> (a, Maybe (Future a))
uncons (Last (Tip a
a))       = (a
a, Maybe (Future a)
forall a. Maybe a
Nothing)
uncons (Last (Bin Int
_ a
a Complete a
l Complete a
r)) = (a
a, Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Complete a
l Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
forall a. Complete a -> Future a
Last Complete a
r))
uncons (Tip a
a       :< Future a
as)  = (a
a, Future a -> Maybe (Future 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, Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Complete a
l Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a
r Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
as))
{-# INLINE uncons #-}

-- | /O(log n)/.
index :: Int -> Future a -> a
index :: forall a. Int -> Future a -> a
index Int
i (Last Complete a
t)
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Complete a -> Int
forall a. Complete a -> Int
weight Complete a
t = Int -> Complete a -> a
forall a. Int -> Complete a -> a
indexComplete Int
i Complete a
t
  | Bool
otherwise    = String -> a
forall a. HasCallStack => String -> a
error String
"index: out of range"
index Int
i (Complete a
t :< Future a
ts)
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
w     = Int -> Complete a -> a
forall a. Int -> Complete a -> a
indexComplete Int
i Complete a
t
  | Bool
otherwise = Int -> Future a -> a
forall a. Int -> Future a -> a
index (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
w) Future a
ts
  where w :: Int
w = Complete a -> Int
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = a
a
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
w'   = Int -> Complete a -> a
forall a. Int -> Complete a -> a
indexComplete (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Complete a
l
  | Bool
otherwise = Int -> Complete a -> a
forall a. Int -> Complete a -> a
indexComplete (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
w') Complete a
r
  where w' :: Int
w' = Int -> Int -> Int
forall a. Integral a => a -> a -> a
div Int
w Int
2
indexComplete Int
_ Complete a
_ = String -> a
forall a. HasCallStack => String -> a
error String
"index: index out of range"

-- | /O(log n)/.
drop :: Int -> Future a -> Maybe (Future a)
drop :: forall a. Int -> Future a -> Maybe (Future a)
drop Int
0 Future a
ts = Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
ts
drop Int
i (Complete a
t :< Future a
ts) = case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
i Int
w of
  Ordering
LT -> Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Int -> Complete a -> (Complete a -> Future a) -> Future a
forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
i Complete a
t (Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
ts))
  Ordering
EQ -> Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
ts
  Ordering
GT -> Int -> Future a -> Maybe (Future a)
forall a. Int -> Future a -> Maybe (Future a)
drop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
w) Future a
ts
  where w :: Int
w = Complete a -> Int
forall a. Complete a -> Int
weight Complete a
t
drop Int
i (Last Complete a
t)
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
w     = Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Int -> Complete a -> (Complete a -> Future a) -> Future a
forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete Int
i Complete a
t Complete a -> Future a
forall a. Complete a -> Future a
Last)
  | Bool
otherwise = Maybe (Future a)
forall a. Maybe a
Nothing
  where w :: Int
w = Complete a -> Int
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 Complete a -> Future a -> Future a
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 Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
w' of
  Ordering
LT -> Int -> Complete a -> (Complete a -> Future a) -> Future a
forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Complete a
l (Complete a -> Future a -> Future a
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 -> Int -> Complete a -> (Complete a -> Future a) -> Future a
forall a. Int -> Complete a -> (Complete a -> Future a) -> Future a
dropComplete (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
w') Complete a
r Complete a -> Future a
f
  where w' :: Int
w' = Int -> Int -> Int
forall a. Integral a => a -> a -> a
div Int
w Int
2
dropComplete Int
_ Complete a
_ Complete a -> Future a
_ = String -> Future a
forall a. HasCallStack => String -> a
error String
"drop: index out of range"

-- /O(n)/.
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 (Future a -> a
forall a. Future a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as) = Future a -> Maybe (Future a)
forall a. Future a -> Maybe (Future a)
tail Future a
as Maybe (Future a)
-> (Future a -> Maybe (Future a)) -> Maybe (Future a)
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (a -> Bool) -> Future a -> Maybe (Future a)
forall a. (a -> Bool) -> Future a -> Maybe (Future a)
dropWhile a -> Bool
p
  | Bool
otherwise = Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
as

-- /O(n)/
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 Future a -> (a, Maybe (Future a))
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) <- (a -> Bool) -> Future a -> ([a], Maybe (Future a))
forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span a -> Bool
p Future a
as -> (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
  (a
a, Maybe (Future a)
Nothing) | a -> Bool
p a
a                        -> ([a
a], Maybe (Future a)
forall a. Maybe a
Nothing)
  (a
_, Maybe (Future a)
_)                                    -> ([], Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
aas)

-- /O(n)/
break :: (a -> Bool) -> Future a -> ([a], Maybe (Future a))
break :: forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
break a -> Bool
p = (a -> Bool) -> Future a -> ([a], Maybe (Future a))
forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
span (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)

-- /(O(n), O(log n))/ split at _some_ edge where function goes from False to True.
-- best used with a monotonic function
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 (Complete a -> a
forall a. Complete a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
a)  = ([], Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
l)
  | Bool
otherwise      = (a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
a Complete a -> Future a
forall a. Complete a -> Future a
Last
split a -> Bool
p (Complete a
a :< Future a
as)
  | a -> Bool
p (Future a -> a
forall a. Future a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract Future a
as) = (a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
a (Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
as)
  | ([a]
ts, Maybe (Future a)
fs) <- (a -> Bool) -> Future a -> ([a], Maybe (Future a))
forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split a -> Bool
p Future a
as = ((a -> [a] -> [a]) -> [a] -> Complete a -> [a]
forall a b. (a -> b -> b) -> b -> Complete a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
a, Maybe (Future a)
fs)

-- for use when we know the split occurs within a given tree
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       = ([], Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Complete a -> Future a
f Complete a
t))
  | Bool
otherwise = ([a
a], Maybe (Future 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                                               = ([], Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just (Complete a -> Future a
f Complete a
t))
  | a -> Bool
p (Complete a -> a
forall a. Complete a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract Complete a
r), ([a]
ts, Maybe (Future a)
fs) <- (a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
forall a.
(a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitComplete a -> Bool
p Complete a
l (Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Complete a -> Future a
f Complete a
r) = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
  |                ([a]
ts, Maybe (Future a)
fs) <- (a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
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
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:(a -> [a] -> [a]) -> [a] -> Complete a -> [a]
forall a b. (a -> b -> b) -> b -> Complete a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
l, Maybe (Future a)
fs)

-- /(O(n), O(log n))/ split at _some_ edge where function goes from False to True.
-- best used with a monotonic function
--
-- > splitW p xs = (map extract &&& fmap (fmap extract)) . split p . duplicate
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       = ([], Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
l)
  | Bool
otherwise = (Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
a Complete a -> Future 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                    = (Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
a (Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
as)
  | ([a]
ts, Maybe (Future a)
fs) <- (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
forall a. (Future a -> Bool) -> Future a -> ([a], Maybe (Future a))
splitW Future a -> Bool
p Future a
as = ((a -> [a] -> [a]) -> [a] -> Complete a -> [a]
forall a b. (a -> b -> b) -> b -> Complete a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
a, Maybe (Future a)
fs)

-- for use when we know the split occurs within a given tree
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 = ([], Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just Future a
w)
  | Bool
otherwise = ([a
a], Maybe (Future 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                                    = ([], Future a -> Maybe (Future a)
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) <- (Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
forall a.
(Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
splitCompleteW Future a -> Bool
p Complete a
l (Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
w) = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ts, Maybe (Future a)
fs)
  |                ([a]
ts, Maybe (Future a)
fs) <- (Future a -> Bool)
-> Complete a
-> (Complete a -> Future a)
-> ([a], Maybe (Future a))
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
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:(a -> [a] -> [a]) -> [a] -> Complete a -> [a]
forall a b. (a -> b -> b) -> b -> Complete a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [a]
ts Complete a
l, Maybe (Future a)
fs)

instance Exts.IsList (Future a) where
  type Item (Future a) = a
  toList :: Future a -> [Item (Future a)]
toList = Future a -> [a]
Future a -> [Item (Future a)]
forall a. Future a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Data.Foldable.toList
  fromList :: [Item (Future a)] -> Future a
fromList [] = String -> Future a
forall a. HasCallStack => String -> a
error String
"fromList: empty list"
  fromList (Item (Future a)
x:[Item (Future a)]
xs) = a -> [a] -> Future a
forall {t}. t -> [t] -> Future t
go a
Item (Future a)
x [a]
[Item (Future a)]
xs
    where go :: t -> [t] -> Future t
go t
a [] = t -> Future t
forall a. a -> Future a
singleton t
a
          go t
a (t
b:[t]
bs) = t
a t -> Future t -> Future t
forall a. a -> Future a -> Future a
<| t -> [t] -> Future t
go t
b [t]
bs

toFuture :: [a] -> Maybe (Future a)
toFuture :: forall a. [a] -> Maybe (Future a)
toFuture [] = Maybe (Future a)
forall a. Maybe a
Nothing
toFuture [a]
xs = Future a -> Maybe (Future a)
forall a. a -> Maybe a
Just ([Item (Future a)] -> Future a
forall l. IsList l => [Item l] -> l
Exts.fromList [a]
[Item (Future a)]
xs)

-- /O(n)/
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 (a -> Bool) -> Future a -> ([a], Maybe (Future a))
forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split (a
aa -> a -> Bool
forall a. Ord a => a -> a -> Bool
<=) Future a
as of
    ([a]
_, Maybe (Future a)
Nothing)  -> (a -> Future a -> Future a) -> Future a -> Future a -> Future a
forall a b. (a -> b -> b) -> b -> Future a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Future a -> Future a
forall a. a -> Future a -> Future a
(<|) (a -> Future a
forall a. a -> Future a
singleton a
a) Future a
as
    ([a]
ts, Just Future a
as') -> (a -> Future a -> Future a) -> Future a -> [a] -> Future a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Future a -> Future a
forall a. a -> Future a -> Future a
(<|) (a
a a -> Future a -> Future a
forall a. a -> Future a -> Future a
<| Future a
as') [a]
ts

-- /O(n)/. Finds the split in O(log n), but then has to recons
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 (a -> Bool) -> Future a -> ([a], Maybe (Future a))
forall a. (a -> Bool) -> Future a -> ([a], Maybe (Future a))
split (\a
b -> a -> a -> Ordering
cmp a
a a
b Ordering -> Ordering -> Bool
forall a. Ord a => a -> a -> Bool
<= Ordering
EQ) Future a
as of
    ([a]
_, Maybe (Future a)
Nothing)  -> (a -> Future a -> Future a) -> Future a -> Future a -> Future a
forall a b. (a -> b -> b) -> b -> Future a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Future a -> Future a
forall a. a -> Future a -> Future a
(<|) (a -> Future a
forall a. a -> Future a
singleton a
a) Future a
as
    ([a]
ts, Just Future a
as') -> (a -> Future a -> Future a) -> Future a -> [a] -> Future a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Future a -> Future a
forall a. a -> Future a -> Future a
(<|) (a
a a -> Future a -> Future a
forall a. a -> Future a -> Future a
<| Future a
as') [a]
ts

-- /O(log n)/ Change the value of the nth entry in the future
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Complete a -> Int
forall a. Complete a -> Int
weight Complete a
a = Complete a -> Future a
forall a. Complete a -> Future a
Last (Int -> (a -> a) -> Complete a -> Complete a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
w = Int -> (a -> a) -> Complete a -> Complete a
forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete Int
n a -> a
f Complete a
a Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Future a
as
  | Bool
otherwise = Complete a
a Complete a -> Future a -> Future a
forall a. Complete a -> Future a -> Future a
:< Int -> (a -> a) -> Future a -> Future a
forall a. Int -> (a -> a) -> Future a -> Future a
adjust (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
w) a -> a
f Future a
as
  where w :: Int
w = Complete a -> Int
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) = a -> Complete 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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Int -> a -> Complete a -> Complete a -> Complete a
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
w = Int -> a -> Complete a -> Complete a -> Complete a
forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m a
a (Int -> (a -> a) -> Complete a -> Complete a
forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) a -> a
f Complete a
l) Complete a
r
  | Bool
otherwise = Int -> a -> Complete a -> Complete a -> Complete a
forall a. Int -> a -> Complete a -> Complete a -> Complete a
Bin Int
m a
a Complete a
l (Int -> (a -> a) -> Complete a -> Complete a
forall a. Int -> (a -> a) -> Complete a -> Complete a
adjustComplete (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
w) a -> a
f Complete a
r)
  where w :: Int
w = Complete a -> Int
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 = Int -> (a -> a) -> Future a -> Future a
forall a. Int -> (a -> a) -> Future a -> Future a
adjust Int
n ((a -> a) -> Future a -> Future a)
-> (a -> a -> a) -> a -> Future a -> Future a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> a
forall a b. a -> b -> a
const