Implement property-based tests using `hedgehog` - Githubissues

kowainik / treap

:leaves: :deciduous_tree: :fallen_leaf: Efficient implementation of the implicit treap data structure

Mozilla Public License 2.0

63 stars 1 forks source link

Implement property-based tests using `hedgehog` #24

Open chshersh opened 5 years ago

chshersh commented 5 years ago

This is a meta-issue to collect all possible laws for the Treap data structure:

Semigroup/Monoid laws

[x] Associativity
[x] Left/Right identity

Measured

[ ] measure (one x) ≡ x

IsList

[ ] Roundtrip IsList: toList . fromList ≡ id

Modifications

[ ] at i . insert i x ≡ Just x
[ ] delete i . insert i x ≡ id
[ ] size (insert i x t) ≡ size t + 1

Cuts

[ ] uncurry merge . splitAt i ≡ id
[ ] size (merge l r) ≡ size l + size r
[ ] Monoid homomorphism: measure (merge l r) ≡ measure l <> measure r
[ ] splitAt i t ≡ (take i t, drop i t)