Do sizes matter in CCBV?

[favonia]

I feel there might be two incompatible design principles in the current CCBV module:

1. CCBV.t is a collection of true bits that resizes like Hashtbl.
2. CCBV.t is a vector of bits without automatic resizing.

I think either is fine, and to be honest I don't have a preference, but mixing them up could eventually lead to confusion. In particular, resizing in set, flip, ... and the interface of the current empty makes sense under the first principle, while the new equality only makes sense under the second principle. It is possible that by setting and resetting some high bit you would end up with a different vector due to resizing, and I feel this could be confusing. It seems to me the current design is closer to the first principle. If so, perhaps it makes more sense to do implicit resizing in equal (by checking whether all the extra integers are zeros) and perhaps add hash and other conversion functions that would ignore all the padding zeros.

As a comparison, the Bitv library sticks to the second principle and does not automatically resize vectors; you can specify the length in of_list, there's no empty that serves as the "polymorphic empty collection", and bitwise operators are only defined for vectors of the same length. Arguably this is more efficient but I doubt this could be a bottleneck.

[c-cube]

It's a bit conflicting indeed. Mostly it's a bitvector with explicit resizing, except for get/set/reset.

You make a good point about the equality part, maybe it should just compare set bits. It's not released yet so we can break it still :-)

[favonia]

Here is my preliminary assessment of the functions in the current library:

Category 1

These items seem to be more compatible with automatic resizing (collections of true bits).

• empty: otherwise, the length should be specified, or simply be removed in favor of create.
• is_empty: otherwise, it should probably be named all_zeros, and all_ones should probably be added.
• set, get, reset, flip: otherwise, out-of-range access should lead to errors.
• union{,_into}, inter{,_into}, diff{,_into}: otherwise, there should be some length restrictions.

Category 2

These items seem to be more compatible with no resizing (imperative vectors of bits). There is no strong preference of true over false from this perspective.

• create: otherwise, only create ~size true makes sense, as you can use empty for create ~size false.
• length: otherwise, the vector could be resized at any time.
• resize: otherwise, this should be a no-op or maybe truncate.
• clear: otherwise, we can just shrink the vector to nil.
• iter, negate{,_self}: otherwise, the leading zeros should not matter.

Category 1+2

These items seem to be equally compatible with both treatments:

• copy
• cardinal: maybe it should probably be named count_ones from the second perspective...
• capacity: this in my opinion is some acceptable extra information even from the "collection" point of view
• iter_true
• to_list, of_list, to_iter, of_iter
• first, first_exn
• filter
• select, selecti

[favonia]

Another idea---how about CCSmallIntSet (or something like that) with resizing and CCBV (or another name for backward compatibility) without resizing?

[c-cube]

I'd rather keep CCBV as the mutable, auto-resizing version, and make more functions independent of size (like equal). I don't think it's useful to have both auto-resizing and non-auto-resizing.

[c-cube]

referenced in #375