Checking Empty child of Internal nodes

[kgeorgiy]

Documentation states that Empty allowed only as a root of the tree. Both performance and functions (e. g. binarySetOpWithKey) 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) 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.

[isturdy]

I believe that binarySetOpWithKey will throw an error if it encounters Empty anywhere but at the top level; one can thus use it to check (as Criterion handles exceptions as failed tests). I, at least, would prefer a dedicated validation function to adding size/complexity to an API function (even if it does not hurt speed, it would cause code bloat in all callers, and could conceivably bump the function over GHC's inlining threshold).

[kgeorgiy]

You are right! difference m m should throw error if an unexpected Empty is encountered.

I'am not aware about specific features of GHC inlining, but AFAIU toList.go cannot be inlined due to recursive (not tail-recursive, specifically) nature. In this case, the following implementation should me a bit more efficient due to inlainability of the top.

toList :: CritBit k v -> [(k, v)]
toList (CritBit root) = top root
  where
    top Empty = []
    top node = go node []

    go (Internal l r _ _) next = go l (go r next)
    go (Leaf k v) next         = (k,v) : next
    go Empty next              = error "CritBit: Empty child of Internal node"

[kgeorgiy]

Pardon, for better performance the List.top should be defined as

    top Empty = []
    top (Internal l r _ _) next = go l (go r next)
    top (Leaf k v) next         = (k,v) : next