kowainik / kowainik/treap

Implement property-based tests using `hedgehog`

Open
#24 0 comments 0 reactions 0 assignees View on GitHub
good first issue Hacktoberfest question tests
Dominant language
Haskell
Stars
63
Forks
1
PR merge metrics
No merged PRs in 30d

Description

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)`

Contributor guide

Open the contributing guide

Research direction

Start by locating the Treap implementation and its existing test entry point, then review the unchecked laws listed in this issue. Use Hedgehog to cover the measured, IsList, modification, and cut laws, and consider the work done when each listed property is implemented and passes.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
data
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.