lean-ja / lean-ja/lean-by-example
`TreeSet` を紹介する
Open
Nobody has claimed this yet.
データ型
- Dominant language
- Lean
- Stars
- 188
- Forks
- 15
- Avg merge
- 9h 8m
- Merged PRs (30d)
- 6
Description
/--
Tree sets.
A tree set stores elements of a certain type in a certain order. It depends on a comparator function
that defines an ordering on the keys and provides efficient order-dependent queries, such as
retrieval of the minimum or maximum.
To ensure that the operations behave as expected, the comparator function `cmp` should satisfy
certain laws that ensure a consistent ordering:
* If `a` is less than (or equal) to `b`, then `b` is greater than (or equal) to `a`
and vice versa (see the `OrientedCmp` typeclass).
* If `a` is less than or equal to `b` and `b` is, in turn, less than or equal to `c`, then `a`
is less than or equal to `c` (see the `TransCmp` typeclass).
Keys for which `cmp a b = Ordering.eq` are considered the same, i.e., there can be only one of them
be contained in a single tree set at the same time.
To avoid expensive copies, users should make sure that the tree set is used linearly.
Internally, the tree sets are represented as size-bounded trees, a type of self-balancing binary
search tree with efficient order statistic lookups.
For use in proofs, the type `Std.ExtTreeSet` of extensional tree sets should be preferred. This
type comes with several extensionality lemmas and provides the same functions but requires a
`TransCmp` instance to work with.
These tree sets contain a bundled well-formedness invariant, which means that they cannot
be used in nested inductive types. For these use cases, `Std.TreeSet.Raw` and
`Std.TreeSet.Raw.WF` unbundle the invariant from the tree set. When in doubt, prefer
`TreeSet` over `TreeSet.Raw`.
-/
structure TreeSet (α : Type u) (cmp : α → α → Ordering := by exact compare) where
/-- Internal implementation detail of the tree map. -/
inner : TreeMap α Unit cmp
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Use the supplied TreeSet documentation as the starting point. The issue names no target file or test, so first locate where TreeSet is documented in the repository; the work is complete when this introduction is added in the appropriate place.
Written by the indexing model from the issue text.
Assessment
- Domain
- documentation
- Issue type
- Documentation
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 50/100