How to remove imperative code from a function?

Question

I'm new to functional world and appreciate help on this one.

I want to SUPERCEDE ugly imperative code from this simple function, but don't know how to do it.

What I want is to randomly pick some element from IEnumerable (seq in F#) with a respect to probability value - second item in tuple (so item with "probability" 0.7 will be picked more often than with 0.1).

/// seq<string * float>
let probabilitySeq = seq [ ("a", 0.7); ("b", 0.6); ("c", 0.5); ("d", 0.1) ]

/// seq<'a * float> -> 'a
let randomPick probSeq =
    let sum = Seq.fold (fun s dir -> s + snd dir) 0.0 probSeq 
    let random = (new Random()).NextDouble() * sum
    // vvvvvv UGLY vvvvvv
    let mutable count = random
    let mutable ret = fst (Seq.hd probSeq )
    let mutable found = false
    for item in probSeq  do
        count <- count - snd item
        if (not found && (count < 0.0)) then
            ret <- fst item  //return ret;  //in C# 
            found <- true
    // ^^^^^^ UGLY ^^^^^^
    ret

////////// at FSI: //////////

> randomPick probabilitySeq;;
    val it : string = "a"
> randomPick probabilitySeq;;
    val it : string = "c"
> randomPick probabilitySeq;;
    val it : string = "a"
> randomPick probabilitySeq;;
    val it : string = "b"

I think that randomPick is pretty straightforward to implement imperatively, but functionally?

---

This is functional, but take list not seq (wanted).

//('a * float) list -> 'a
let randomPick probList =
    let sum = Seq.fold (fun s dir -> s + snd dir) 0.0 probList
    let random = (new Random()).NextDouble() * sum
    let rec pick_aux p list = 
        match p, list with
        | gt, h::t when gt >= snd h -> pick_aux (p - snd h) t
        | lt, h::t when lt < snd h -> fst h 
        | _, _ -> failwith "Some error"
    pick_aux random probList

Answer 1

An F# solution using the principle suggested by Matajon:

let randomPick probList =
    let ps = Seq.skip 1 (Seq.scan (+) 0.0 (Seq.map snd probList))
    let random = (new Random()).NextDouble() * (Seq.fold (fun acc e -> e) 0.0 ps)
    Seq.find (fun (p, e) -> p >= random)
             (Seq.zip ps (Seq.map fst probList))
    |> snd

But I would probably also use a list-based approach in this case since the sum of the probability values needs to be precalculated anyhow...