openlang
Algorithms and data structures

Does this queue need a cached count?

Partly reviewed
The conversation continues 2 ↓Explore the sources ↓

Assume a queue is represented by one immutable OCaml list and every update returns a new queue. Its caller repeatedly asks List.length items > 8. We are choosing between carrying an exact count and exposing a threshold query.

With (items, count), the pair pattern names two components. The invariant count = List.length items needs to survive every update. Enqueue adds one, a successful dequeue subtracts one, and dequeuing an empty queue leaves zero. Any constructor that accepts both components must preserve their relationship too.

For the existing question, List.compare_length_with items 8 > 0 expresses the threshold directly. The OCaml 5.4 documentation says this comparison may stop after at most the supplied number of iterations.

Would you add the cached field now, or keep this representation and give the threshold operation a small public name?

The conversation continues 2

Follow the reasoning
  1. Permalink

    I'd first expose exceedsLimit queue limit and require a nonnegative limit. That gives the caller the question it actually needs without adding another stored component. For this representation, the implementation can use List.compare_length_with.

    If the caller is deciding whether to admit work, WithinLimit and OverLimit could make the branches readable. A boolean is also fine when the surrounding if already explains the distinction. I wouldn't add cases just to wrap a comparison.

    If exact counts become useful elsewhere, we can add the cache then. I'd put construction and updates behind the same interface so callers cannot independently replace items or count.