Proposal: containers: add indexing operations for Set

[Thomas Schilling]

On 4 July 2012 14:54, Patrick Palka <patrick at parcs.ath.cx> wrote:
> On 7/4/2012 5:02 AM, Thomas Schilling wrote:
>>
>> I'm surprised that these functions already exists in Data.Map. What are
>> the use cases?
>
>
> One can use the indexing functions to retrieve a random element from the
> container, or to random-shuffle a container in n log n time.

OK, that seems like a reasonable use case.

The existing documentation is lacking, though.  For example, the above
use case requires that: 0 <= index < Map.size map

It's also not specified that the index refers to the index in the
sorted sequence.  Of course, that problem here is that "Ord" -- which
is really an implementation detail -- becomes part of the specified
properties of a Map/Set. E.g., the same function for HashMap probably
wouldn't make that guarantee.

I.e., what are the properties of these functions?  Do we have:

  - findIndex a set `compare` findIndex b set ==> a `compare` b
  - findIndex a set == findIndex a (Set.toList set)
  - ...

Hoogle is down (along with haskell.org), ATM, so I can't look up the
proper list functions.