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

[PSeitz]

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.

[leonardo]

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

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

[PSeitz]

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?

[stebalien]

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):

Collection Traits, Take 2

Before we finalize everything forever, I figured we should quickly reflect on what we want to collection traits to look like. So here's a quick sketch of the minimal API I think we should provide. Some notable points: Everything is associated types; nothing should plausibly be a collection of more than one type at once. Very little inherits from anything else. This might be unergonomic (wrangling that foo is a Stack and Seq with the same Elem type). Not sure if we should mandate that e.g. all…

[system]

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