# Proposed amendment to SE-202: Replace \`Collection.randomElement\` requirement with \`randomIndex\`

**URL:** <https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056>\
**Category:** Pitches\
**Created:** [May 30, 2018, 8:16pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056 "2018-05-30T20:16:14Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [May 30, 2018, 8:16pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/1 "2018-05-30T20:16:14Z")

</div>

[SE-202](https://github.com/apple/swift-evolution/blob/master/proposals/0202-random-unification.md), the "Random Unification" proposal, adds the following requirement to the Collection protocol:

```swift
protocol Collection {
  ...
  func randomElement<T: RandomNumberGenerator>(using generator: inout T) -> Element?
}

```

This was added as a requirement because collections with more than `Int.max` elements (for instance, the range `Int.min ... Int.max`) would not be able to use a generic implementation. However, this poses a forward-compatibility problem for `Collection` if we add move-only types in the future, since this requirement cannot be implemented by a collection with move-only elements, since returning the chosen element would require copying it out of the collection. We could make this requirement be `consuming`, but that's unlikely to be very useful, since picking a single random element out of a collection is unlikely to be the final thing you do with a collection.

There's a more primitive operation we could make a Collection requirement, which instead returns the _index_ of a random element in the collection:

```swift
protocol Collection {
  func randomIndex<T: RandomNumberGenerator>(using generator: inout T) -> Index?
}

```

`randomElement` can then be implemented as an extension method in terms of this requirement (for copyable Collections):

```swift
extension Collection {
  func randomElement<T: RandomNumberGenerator>(using generator: inout T) -> Element? {
    if let index = randomIndex(using: &generator) {
      return self[index]
    } else {
      return nil
    }
  }
}

```

Aside from future compatibility with move-only types, `randomIndex` seems like a better primitive operation, since it can used to build other interesting operations like "insert an element at a random index", "split a collection into random sub-collections", etc. Does this seem like a reasonable amendment to the proposal?

---

<div class="post-metadata">

**Author:** ![hlovatt](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hlovatt/32/3044_2.png) [@hlovatt](https://forums.swift.org/u/hlovatt)\
**Post date:** [May 30, 2018, 8:53pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/2 "2018-05-30T20:53:33Z")

</div>

Seems like a good suggestion.

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [May 30, 2018, 9:48pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/3 "2018-05-30T21:48:44Z")

</div>

I’m going to speak for myself, and possibly others, when I say that I do not know what a move-only type is. Or rather, I have looked up the definition—an instance of a move-only type cannot be copied, it can only be moved—but I do not understand the benefit or use. Why would we want move-only types in Swift, and what are they good for?

---

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [May 30, 2018, 9:54pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/4 "2018-05-30T21:54:58Z")

</div>

You may want to read @John_McCall's "ownership manifesto": [https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md](https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md)

---

<div class="post-metadata">

**Author:** ![griotspeak](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/griotspeak/32/1966_2.png) [@griotspeak](https://forums.swift.org/u/griotspeak)\
**Post date:** [May 30, 2018, 11:01pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/5 "2018-05-30T23:01:43Z")

</div>

more specifically, the section about non-copyable types [swift/OwnershipManifesto.md at main · apple/swift · GitHub](https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md#non-copyable-types)

---

<div class="post-metadata">

**Author:** ![jeremyp](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jeremyp/32/3552_2.png) [@jeremyp](https://forums.swift.org/u/jeremyp)\
**Post date:** [May 31, 2018, 9:29am UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/6 "2018-05-31T09:29:51Z")

</div>

As a general rule, I don't think hacking things about just because of some future feature that may or may not ever get implemented is a bad idea.

However, in this case, I think the other arguments for having `randomIndex` are fairly compelling and, in hindsight, this is how it should have been designed in the first place IMO.

---

<div class="post-metadata">

**Author:** ![DevAndArtist](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/devandartist/32/287_2.png) [@DevAndArtist](https://forums.swift.org/u/DevAndArtist)\
**Post date:** [May 31, 2018, 12:23pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/7 "2018-05-31T12:23:49Z")

</div>

> [@jeremyp](#):
>
> As a general rule, I don't think hacking things about just because of some future feature that may or may not ever get implemented is a bad idea.

As far as I'm concerned, the whole stdlib was designed around a lot of missing generic features which may or may not ever be implemented in Swift. Now we have a lot of those and the stdlib become much much simpler. That said, I don't buy this rule, as long as everything is crafted carefully it should be fine.

---

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [May 31, 2018, 4:46pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/8 "2018-05-31T16:46:50Z")

</div>

> [@jeremyp](#):
>
> As a general rule, I don't think hacking things about just because of some future feature that may or may not ever get implemented is a bad idea.

I agree with the general rule. In this case, ownership and move-only types are features we know fairly certainly we want to support in the near future, and this protocol requirement poses a clear obstacle for delivering the feature in the way we'd like.

---

<div class="post-metadata">

**Author:** ![beccadax](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/beccadax/32/34217_2.png) [@beccadax](https://forums.swift.org/u/beccadax)\
**Post date:** [June 1, 2018, 2:24am UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/9 "2018-06-01T02:24:11Z")

</div>

Don't other members like `first` have the same problem?

Should we address this in the `moveonly` design by allowing a protocol to say "this requirement only applies to non-`moveonly` conformances"? I've wanted a similar feature for other purposes—particularly, I've wanted to be able to put a `func index(of elem: Element) -> Index? where Element: Equatable` requirement so we could replace the private `_customIndexOfEquatableElement(_:)` requirement with something publicly usable.

---

<div class="post-metadata">

**Author:** ![hlovatt](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hlovatt/32/3044_2.png) [@hlovatt](https://forums.swift.org/u/hlovatt)\
**Post date:** [June 1, 2018, 3:57am UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/10 "2018-06-01T03:57:40Z")

</div>

> [@beccadax](#):
>
> "this requirement only applies to non- `moveonly` conformances"

Why not just subdivide the protocol; I dislike these massive protocols that you get stuck with all the requirements? Rather than introduce another where clause item. You can retain backwards compatibility with a 'convenience protocol' that inherits all the 'sub-protocols'.

---

<div class="post-metadata">

**Author:** ![felix91gr](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/felix91gr/32/443_2.png) [@felix91gr](https://forums.swift.org/u/felix91gr)\
**Post date:** [June 1, 2018, 5:05am UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/11 "2018-06-01T05:05:22Z")

</div>

I don't quite understand what you mean. What would a "convenience protocol" like you say look like?

---

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [June 1, 2018, 2:36pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/12 "2018-06-01T14:36:24Z")

</div>

> [@beccadax](#):
>
> Don't other members like `first` have the same problem?

I raised the issue with `first` in [another thread](https://forums.swift.org/t/preparing-the-iteration-abi-for-move-only-types/12980/8). @ben-cohen said it's a unnecessary customization point he can remove.

> [@beccadax](#):
>
> Should we address this in the `moveonly` design by allowing a protocol to say "this requirement only applies to non- `moveonly` conformances"? I've wanted a similar feature for other purposes—particularly, I've wanted to be able to put a `func index(of elem: Element) -> Index? where Element: Equatable` requirement so we could replace the private `_customIndexOfEquatableElement(_:)` requirement with something publicly usable.

@Douglas_Gregor has expressed concerns about implementing such a feature. All things equal, it'd be better to avoid tying the move-only feature to more prerequisite features if we can avoid it.

---

<div class="post-metadata">

**Author:** ![hlovatt](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hlovatt/32/3044_2.png) [@hlovatt](https://forums.swift.org/u/hlovatt)\
**Post date:** [June 1, 2018, 11:32pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/13 "2018-06-01T23:32:45Z")

</div>

> [@felix91gr](#):
>
> What would a "convenience protocol" like you say look like?

```swift
protocol MoveOnlyCollection {
    // Methods that are valid for move semantics like `randomIndex`.
}

protocol Collection: MoveOnlyCollection { // Convenience protocol if you want the lot. 
    // Other methods like `randomEment`. 
}

```

---

<div class="post-metadata">

**Author:** ![felix91gr](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/felix91gr/32/443_2.png) [@felix91gr](https://forums.swift.org/u/felix91gr)\
**Post date:** [June 1, 2018, 11:44pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/14 "2018-06-01T23:44:44Z")

</div>

Ah, I think I get it now. The idea would be that, since move-only collections can have some but not all of the functions that normal collections can, you use a small protocol (`MoveOnlyCollection`) and expand it to give it all the normal-but-not-moveonly-collection's functions (`Collection`)

* * *

That said though, it looks strange to say that `Collection : MoveOnlyCollection`. I'd prefer to have the smaller one be called `CoreCollection`, and have a shim-protocol that's named `MoveOnlyCollection`. That'd also allow for future "only for moveonly collection"-functions, if we'd ever need them.

EDIT: maybe your naming is actually spot-on. We could benefit from having explicit moveonly guarantees for what functions can be shared between the moveonly and non-moveonly collections.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [June 2, 2018, 4:54pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/15 "2018-06-02T16:54:32Z")

</div>

> [@Joe\_Groff](#):
>
> I raised the issue with `first` in [another thread](https://forums.swift.org/t/preparing-the-iteration-abi-for-move-only-types/12980/8). @ben-cohen said it's a unnecessary customization point he can remove.

Yeah, I can't see the justification for keeping `first` (and `last`) as protocol requirements.

Unfortunately, `min` and `max` are another story, given `Comparable`-ordered collections are common (`Indices`, ranges, hopefully soon a sorted set or dictionary) so it's definitely good to allow collections that know they're sorted to have an `O(n)` version of these.

Doing the same trick of switching to returning the index instead of the element presents a couple of challenges:

1. They're a naming nightmare. `minIndex` is wrong – it's the index of the minimum element, not the minimum index (which is always `startIndex`). So you need to go for something waffly like `minimumElementIndex`.

2. They return an optional, and handling that is a real pain: `c.minIndex.map { c[$0] }`. So we'd definitely need to keep the element-returning versions too, and that's an unfortunate amount of redundancy.

That said, I don't see a real problem adding both the index versions on the protocol plus the convenience element versions via extensions that can in future be constrained to only copyable types.

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [June 2, 2018, 8:18pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/16 "2018-06-02T20:18:45Z")

</div>

> [@Joe\_Groff](#):
>
> You may want to read @John_McCall's "ownership manifesto": [https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md](https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md)

I read the entire thing once before, and I just re-read the section on non-copyable types. I’ll trust that you and John and the rest know what you’re talking about, but that document did not convey to me an understanding of what move-only types are for, nor why we should want them.

> [@ben-cohen](#):
>
> Unfortunately, `min` and `max` are another story, given `Comparable` -ordered collections are common ( `Indices` , ranges, hopefully soon a sorted set or dictionary) so it's definitely good to allow collections that know they're sorted to have an `O(n)` version of these.
> 
> Doing the same trick of switching to returning the index instead of the element presents a couple of challenges:
> 
> 1. They're a naming nightmare. `minIndex` is wrong – it's the index of the minimum element, not the minimum index (which is always `startIndex` ). So you need to go for something waffly like `minimumElementIndex` .
> 
> 2. They return an optional, and handling that is a real pain: `c.minIndex.map { c[$0] }` . So we'd definitely need to keep the element-returning versions too, and that's an unfortunate amount of redundancy.
> 
> That said, I don't see a real problem adding both the index versions on the protocol plus the convenience element versions via extensions that an in future be constrained to only copyable types.

The naming is easy: `indexOfMin` and `indexOfMax`. I’ve written and used these myself for various purposes.

Although, to mesh with the recent renaming of `index(where:)` to `firstIndex(where:)`, perhaps it ought to be `firstIndexOfMin`, etc.

---

<div class="post-metadata">

**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\
**Post date:** [June 2, 2018, 9:48pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/17 "2018-06-02T21:48:27Z")

</div>

> [@Nevin](#):
>
> The naming is easy: `indexOfMin` and `indexOfMax` . I’ve written and used these myself for various purposes.
> 
> Although, to mesh with the recent renaming of `index(where:)` to `firstIndex(where:)` , perhaps it ought to be `firstIndexOfMin` , etc.

Do we care that it returns specifically the _first_ index? I'd imagine that, for most uses, it's sufficient that it returns _an_ index, and guaranteeing that it's the _first_ one seems like it might be overly restrictive.

I really don't think it's a problem to name that property `minElementIndex`. It's clear and not overly verbose.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [June 2, 2018, 10:13pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/18 "2018-06-02T22:13:51Z")

</div>

> [@Nevin](#):
>
> The naming is easy: `indexOfMin` and `indexOfMax` . I’ve written and used these myself for various purposes.
> 
> Although, to mesh with the recent renaming of `index(where:)` to `firstIndex(where:)` , perhaps it ought to be `firstIndexOfMin` , etc.

Abbreviations are usually only allowed when they’re terms of art, which `min` and `max` are but these index versions aren’t. But if the element versions remain, we can probably abbreviate the index versions for consistency.

I don’t think the `first` naming applies here. There are many possible equal elements, but only one minimum.

Edit: duh, no, sorry, I guess the same minimum element could appear a second time. But still, it doesn’t seem to have the same importance as the matching first/last symmetry.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [June 2, 2018, 10:26pm UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/19 "2018-06-02T22:26:11Z")

</div>

It shouldn’t be necessary to introduce a second protocol for the fetching of elements. This could be done via extension where the element type were copyable. A protocol is necessary to add customization points, but here the necesssry customization can be on the index returning versions (i.e. getting the minimum of a sorted collection can be done in constant time).

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [June 3, 2018, 12:08am UTC](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056/20 "2018-06-03T00:08:14Z")

</div>

Thinking about it more…

`min` is currently defined on `Sequence`. If we go through with the revamp to make `Sequence` just a typealias for `Collection` with auto-generated indices, then there’s no problem.

But the way things stand today, `Sequence.min` cannot be implemented in terms of `indexOfMin`, because sequences don’t have indices.

[Next page](https://forums.swift.org/t/proposed-amendment-to-se-202-replace-collection-randomelement-requirement-with-randomindex/13056.md?page=2)