[swift-users] Incorrect Fisher-Yates shuffle in example code

[Nevin Brackett-Rozinsky]

On Sun, Dec 17, 2017 at 7:37 PM, Dave Abrahams <dabrahams at apple.com> wrote:

>
> On Dec 16, 2017, at 4:34 PM, Nevin Brackett-Rozinsky via swift-users <
> swift-users at swift.org> wrote:
>
> public extension MutableCollection where Self: RandomAccessCollection,
> IndexDistance == Int {
>
>
> IndexDistance == Int is an over-constraint, FWIW.  Adding it is generally
> a mistake.  Not a serious one, but it does limit utility somewhat.
>
> HTH,
> Dave
>

You are correct, however there is an accepted-and-implemented proposal (
SE–0191
<https://github.com/apple/swift-evolution/blob/master/proposals/0191-eliminate-indexdistance.md>)
to eliminate IndexDistance and replace it with Int, so the constraint will
always be satisfied starting in Swift 4.1.

I wrote a version of shuffle() without that constraint, but it is less
elegant: the line “for n in 0 ..< count - 1” no longer compiles, and
writing “0 as IndexDistance” doesn’t fix it because the resulting Range is
not a Sequence, since IndexDistance.Stride does not conform to
SignedInteger (at least in Swift 4.0 according to Xcode 9.2).

A while loop works of course, though a direct conversion requires writing
“var n = 0 as IndexDistance” before the loop. Luckily, with a bit of
cleverness we can eliminate all mention of IndexDistance, and this time we
really and truly don’t need the “guard !isEmpty” line:

extension MutableCollection where Self: RandomAccessCollection {
    mutating func shuffle() {
        var n = count
        while n > 1 {
            let i = index(startIndex, offsetBy: count - n)
            let j = index(i, offsetBy: random(n))
            n -= 1
            swapAt(i, j)
        }
    }
}

Essentially, the constraint is there to make the code nicer on pre-4.1
versions of Swift, though I’m happy to remove it if you think that’s
better. If nothing else, removing the constraint means people reading the
example code in the future won’t be misled into thinking they need to use
it themselves, so perhaps it should go just on that account.

Okay, you’ve convinced me, I’ll update the PR. :-)

Nevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20171217/c13f90c7/attachment.html>