How can I select a random value from a list using F#

Question

I'm new to F# and I'm trying to figure out how to return a random string value from a list/array of strings.

I have a list like this:

["win8FF40", "win10Chrome45", "win7IE11"]

How can I randomly select and return one item from the list above?

Here is my first try:

let combos = ["win8FF40";"win10Chrome45";"win7IE11"]  

let getrandomitem () =  
  let rnd = System.Random()  
  fun (combos : string[]) -> combos.[rnd.Next(combos.Length)]  

Answer 1

Both the answers given here by latkin and mydogisbox are good, but I still want to add a third approach that I sometimes use. This approach isn't faster, but it's more flexible and more composable, and fast enough for small sequences. Depending on your needs, you can use one of higher performance options given here, or you can use the following.

Single-argument function using Random

Instead of directly enabling you to select a single element, I often define a shuffleR function like this:

open System

let shuffleR (r : Random) xs = xs |> Seq.sortBy (fun _ -> r.Next())

This function has the type System.Random -> seq<'a> -> seq<'a>, so it works with any sort of sequence: lists, arrays, collections, and lazily evaluated sequences (although not with infinite sequences).

If you want a single random element from a list, you can still do that:

> [1..100] |> shuffleR (Random ()) |> Seq.head;;
val it : int = 85

but you can also take, say, three randomly picked elements:

> [1..100] |> shuffleR (Random ()) |> Seq.take 3;;
val it : seq<int> = seq [95; 92; 12]

No-argument function

Sometimes, I don't care about having to pass in that Random value, so I instead define this alternative version:

let shuffleG xs = xs |> Seq.sortBy (fun _ -> Guid.NewGuid())

It works in the same way:

> [1..100] |> shuffleG |> Seq.head;;
val it : int = 11
> [1..100] |> shuffleG |> Seq.take 3;;
val it : seq<int> = seq [69; 61; 42]

Although the purpose of Guid.NewGuid() isn't to provide random numbers, it's often random enough for my purposes - random, in the sense of being unpredictable.

Generalised function

Neither shuffleR nor shuffleG are truly random. Due to the ways Random and Guid.NewGuid() work, both functions may result in slightly skewed distributions. If this is a concern, you can define an even more general-purpose shuffle function:

let shuffle next xs = xs |> Seq.sortBy (fun _ -> next())

This function has the type (unit -> 'a) -> seq<'b> -> seq<'b> when 'a : comparison. It can still be used with Random:

> let r = Random();;    
val r : Random    
> [1..100] |> shuffle (fun _ -> r.Next()) |> Seq.take 3;;
val it : seq<int> = seq [68; 99; 54]
> [1..100] |> shuffle (fun _ -> r.Next()) |> Seq.take 3;;
val it : seq<int> = seq [99; 63; 11]

but you can also use it with some of the cryptographically secure random number generators provided by the Base Class Library:

open System.Security.Cryptography
open System.Collections.Generic

let rng = new RNGCryptoServiceProvider ()
let bytes = Array.zeroCreate<byte> 100
rng.GetBytes bytes

let q = bytes |> Queue

FSI:

> [1..100] |> shuffle (fun _ -> q.Dequeue()) |> Seq.take 3;;
val it : seq<int> = seq [74; 82; 61]

Unfortunately, as you can see from this code, it's quite cumbersome and brittle. You have to know the length of the sequence up front; RNGCryptoServiceProvider implements IDisposable, so you should make sure to dispose of rng after use; and items will be removed from q after use, which means it's not reusable.

Cryptographically random sort or selection

Instead, if you really need a cryptographically correct sort or selection, it'd be easier to do it like this:

let shuffleCrypto xs =
    let a = xs |> Seq.toArray

    use rng = new RNGCryptoServiceProvider ()
    let bytes = Array.zeroCreate a.Length
    rng.GetBytes bytes

    Array.zip bytes a |> Array.sortBy fst |> Array.map snd

Usage:

> [1..100] |> shuffleCrypto |> Array.head;;
val it : int = 37
> [1..100] |> shuffleCrypto |> Array.take 3;;
val it : int [] = [|35; 67; 36|]

This isn't something I've ever had to do, though, but I thought I'd include it here for the sake of completeness. While I haven't measured it, it's most likely not the fastest implementation, but it should be cryptographically random.

Answer 2

Your problem is that you are mixing Arrays and F# Lists (*type*[] is a type notation for Array). You could modify it like this to use lists:

let getrandomitem () =  
  let rnd = System.Random()  
  fun (combos : string list) -> List.nth combos (rnd.Next(combos.Length))

That being said, indexing into a List is usually a bad idea since it has O(n) performance since an F# list is basically a linked-list. You would be better off making combos into an array if possible like this:

let combos = [|"win8FF40";"win10Chrome45";"win7IE11"|]