-- 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.8
module Data.Struct.Internal
data NullPointerException
NullPointerException :: NullPointerException
-- | A Dict reifies an instance of the constraint p 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 PrimMonad dictionary.
st :: PrimMonad m => ST (PrimState m) a -> m a
-- | An instance for Struct t is a witness to the
-- machine-level equivalence of t and Object.
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
pattern Struct :: Struct t => () => SmallMutableArray# s Any -> t s
-- | Allocate a structure made out of n 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
-- Null type instead of a mutable array. This hack relies on GHC
-- reusing the same Null 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 Nil.
--
--
-- >>> isNil (Nil :: Object (PrimState IO))
-- True
--
-- >>> o <- alloc 1 :: IO (Object (PrimState IO))
--
-- >>> isNil o
-- False
--
isNil :: Struct t => t s -> Bool
-- | Truly imperative.
pattern Nil :: Struct t => () => t s
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 Slot 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 Slot at the given position in a Struct
slot :: Int -> Slot s t
-- | Get the value from a Slot
get :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> m (y (PrimState m))
-- | Set the value of a Slot
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 Field 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 unboxedField. 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.Type.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 Struct t is a witness to the
-- machine-level equivalence of t and Object.
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 n slots. Initialize the
-- structure before proceeding!
alloc :: (PrimMonad m, Struct t) => Int -> m (t (PrimState m))
-- | Truly imperative.
pattern Nil :: Struct t => () => t s
-- | Predicate to check if a struct is Nil.
--
--
-- >>> isNil (Nil :: Object (PrimState IO))
-- True
--
-- >>> o <- alloc 1 :: IO (Object (PrimState IO))
--
-- >>> isNil o
-- False
--
isNil :: Struct t => t s -> Bool
data NullPointerException
NullPointerException :: NullPointerException
-- | A Slot is a reference to another unboxed mutable object.
data Slot x y
-- | The Slot at the given position in a Struct
slot :: Int -> Slot s t
-- | Get the value from a Slot
get :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> m (y (PrimState m))
-- | Set the value of a Slot
set :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> y (PrimState m) -> m ()
-- | A Field 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.
--
--
-- >>> x <- makeLabel 0 Nil Nil
--
-- >>> isNil x
-- False
--
-- >>> n <- get next x
--
-- >>> isNil n
-- True
--
-- >>> p <- get prev x
--
-- >>> isNil p
-- True
--
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 (n / log w) elements in a
-- universe of size w^2, 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 2^log w =
-- w 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 O(log
-- w) 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 (n / log w) elements in a
-- universe of size w^2, 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 2^log w =
-- w 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 O(log
-- w) 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.Representation
instance GHC.Show.Show Data.Struct.TH.Member
instance GHC.Show.Show Data.Struct.TH.StructRep
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 a 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 Monoid is String, so we
-- can get a textual description of the path to the root.
--
--
-- >>> x <- new "x"
--
-- >>> y <- new "y"
--
-- >>> link x y -- now x is a child of y
--
-- >>> x == y
-- False
--
-- >>> connected x y
-- True
--
-- >>> z <- new "z"
--
-- >>> link z x -- now z is a child of y
--
-- >>> (y ==) <$> root z
-- True
--
-- >>> cost z
-- "yxz"
--
-- >>> w <- new "w"
--
-- >>> u <- new "u"
--
-- >>> v <- new "v"
--
-- >>> link u w
--
-- >>> link v z
--
-- >>> link w z
--
-- >>> cost u
-- "yxzwu"
--
-- >>> (y ==) <$> root v
-- True
--
-- >>> connected x v
-- True
--
-- >>> cut z
--
--
--
-- y
-- x z y
-- z ==> w v x
-- w v u
-- u
--
--
--
-- >>> connected x v
-- False
--
-- >>> cost u
-- "zwu"
--
-- >>> (z ==) <$> root v
-- True
--
newtype LinkCut a_aeLL s_aeLM
LinkCut :: Object s_aeLM -> LinkCut a_aeLL s_aeLM
allocLinkCut :: forall a_aeLL. forall m_aeLV. PrimMonad m_aeLV => m_aeLV (LinkCut a_aeLL (PrimState m_aeLV))
newLinkCut :: forall a_aeLL. forall m_aeLU. PrimMonad m_aeLU => LinkCut a_aeLL (PrimState m_aeLU) -> LinkCut a_aeLL (PrimState m_aeLU) -> LinkCut a_aeLL (PrimState m_aeLU) -> LinkCut a_aeLL (PrimState m_aeLU) -> a_aeLL -> a_aeLL -> m_aeLU (LinkCut a_aeLL (PrimState m_aeLU))
summary :: forall a_aeLL. Field (LinkCut a_aeLL) a_aeLL
value :: forall a_aeLL. Field (LinkCut a_aeLL) a_aeLL
right :: forall a_aeLL. Slot (LinkCut a_aeLL) (LinkCut a_aeLL)
left :: forall a_aeLL. Slot (LinkCut a_aeLL) (LinkCut a_aeLL)
parent :: forall a_aeLL. Slot (LinkCut a_aeLL) (LinkCut a_aeLL)
path :: forall a_aeLL. Slot (LinkCut a_aeLL) (LinkCut a_aeLL)
-- | 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). cut v removes the linkage between v
-- upwards to whatever tree it was in, making v 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). link v w inserts v which must be
-- the root of a tree in as a child of w. v and
-- w must not be connected.
link :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m ()
-- | O(log n). connected v w determines if v and
-- w inhabit the same tree.
connected :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m Bool
-- | O(log n). cost v computes the root-to-leaf path cost
-- of v under whatever Monoid 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 Nil 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 a 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 Monoid is String, so we
-- can get a textual description of the path to the root.
--
--
-- >>> x <- new "x"
--
-- >>> y <- new "y"
--
-- >>> link x y -- now x is a child of y
--
-- >>> x == y
-- False
--
-- >>> connected x y
-- True
--
-- >>> z <- new "z"
--
-- >>> link z x -- now z is a child of y
--
-- >>> (y ==) <$> root z
-- True
--
-- >>> cost z
-- "yxz"
--
-- >>> w <- new "w"
--
-- >>> u <- new "u"
--
-- >>> v <- new "v"
--
-- >>> link u w
--
-- >>> link v z
--
-- >>> link w z
--
-- >>> cost u
-- "yxzwu"
--
-- >>> (y ==) <$> root v
-- True
--
-- >>> connected x v
-- True
--
-- >>> cut z
--
--
--
-- y
-- x z y
-- z ==> w v x
-- w v u
-- u
--
--
--
-- >>> connected x v
-- False
--
-- >>> cost u
-- "zwu"
--
-- >>> (z ==) <$> root v
-- True
--
data LinkCut a_aeLL s_aeLM
-- | 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). link v w inserts v which must be
-- the root of a tree in as a child of w. v and
-- w must not be connected.
link :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m ()
-- | O(log n). cut v removes the linkage between v
-- upwards to whatever tree it was in, making v 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). cost v computes the root-to-leaf path cost
-- of v under whatever Monoid 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 Nil 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). connected v w determines if v and
-- w inhabit the same tree.
connected :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m Bool