Is it possible to implement `SortedMap` and `SortedSet` the same way? about fsharp-hashcollections HOT 2 CLOSED

Depends what you mean by the same way.

The short answer is - no.

The long answer is - if your hash/partition key is an integer that is sorted with the data then the collection with some minor tweaks to the library it could possibly give the appearance of a mostly sorted structure bar any hash clashes. The classic example of this of course is int32 where hash int32Var = int32Var.

This is because under the hood the structure naturally sorts itself by hash. It would not be possible by using standard comparison (-1, 0, or 1) using this method. I haven't found the need to do this to date however; and it should not be behavior that library consumers rely upon. Internals of the library are subject to change if there is a way to make it even faster; the algorithm is an implementation detail.

Fundamentally comparison based sorted maps/sets, especially when immutable and share data, often exhibit worse performance characteristics for a number of reasons both in retrieval and insertion by a significant factor.

from fsharp-hashcollections.

Closing this issue as the question has been answered.

from fsharp-hashcollections.