haskell / haskell/critbit

Checking `Empty` child of `Internal` nodes

Open
#59 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
141
Forks
40
PR merge metrics
No merged PRs in 30d

Description

[Documentation](https://github.com/bos/critbit/blob/master/Data/CritBit/Types/Internal.hs#L46) states that `Empty` allowed only as a root of the tree. Both performance and functions (e. g. [binarySetOpWithKey](https://github.com/bos/critbit/blob/master/Data/CritBit/Tree.hs#L605)) depends on this invariant. But, now it is not checked by tests at all.

Unfortunately, there is no way to write such check function using public API only.

AFAIU there are two ways to solve this problem:
1. Make one of the API functions (e.g. [toList](https://github.com/bos/critbit/blob/master/Data/CritBit/Types/Internal.hs#L128)) to check this. This check will cost just a one call on the root tree.
2. Provide special check function in the API.

I think first variant is better.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.