[pre-rfc] bind binary_search to traits instead of slice

language design
1

Summary

binary_search is only available for slices. Sometimes the data is not convertible to a slice, but traits could be implemented.

Motivation

It would be nice to enable core features like the binary_search algorithm on the data by just implementing the required traits.

Detailed design

The traits for binary_search would need random access to the elements (core::ops::Index) and the length (is there a trait?)

Currently a custom binary search implementation would be required, if the data structure is not convertible to a slice.

Like mentioned below, these could be grouped like in D, into something like a SortedRange Trait.

Alternatives

This does not necessarily need to be part of the rust core. It could also be moved to a separate crate. Although it is nice to have reliable methods in the core libraries.

2

You also need the elements to be sorted. See the SortedRange in D language.

3

Yes, but from the language perspective there is probably not much we could do about that, except bundle methods like binary_search into something like a SortedRange trait?

4

IIRC, the main thing holding stuff like this back are generalized collection traits and the main reason we don't have those is the lack of HKT.

See the following for a relevent discussion (it doesn't explicitly mention binary search but that would probably be added to the SortedSet trait):

5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.