Safe Haskell	None
Language	GHC2021

Test.Credit

Contents

Common Time-Complexity Functions
Execution Traces for Testing
Running Data Structures on Execution Traces
Testing Data Structures on Execution Traces

Synopsis

data Size
logstar :: Size -> Credit
log2 :: Size -> Credit
linear :: Size -> Credit
data Strategy
- = Path
- | Bloom
- | Pennant
- | Random
genExecutionTrace :: Arbitrary op => Strategy -> Gen (Tree op)
class (Arbitrary op, Show op) => DataStructure (t :: (Type -> Type) -> Type) op | t -> op where
- cost :: Size -> op -> Credit
- create :: MonadLazy m => m (t m)
- perform :: MonadInherit m => Size -> t m -> op -> m (Size, t m)
runTree :: forall (t :: (Type -> Type) -> Type) op. DataStructure t op => Tree op -> Either Error ()
runTreeTrace :: forall (t :: (Type -> Type) -> Type) op. (MemoryStructure t, DataStructure t op) => Tree op -> String
checkCredits :: forall (t :: (Type -> Type) -> Type) op. DataStructure t op => Strategy -> Property
checkCreditsTrace :: forall (t :: (Type -> Type) -> Type) op. (MemoryStructure t, DataStructure t op) => Strategy -> Property

Common Time-Complexity Functions

data Size Source #

Instances

Instances details

Enum Size Source #
Instance details Defined in Test.Credit Methods succ :: Size -> Size # pred :: Size -> Size # toEnum :: Int -> Size # fromEnum :: Size -> Int # enumFrom :: Size -> [Size] # enumFromThen :: Size -> Size -> [Size] # enumFromTo :: Size -> Size -> [Size] # enumFromThenTo :: Size -> Size -> Size -> [Size] #
Num Size Source #
Instance details Defined in Test.Credit Methods (+) :: Size -> Size -> Size # (-) :: Size -> Size -> Size # (*) :: Size -> Size -> Size # negate :: Size -> Size # abs :: Size -> Size # signum :: Size -> Size # fromInteger :: Integer -> Size #
Integral Size Source #
Instance details Defined in Test.Credit Methods quot :: Size -> Size -> Size # rem :: Size -> Size -> Size # div :: Size -> Size -> Size # mod :: Size -> Size -> Size # quotRem :: Size -> Size -> (Size, Size) # divMod :: Size -> Size -> (Size, Size) # toInteger :: Size -> Integer #
Real Size Source #
Instance details Defined in Test.Credit Methods toRational :: Size -> Rational #
Show Size Source #
Instance details Defined in Test.Credit Methods showsPrec :: Int -> Size -> ShowS # show :: Size -> String # showList :: [Size] -> ShowS #
Eq Size Source #
Instance details Defined in Test.Credit Methods (==) :: Size -> Size -> Bool # (/=) :: Size -> Size -> Bool #
Ord Size Source #
Instance details Defined in Test.Credit Methods compare :: Size -> Size -> Ordering # (<) :: Size -> Size -> Bool # (<=) :: Size -> Size -> Bool # (>) :: Size -> Size -> Bool # (>=) :: Size -> Size -> Bool # max :: Size -> Size -> Size # min :: Size -> Size -> Size #
Pretty Size Source #
Instance details Defined in Test.Credit Methods pretty :: Size -> Doc ann # prettyList :: [Size] -> Doc ann #
Monad m => MemoryCell m Size Source #
Instance details Defined in Test.Credit Methods prettyCell :: Size -> m Memory Source #

logstar :: Size -> Credit Source #

log2 :: Size -> Credit Source #

linear :: Size -> Credit Source #

Execution Traces for Testing

data Strategy Source #

Constructors

Path
Bloom
Pennant
Random

Instances

Instances details

Show Strategy Source #
Instance details Defined in Test.Credit Methods showsPrec :: Int -> Strategy -> ShowS # show :: Strategy -> String # showList :: [Strategy] -> ShowS #
Eq Strategy Source #
Instance details Defined in Test.Credit Methods (==) :: Strategy -> Strategy -> Bool # (/=) :: Strategy -> Strategy -> Bool #
Ord Strategy Source #
Instance details Defined in Test.Credit Methods compare :: Strategy -> Strategy -> Ordering # (<) :: Strategy -> Strategy -> Bool # (<=) :: Strategy -> Strategy -> Bool # (>) :: Strategy -> Strategy -> Bool # (>=) :: Strategy -> Strategy -> Bool # max :: Strategy -> Strategy -> Strategy # min :: Strategy -> Strategy -> Strategy #

genExecutionTrace :: Arbitrary op => Strategy -> Gen (Tree op) Source #

Running Data Structures on Execution Traces

class (Arbitrary op, Show op) => DataStructure (t :: (Type -> Type) -> Type) op | t -> op where Source #

Methods

cost :: Size -> op -> Credit Source #

Given a size and an operation, return the cost of the operation. This function can not inspect the internal state of the data structure.

create :: MonadLazy m => m (t m) Source #

create a new instance of the data structure. We allow the computation to be lazy, since lazy data structures often contain thunks even if they contain no elements. The create data structure is assumed to have size zero.

perform :: MonadInherit m => Size -> t m -> op -> m (Size, t m) Source #

Given a data structure, its size, and an operation, return the updated size and data structure. We allow the size to depend on the internal state of the data structure, since some operations, like insertions into a binary search tree, might return different sizes depending on whether a new element is already present.

Instances

Instances details

(Arbitrary a, BoundedDeque q, Show a) => DataStructure (BD q a) (DequeOp a) Source #
Instance details Defined in Test.Credit.Deque.Base Methods cost :: Size -> DequeOp a -> Credit Source # create :: MonadLazy m => m (BD q a m) Source # perform :: MonadInherit m => Size -> BD q a m -> DequeOp a -> m (Size, BD q a m) Source #
(Arbitrary a, BoundedDeque q, Show a) => DataStructure (D q a) (DequeOp a) Source #
Instance details Defined in Test.Credit.Deque.Base Methods cost :: Size -> DequeOp a -> Credit Source # create :: MonadLazy m => m (D q a m) Source # perform :: MonadInherit m => Size -> D q a m -> DequeOp a -> m (Size, D q a m) Source #
(Arbitrary a, Ord a, BoundedHeap h, Show a) => DataStructure (BH h a) (HeapOp a) Source #
Instance details Defined in Test.Credit.Heap.Base Methods cost :: Size -> HeapOp a -> Credit Source # create :: MonadLazy m => m (BH h a m) Source # perform :: MonadInherit m => Size -> BH h a m -> HeapOp a -> m (Size, BH h a m) Source #
(Arbitrary a, Ord a, BoundedHeap h, Show a) => DataStructure (H h a) (HeapOp a) Source #
Instance details Defined in Test.Credit.Heap.Base Methods cost :: Size -> HeapOp a -> Credit Source # create :: MonadLazy m => m (H h a m) Source # perform :: MonadInherit m => Size -> H h a m -> HeapOp a -> m (Size, H h a m) Source #
(Arbitrary a, BoundedQueue q, Show a) => DataStructure (Q q a) (QueueOp a) Source #
Instance details Defined in Test.Credit.Queue.Base Methods cost :: Size -> QueueOp a -> Credit Source # create :: MonadLazy m => m (Q q a m) Source # perform :: MonadInherit m => Size -> Q q a m -> QueueOp a -> m (Size, Q q a m) Source #
(Arbitrary a, BoundedRandomAccess q, Show a) => DataStructure (RA q a) (RandomAccessOp a) Source #
Instance details Defined in Test.Credit.RandomAccess.Base Methods cost :: Size -> RandomAccessOp a -> Credit Source # create :: MonadLazy m => m (RA q a m) Source # perform :: MonadInherit m => Size -> RA q a m -> RandomAccessOp a -> m (Size, RA q a m) Source #
(Arbitrary a, Ord a, BoundedSortable q, Show a) => DataStructure (S q a) (SortableOp a) Source #
Instance details Defined in Test.Credit.Sortable.Base Methods cost :: Size -> SortableOp a -> Credit Source # create :: MonadLazy m => m (S q a m) Source # perform :: MonadInherit m => Size -> S q a m -> SortableOp a -> m (Size, S q a m) Source #

runTree :: forall (t :: (Type -> Type) -> Type) op. DataStructure t op => Tree op -> Either Error () Source #

Evaluate an execution trace of operations on the given data structure using the credit monad. Returns either an error or unit if the evaluation succeeded.

runTreeTrace :: forall (t :: (Type -> Type) -> Type) op. (MemoryStructure t, DataStructure t op) => Tree op -> String Source #

Evaluate an execution trace of operations on the given data structure using the credit monad. Returns a pretty-printed string of the execution trace annotated with the internal state of the data structure at each step.

Testing Data Structures on Execution Traces

checkCredits :: forall (t :: (Type -> Type) -> Type) op. DataStructure t op => Strategy -> Property Source #

Test the given data structure in the credit monad using the given strategy. This property only reports if evaluation succeeded or not.

checkCreditsTrace :: forall (t :: (Type -> Type) -> Type) op. (MemoryStructure t, DataStructure t op) => Strategy -> Property Source #

Test the given data structure in the credit monad using the given strategy. If evaluation fails, this property prints the execution trace annotated with the internal state of the data structure at each step.