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
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).
Thanks for Yours solutions, especially Juliet and Johan (I've to read it few times to actually get it).
:-)