[RFC FS-1135] Random functions for collections

[Lanayx]

Let's discuss RFC FS-1135 as proposed in PR #732

[kerams]

In .NET 6 and higher Random.Shared will be used, otherwise Fsharp.Core defined shared instance

FSharp.Core does not target .NET 6 or higher though.

[Lanayx]

You are right, I moved it down to unresolved questions. If targeting .NET 6 is not on horizon, we'll need to basically copy Random.Shared implementation.

[abelbraaksma]

I think the only targets atm are NetStandard 2.0 and NetStandard 2.1. And indeed, this is not in there. I guess we can cherrypick.

[Lanayx]

Right now there is a main issue - how to call newly functions, right now we have two main options

1. With prefix (e.g. List.randomShuffle, List.randomChoice, List.randomChoices, List.randomSample)
2. Without prefix (e.g. List.shuffle, List.choice, List.choices, List.sample)

Please vote for the prefixed version with 🚀, for the short version with 🎉

[Lanayx]

Hmm, I didn't realize that Array.Parallel chose that way, in that case a module makes more sense than a prefix. If Array.Parallel didn't exist, I wouldn't go this approach, but since that design was approved, I don't have anything against it

[dsyme]

This doesn't feel right - for Parallel it's like "this is Array only parallel". For Random that doesn't apply - none of the names are in common, and if any were it would be really confusing.

[Lanayx]

I've reverted, however I don't read Array.Parallel as "this is Array only parallel" :) I read it - this is a Parallel module for Array that contains parallel operations, so I don't care about whether any names are common or not. They all could have been named just the in the same way with prefix - Array.parallelMap, Array.parallelPartition, but the submodule design was chosen. If we go with prefixes for random, it will be a diverge in approaches.

[Lanayx]

Just for reference I've asked ChatGPT 4.0 about this choice (prefixes vs submodules) and here is what it answered

[Lanayx]

@dsyme are you still thinking about it?

[abelbraaksma]

Hey @Lanayx, I'm reviewing your proposal atm (and was hoping to un-stale this RFC, it is good work and should go in!). I was wondering if you've considered to use a function as argument, as opposed to a Random type object? I.e.: randomShuffle: randomizer: (unit -> int) -> array: 'T[] -> 'T[]?

I know it would increase the surface area of the functions, and it would require an extra check (i.e., if the returned value is out of range). But considering we're in a functional language, it stands to reason that we allow users to use a function to provide the random values.

Alternatively, randomShuffle: randomizer: (unit -> float) -> array: 'T[] -> 'T[] could be considered, where the returned float value must be between 0.0 - 1.0, which is possibly less of a burden on the programmer, as the translation to an index within bounds will be done by the function implementation.

[abelbraaksma]

Still it seems some people think that HOF is a good idea, so I can agree to add it as 3d option to RFC if you (or someone else) will give a practical example

I've given a bunch of them above. Hope this helps understanding our motivation for wanting a more generic approach than only one through System.Random.

[Lanayx]

Thanks @abelbraaksma for such a detailed answer!
It's quite remarkable that almost all your links either provide a System.Random custom implementation or provide API that is very similar to System.Random one, which means that Random generator is really expected to be a class with methods. I've also went through several performance-related links you provided and figured out that slowness comes not because of it's API, but rather default implementation.

I'd also argue about unit test for shuffling business logic that doesn't shuffle, but that's a weak point.

I think conversation really boils down to the question - once user wants their own implementation of random sampling, what's more convenient for them - to inherit and override Random methods or just to provide a single function that returns a value from 0..1 range. And now I think that you are right, that giving a single function is way easier that dealing with bunch of different methods. I don't know if that simplicity is good or bad (for example from performance perspective), but I do agree, that it can be useful for some people.

[Lanayx]

I'll update the RFC accordingly soon.

[abelbraaksma]

I've also went through several performance-related links you provided and figured out that slowness comes not because of it's API, but rather default implementation.

I've actually been meaning for years to do some perf tests myself and to test the distribution of the default implementation. But you know, priorities. I didn't look deeply into it, there's so much written on the subject of Random that I just picked several posts that I came across.

When I've more time I may take a deeper dive (esp about the lib that promises an 8x perf improvement).

I don't know if that simplicity is good or bad (for example from performance perspective)

The great thing not mentioned so far, but you hinted about it, is that a function is F# can be inlined (through InlineIfLambdaAttribute), removing any and all allocations (as you may be aware, a function has state through its closure, and to capture that state, an object is allocated. Which is why inlining is important).

I'll update the RFC accordingly soon.

Thanks, that's appreciated! ❤️

[Lanayx]

If talking about performance I meant that converting to float and back might have a performance hit which will make lambda version not suitable for such cases. For example someone could use RandomNumberGenerator.GetInt32 to sample an element from array, but instead he will have to first map that to float (range 0..1) which will eventually be converted back to int. Implementing Random based on RandomNumberGenerator would give better performance in this case.

[abelbraaksma]

@Lanayx, putting this in a different discussion thread, @nkeenan38 pointed out the following point in an offline discussion:

but how these functions work for sequences? The size isn’t known, right? They may even be infinite? Its not clear to me how a (non-trivial) infinite sequence is randomly sorted (or an element is randomly selected)

My take on this is that these will fail for infinite sequences (similar to sort and sortBy) and that for list and seq, the sequences will be cached. We may even use a type-test to find if a seq is a cast of an array or IList, but that's an implementation detail perhaps.

[Lanayx]

Right, shuffling shouldn't be different from sorting as regarding to handling infinite sequences

[abelbraaksma]

@Lanayx, you raised a point about what should happen when the shuffling algorithm you provide is not really shuffling. I wasn't entirely sure wrt my own answer, so I figured, let's look at the source.

You may or may not want to mention this in the RFC. It may help with adding corner cases.

Here are two examples (remember that max is exclusive, min is inclusive):

type MyRandom() =
    inherit System.Random()

    override this.Next(minv, maxv) =
        if minv = maxv then minv
        else maxv - 1

let testShuffle() =
    let xs = [|1;2;3;4;5;6;7;8|]
    MyRandom().Shuffle(xs)
    xs

> testShuffle();;
val it: int array = [|8; 1; 2; 3; 4; 5; 6; 7|]

type MyRandom() =
    inherit System.Random()

    override this.Next(minv, maxv) =minv

let testShuffle() =
    let xs = [|1;2;3;4;5;6;7;8|]
    MyRandom().Shuffle(xs)
    xs

> testShuffle();;
val it: int array = [|1; 2; 3; 4; 5; 6; 7; 8|]

Essentially, I'd suggest we just follow the .NET algorithm and translate where needed. I'm sure you've seen this before (for reference, here's the original implementation, not sure we pointed to it before: dotnet/runtime#78598):

        public void Shuffle<T>(Span<T> values)
        {
            int n = values.Length;

            for (int i = 0; i < n - 1; i++)
            {
                int j = Next(i, n);

                if (j != i)
                {
                    T temp = values[i];
                    values[i] = values[j];
                    values[j] = temp;
                }
            }
        }

I don't think we can rely on Span, unless we want to create multiple implementations, but the same applies to any other algo anyway.

[abelbraaksma]

Same applies to using the same seed, which is prob. what you want to use in your tests (yes, I'm sure this is well-known, but just figured I'd make it explicit ;) ):

let testShuffle() =
    let xs = [|1;2;3;4;5;6;7;8|]
    Random(42).Shuffle(xs)
    xs

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]