-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Strict GC'd imperative object-oriented programming with cheap pointers.
--   
--   This project is an experiment with a small GC'd strict mutable
--   imperative universe with cheap pointers inside of the GHC runtime
--   system.
@package structs
@version 0.1.1


module Data.Struct.Internal
data NullPointerException
NullPointerException :: NullPointerException

-- | A <a>Dict</a> reifies an instance of the constraint <tt>p</tt> into a
--   value.
data Dict p
[Dict] :: p => Dict p

-- | Run an ST calculation inside of a PrimMonad. This lets us avoid
--   dispatching everything through the <a>PrimMonad</a> dictionary.
st :: PrimMonad m => ST (PrimState m) a -> m a

-- | An instance for <a>Struct</a> <tt>t</tt> is a witness to the
--   machine-level equivalence of <tt>t</tt> and <tt>Object</tt>.
class Struct t
struct :: Struct t => Dict (Coercible (t s) (Object s))
struct :: (Struct t, Coercible (t s) (Object s)) => Dict (Coercible (t s) (Object s))
data Object s
Object :: SmallMutableArray# s Any -> Object s
[runObject] :: Object s -> SmallMutableArray# s Any
coerceF :: Dict (Coercible a b) -> a -> b
coerceB :: Dict (Coercible a b) -> b -> a
destruct :: Struct t => t s -> SmallMutableArray# s Any
construct :: Struct t => SmallMutableArray# s Any -> t s
unsafeCoerceStruct :: (Struct x, Struct y) => x s -> y s
eqStruct :: Struct t => t s -> t s -> Bool

-- | Allocate a structure made out of <tt>n</tt> slots. Initialize the
--   structure before proceeding!
alloc :: (PrimMonad m, Struct t) => Int -> m (t (PrimState m))

-- | Box is designed to mirror object's single field but using the
--   <a>Null</a> type instead of a mutable array. This hack relies on GHC
--   reusing the same <a>Null</a> data constructor for all occurrences.
--   Box's field must not be strict to prevent the compiler from making
--   assumptions about its contents.
data Box
Box :: Null -> Box
data Null
Null :: Null

-- | Predicate to check if a struct is <a>Nil</a>.
--   
--   <pre>
--   &gt;&gt;&gt; isNil (Nil :: Object (PrimState IO))
--   True
--   
--   &gt;&gt;&gt; o &lt;- alloc 1 :: IO (Object (PrimState IO))
--   
--   &gt;&gt;&gt; isNil o
--   False
--   </pre>
isNil :: Struct t => t s -> Bool

-- | Truly imperative.
writeSmallMutableArraySmallArray# :: SmallMutableArray# s Any -> Int# -> SmallMutableArray# s Any -> State# s -> State# s
readSmallMutableArraySmallArray# :: SmallMutableArray# s Any -> Int# -> State# s -> (# State# s, SmallMutableArray# s Any #)
writeMutableByteArraySmallArray# :: SmallMutableArray# s Any -> Int# -> MutableByteArray# s -> State# s -> State# s
readMutableByteArraySmallArray# :: SmallMutableArray# s Any -> Int# -> State# s -> (# State# s, MutableByteArray# s #)
casSmallMutableArraySmallArray# :: SmallMutableArray# s Any -> Int# -> SmallMutableArray# s Any -> SmallMutableArray# s Any -> State# s -> (# State# s, Int#, SmallMutableArray# s Any #)

-- | A <a>Slot</a> is a reference to another unboxed mutable object.
data Slot x y
Slot :: (forall s. SmallMutableArray# s Any -> State# s -> (# State# s, SmallMutableArray# s Any #)) -> (forall s. SmallMutableArray# s Any -> SmallMutableArray# s Any -> State# s -> State# s) -> (forall s. SmallMutableArray# s Any -> SmallMutableArray# s Any -> SmallMutableArray# s Any -> State# s -> (# State# s, Int#, SmallMutableArray# s Any #)) -> Slot x y

-- | We can compose slots to get a nested slot or field accessor
class Precomposable t
(#) :: Precomposable t => Slot x y -> t y z -> t x z

-- | The <a>Slot</a> at the given position in a <a>Struct</a>
slot :: Int -> Slot s t

-- | Get the value from a <a>Slot</a>
get :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> m (y (PrimState m))

-- | Set the value of a <a>Slot</a>
set :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> y (PrimState m) -> m ()

-- | Compare-and-swap the value of the slot. Takes the expected old value,
--   the new value and returns if it succeeded and the value found.
cas :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> y (PrimState m) -> y (PrimState m) -> m (Bool, y (PrimState m))

-- | A <a>Field</a> is a reference from a struct to a normal Haskell data
--   type.
data Field x a
Field :: (forall s. SmallMutableArray# s Any -> State# s -> (# State# s, a #)) -> (forall s. SmallMutableArray# s Any -> a -> State# s -> State# s) -> Field x a

-- | Store the reference to the Haskell data type in a normal field
field :: Int -> Field s a

-- | Store the reference in the nth slot in the nth argument, treated as a
--   MutableByteArray
unboxedField :: Prim a => Int -> Int -> Field s a

-- | Initialized the mutable array used by <a>unboxedField</a>. Returns the
--   array after storing it in the struct to help with initialization.
initializeUnboxedField :: (PrimMonad m, Struct x) => Int -> Int -> Int -> x (PrimState m) -> m (MutableByteArray (PrimState m))

-- | Get the value of a field in a struct
getField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> m a

-- | Set the value of a field in a struct
setField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> a -> m ()
modifyField :: (Struct x, PrimMonad m) => Field x a -> x (PrimState m) -> (a -> a) -> m ()
modifyField' :: (Struct x, PrimMonad m) => Field x a -> x (PrimState m) -> (a -> a) -> m ()
instance GHC.Exception.Exception Data.Struct.Internal.NullPointerException
instance GHC.Show.Show Data.Struct.Internal.NullPointerException
instance Data.Struct.Internal.Precomposable Data.Struct.Internal.Field
instance Data.Struct.Internal.Precomposable Data.Struct.Internal.Slot
instance Data.Struct.Internal.Struct Data.Struct.Internal.Object
instance GHC.Classes.Eq (Data.Struct.Internal.Object s)


module Data.Struct

-- | An instance for <a>Struct</a> <tt>t</tt> is a witness to the
--   machine-level equivalence of <tt>t</tt> and <tt>Object</tt>.
class Struct t
struct :: Struct t => Dict (Coercible (t s) (Object s))
struct :: (Struct t, Coercible (t s) (Object s)) => Dict (Coercible (t s) (Object s))
data Object s
destruct :: Struct t => t s -> SmallMutableArray# s Any
construct :: Struct t => SmallMutableArray# s Any -> t s
eqStruct :: Struct t => t s -> t s -> Bool

-- | Allocate a structure made out of <tt>n</tt> slots. Initialize the
--   structure before proceeding!
alloc :: (PrimMonad m, Struct t) => Int -> m (t (PrimState m))

-- | Truly imperative.

-- | Predicate to check if a struct is <a>Nil</a>.
--   
--   <pre>
--   &gt;&gt;&gt; isNil (Nil :: Object (PrimState IO))
--   True
--   
--   &gt;&gt;&gt; o &lt;- alloc 1 :: IO (Object (PrimState IO))
--   
--   &gt;&gt;&gt; isNil o
--   False
--   </pre>
isNil :: Struct t => t s -> Bool
data NullPointerException
NullPointerException :: NullPointerException

-- | A <a>Slot</a> is a reference to another unboxed mutable object.
data Slot x y

-- | The <a>Slot</a> at the given position in a <a>Struct</a>
slot :: Int -> Slot s t

-- | Get the value from a <a>Slot</a>
get :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> m (y (PrimState m))

-- | Set the value of a <a>Slot</a>
set :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> y (PrimState m) -> m ()

-- | A <a>Field</a> is a reference from a struct to a normal Haskell data
--   type.
data Field x a

-- | Store the reference to the Haskell data type in a normal field
field :: Int -> Field s a

-- | Store the reference in the nth slot in the nth argument, treated as a
--   MutableByteArray
unboxedField :: Prim a => Int -> Int -> Field s a

-- | Get the value of a field in a struct
getField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> m a

-- | Set the value of a field in a struct
setField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> a -> m ()
modifyField :: (Struct x, PrimMonad m) => Field x a -> x (PrimState m) -> (a -> a) -> m ()
modifyField' :: (Struct x, PrimMonad m) => Field x a -> x (PrimState m) -> (a -> a) -> m ()

-- | We can compose slots to get a nested slot or field accessor
class Precomposable t
(#) :: Precomposable t => Slot x y -> t y z -> t x z


module Data.Struct.Internal.Label
type Key = Word64
midBound :: Key
key :: Field Label Key
next :: Slot Label Label
prev :: Slot Label Label

-- | Logarithmic time list labeling solution
newtype Label s
Label :: (Object s) -> Label s

-- | Construct an explicit list labeling structure.
--   
--   <pre>
--   &gt;&gt;&gt; x &lt;- makeLabel 0 Nil Nil
--   
--   &gt;&gt;&gt; isNil x
--   False
--   
--   &gt;&gt;&gt; n &lt;- get next x
--   
--   &gt;&gt;&gt; isNil n
--   True
--   
--   &gt;&gt;&gt; p &lt;- get prev x
--   
--   &gt;&gt;&gt; isNil p
--   True
--   </pre>
makeLabel :: PrimMonad m => Key -> Label (PrimState m) -> Label (PrimState m) -> m (Label (PrimState m))

-- | O(1). Create a new labeling structure. Labels from different list
--   labeling structures are incomparable.
new :: PrimMonad m => m (Label (PrimState m))

-- | O(1). Remove a label
delete :: PrimMonad m => Label (PrimState m) -> m ()

-- | O(log n) amortized. Insert a new label after a given label.
insertAfter :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

-- | O(1). Split off all labels after the current label.
cutAfter :: PrimMonad m => Label (PrimState m) -> m ()

-- | O(1). Split off all labels before the current label.
cutBefore :: PrimMonad m => Label (PrimState m) -> m ()

-- | O(n). Retrieve the least label
least :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

-- | O(n). Retrieve the greatest label
greatest :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

-- | O(1). Compare two labels for ordering.
compareM :: PrimMonad m => Label (PrimState m) -> Label (PrimState m) -> m Ordering
delta :: Key -> Word64 -> Key

-- | O(1). Extract the current value assignment for this label. Any label
--   mutation, even on other labels in this label structure, may change
--   this answer.
value :: PrimMonad m => Label (PrimState m) -> m Key

-- | O(n). Get the keys of every label from here to the right.
keys :: PrimMonad m => Label (PrimState m) -> m [Key]
instance GHC.Classes.Eq (Data.Struct.Internal.Label.Label s)
instance Data.Struct.Internal.Struct Data.Struct.Internal.Label.Label


module Data.Struct.Label

-- | Logarithmic time list labeling solution
data Label s

-- | O(1). Create a new labeling structure. Labels from different list
--   labeling structures are incomparable.
new :: PrimMonad m => m (Label (PrimState m))

-- | O(log n) amortized. Insert a new label after a given label.
insertAfter :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

-- | O(1). Remove a label
delete :: PrimMonad m => Label (PrimState m) -> m ()

-- | O(n). Retrieve the least label
least :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

-- | O(n). Retrieve the greatest label
greatest :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

-- | O(1). Split off all labels after the current label.
cutAfter :: PrimMonad m => Label (PrimState m) -> m ()

-- | O(1). Split off all labels before the current label.
cutBefore :: PrimMonad m => Label (PrimState m) -> m ()

-- | O(1). Compare two labels for ordering.
compareM :: PrimMonad m => Label (PrimState m) -> Label (PrimState m) -> m Ordering


module Data.Struct.Internal.Order

-- | This structure maintains an order-maintenance structure as two levels
--   of list-labeling.
--   
--   The upper labeling scheme holds <tt>(n / log w)</tt> elements in a
--   universe of size <tt>w^2</tt>, operating in O(log n) amortized time
--   per operation.
--   
--   It is accelerated by an indirection structure where each smaller
--   universe holds O(log w) elements, with total label space <tt>2^log w =
--   w</tt> and O(1) expected update cost, so we can charge rebuilds to the
--   upper structure to the lower structure.
--   
--   Every insert to the upper structure is amortized across <tt>O(log
--   w)</tt> operations below.
--   
--   This means that inserts are O(1) amortized, while comparisons remain
--   O(1) worst-case.
newtype Order a s
Order :: Object s -> Order a s
[runOrder] :: Order a s -> Object s
key :: Field (Order a) Key
value :: Field (Order a) a
next :: Slot (Order a) (Order a)
prev :: Slot (Order a) (Order a)
parent :: Slot (Order a) Label
makeOrder :: PrimMonad m => Label (PrimState m) -> Key -> a -> Order a (PrimState m) -> Order a (PrimState m) -> m (Order a (PrimState m))

-- | O(1) compareM, O(1) amortized insert
compareM :: PrimMonad m => Order a (PrimState m) -> Order a (PrimState m) -> m Ordering
insertAfter :: PrimMonad m => Order a (PrimState m) -> a -> m (Order a (PrimState m))
delete :: PrimMonad m => Order a (PrimState m) -> m ()
logU :: Int
loglogU :: Int
deltaU :: Key
new :: PrimMonad m => a -> m (Order a (PrimState m))
keys :: PrimMonad m => Order a (PrimState m) -> m (Key, Key)
instance GHC.Classes.Eq (Data.Struct.Internal.Order.Order a s)
instance Data.Struct.Internal.Struct (Data.Struct.Internal.Order.Order a)


module Data.Struct.Order

-- | This structure maintains an order-maintenance structure as two levels
--   of list-labeling.
--   
--   The upper labeling scheme holds <tt>(n / log w)</tt> elements in a
--   universe of size <tt>w^2</tt>, operating in O(log n) amortized time
--   per operation.
--   
--   It is accelerated by an indirection structure where each smaller
--   universe holds O(log w) elements, with total label space <tt>2^log w =
--   w</tt> and O(1) expected update cost, so we can charge rebuilds to the
--   upper structure to the lower structure.
--   
--   Every insert to the upper structure is amortized across <tt>O(log
--   w)</tt> operations below.
--   
--   This means that inserts are O(1) amortized, while comparisons remain
--   O(1) worst-case.
data Order a s
new :: PrimMonad m => a -> m (Order a (PrimState m))
value :: Field (Order a) a
insertAfter :: PrimMonad m => Order a (PrimState m) -> a -> m (Order a (PrimState m))
delete :: PrimMonad m => Order a (PrimState m) -> m ()

module Data.Struct.TH

-- | Generate allocators, slots, fields, unboxed fields, Eq instances, and
--   Struct instances for the given "data types".
--   
--   Inputs are expected to be "data types" parameterized by a state type.
--   Strict fields are considered to be slots, Non-strict fields are
--   considered to be boxed types, Unpacked fields are considered to be
--   unboxed primitives.
--   
--   The data type should use record syntax and have a single constructor.
--   The field names will be used to generate slot, field, and unboxedField
--   values of the same name.
--   
--   An allocator for the struct is generated by prefixing "alloc" to the
--   data type name.
makeStruct :: DecsQ -> DecsQ
instance GHC.Show.Show Data.Struct.TH.StructRep
instance GHC.Show.Show Data.Struct.TH.Member
instance GHC.Show.Show Data.Struct.TH.Representation


module Data.Struct.Internal.LinkCut

-- | Amortized Link-Cut trees via splay trees based on Tarjan's little
--   book.
--   
--   These support O(log n) operations for a lot of stuff.
--   
--   The parameter <tt>a</tt> is an arbitrary user-supplied monoid that
--   will be summarized along the path to the root of the tree.
--   
--   In this example the choice of <a>Monoid</a> is <a>String</a>, so we
--   can get a textual description of the path to the root.
--   
--   <pre>
--   &gt;&gt;&gt; x &lt;- new "x"
--   
--   &gt;&gt;&gt; y &lt;- new "y"
--   
--   &gt;&gt;&gt; link x y -- now x is a child of y
--   
--   &gt;&gt;&gt; x == y
--   False
--   
--   &gt;&gt;&gt; connected x y
--   True
--   
--   &gt;&gt;&gt; z &lt;- new "z"
--   
--   &gt;&gt;&gt; link z x -- now z is a child of y
--   
--   &gt;&gt;&gt; (y ==) &lt;$&gt; root z
--   True
--   
--   &gt;&gt;&gt; cost z
--   "yxz"
--   
--   &gt;&gt;&gt; w &lt;- new "w"
--   
--   &gt;&gt;&gt; u &lt;- new "u"
--   
--   &gt;&gt;&gt; v &lt;- new "v"
--   
--   &gt;&gt;&gt; link u w
--   
--   &gt;&gt;&gt; link v z
--   
--   &gt;&gt;&gt; link w z
--   
--   &gt;&gt;&gt; cost u
--   "yxzwu"
--   
--   &gt;&gt;&gt; (y ==) &lt;$&gt; root v
--   True
--   
--   &gt;&gt;&gt; connected x v
--   True
--   
--   &gt;&gt;&gt; cut z
--   </pre>
--   
--   <pre>
--       y
--      x          z    y
--     z    ==&gt;   w v  x
--    w v        u
--   u
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; connected x v
--   False
--   
--   &gt;&gt;&gt; cost u
--   "zwu"
--   
--   &gt;&gt;&gt; (z ==) &lt;$&gt; root v
--   True
--   </pre>
newtype LinkCut a_akGK s_akGL
LinkCut :: (Object s_akGL) -> LinkCut a_akGK s_akGL
allocLinkCut :: forall a_akGK. forall m_akGU. PrimMonad m_akGU => m_akGU (LinkCut a_akGK (PrimState m_akGU))
newLinkCut :: forall a_akGK. forall m_akGT. PrimMonad m_akGT => LinkCut a_akGK (PrimState m_akGT) -> LinkCut a_akGK (PrimState m_akGT) -> LinkCut a_akGK (PrimState m_akGT) -> LinkCut a_akGK (PrimState m_akGT) -> a_akGK -> a_akGK -> m_akGT (LinkCut a_akGK (PrimState m_akGT))
summary :: forall a_akGK. Field (LinkCut a_akGK) a_akGK
value :: forall a_akGK. Field (LinkCut a_akGK) a_akGK
right :: forall a_akGK. Slot (LinkCut a_akGK) (LinkCut a_akGK)
left :: forall a_akGK. Slot (LinkCut a_akGK) (LinkCut a_akGK)
parent :: forall a_akGK. Slot (LinkCut a_akGK) (LinkCut a_akGK)
path :: forall a_akGK. Slot (LinkCut a_akGK) (LinkCut a_akGK)

-- | O(1). Allocate a new link-cut tree with a given monoidal summary.
new :: PrimMonad m => a -> m (LinkCut a (PrimState m))

-- | O(log n). <tt><a>cut</a> v</tt> removes the linkage between <tt>v</tt>
--   upwards to whatever tree it was in, making <tt>v</tt> a root node.
--   
--   Repeated calls on the same value without intermediate accesses are
--   O(1).
cut :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m ()

-- | O(log n). <tt><a>link</a> v w</tt> inserts <tt>v</tt> which must be
--   the root of a tree in as a child of <tt>w</tt>. <tt>v</tt> and
--   <tt>w</tt> must not be <a>connected</a>.
link :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m ()

-- | O(log n). <tt><a>connected</a> v w</tt> determines if <tt>v</tt> and
--   <tt>w</tt> inhabit the same tree.
connected :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m Bool

-- | O(log n). <tt><a>cost</a> v</tt> computes the root-to-leaf path cost
--   of <tt>v</tt> under whatever <a>Monoid</a> was built into the tree.
--   
--   Repeated calls on the same value without intermediate accesses are
--   O(1).
cost :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m a

-- | O(log n). Find the root of a tree.
--   
--   Repeated calls on the same value without intermediate accesses are
--   O(1).
root :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))

-- | O(log n). Move upward one level.
--   
--   This will return <a>Nil</a> if the parent is not available.
--   
--   Note: Repeated calls on the same value without intermediate accesses
--   are O(1).
up :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))

-- | O(1)
summarize :: Monoid a => LinkCut a s -> ST s a

-- | O(log n)
access :: Monoid a => LinkCut a s -> ST s ()

-- | O(log n). Splay within an auxiliary tree
splay :: Monoid a => LinkCut a s -> ST s ()
instance Data.Struct.Internal.Struct (Data.Struct.Internal.LinkCut.LinkCut a)
instance GHC.Classes.Eq (Data.Struct.Internal.LinkCut.LinkCut a s)


module Data.Struct.LinkCut

-- | Amortized Link-Cut trees via splay trees based on Tarjan's little
--   book.
--   
--   These support O(log n) operations for a lot of stuff.
--   
--   The parameter <tt>a</tt> is an arbitrary user-supplied monoid that
--   will be summarized along the path to the root of the tree.
--   
--   In this example the choice of <a>Monoid</a> is <a>String</a>, so we
--   can get a textual description of the path to the root.
--   
--   <pre>
--   &gt;&gt;&gt; x &lt;- new "x"
--   
--   &gt;&gt;&gt; y &lt;- new "y"
--   
--   &gt;&gt;&gt; link x y -- now x is a child of y
--   
--   &gt;&gt;&gt; x == y
--   False
--   
--   &gt;&gt;&gt; connected x y
--   True
--   
--   &gt;&gt;&gt; z &lt;- new "z"
--   
--   &gt;&gt;&gt; link z x -- now z is a child of y
--   
--   &gt;&gt;&gt; (y ==) &lt;$&gt; root z
--   True
--   
--   &gt;&gt;&gt; cost z
--   "yxz"
--   
--   &gt;&gt;&gt; w &lt;- new "w"
--   
--   &gt;&gt;&gt; u &lt;- new "u"
--   
--   &gt;&gt;&gt; v &lt;- new "v"
--   
--   &gt;&gt;&gt; link u w
--   
--   &gt;&gt;&gt; link v z
--   
--   &gt;&gt;&gt; link w z
--   
--   &gt;&gt;&gt; cost u
--   "yxzwu"
--   
--   &gt;&gt;&gt; (y ==) &lt;$&gt; root v
--   True
--   
--   &gt;&gt;&gt; connected x v
--   True
--   
--   &gt;&gt;&gt; cut z
--   </pre>
--   
--   <pre>
--       y
--      x          z    y
--     z    ==&gt;   w v  x
--    w v        u
--   u
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; connected x v
--   False
--   
--   &gt;&gt;&gt; cost u
--   "zwu"
--   
--   &gt;&gt;&gt; (z ==) &lt;$&gt; root v
--   True
--   </pre>
data LinkCut a_akGK s_akGL

-- | O(1). Allocate a new link-cut tree with a given monoidal summary.
new :: PrimMonad m => a -> m (LinkCut a (PrimState m))

-- | O(log n). <tt><a>link</a> v w</tt> inserts <tt>v</tt> which must be
--   the root of a tree in as a child of <tt>w</tt>. <tt>v</tt> and
--   <tt>w</tt> must not be <a>connected</a>.
link :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m ()

-- | O(log n). <tt><a>cut</a> v</tt> removes the linkage between <tt>v</tt>
--   upwards to whatever tree it was in, making <tt>v</tt> a root node.
--   
--   Repeated calls on the same value without intermediate accesses are
--   O(1).
cut :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m ()

-- | O(log n). Find the root of a tree.
--   
--   Repeated calls on the same value without intermediate accesses are
--   O(1).
root :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))

-- | O(log n). <tt><a>cost</a> v</tt> computes the root-to-leaf path cost
--   of <tt>v</tt> under whatever <a>Monoid</a> was built into the tree.
--   
--   Repeated calls on the same value without intermediate accesses are
--   O(1).
cost :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m a

-- | O(log n). Find the parent of a node.
--   
--   This will return <tt>Nil</tt> if the parent does not exist.
--   
--   Repeated calls on the same value without intermediate accesses are
--   O(1).
parent :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))

-- | O(log n). <tt><a>connected</a> v w</tt> determines if <tt>v</tt> and
--   <tt>w</tt> inhabit the same tree.
connected :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m Bool
