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

I think that cfern's suggestion is actually simplest (?= best) solution to this.

Entire input needs to be evaluated, so seq's advantage of yield-on-demand is lost anyway. Easiest seems to take sequence as input and convert it to a list and total sum at the same time. Then use the list for the list-based portion of the algorithm (list will be in reverse order, but that doesn't matter for the calculation).

let randomPick moveList =
    let sum, L = moveList
        |> Seq.fold (fun (sum, L) dir -> sum + snd dir, dir::L) (0.0, [])
    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 (rand.NextDouble() * sum) L

Thanks for Yours solutions, especially Juliet and Johan (I've to read it few times to actually get it).
:-)