F# remove imperative code - quick help

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? Hmm? :-)

Thanks.

---

Edit: 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 would use Seq.to_list to transform the input sequence into a list and then use the list based approach. The list quoted is short enough that it shouldn't be an unreasonable overhead.

Answer 2

I will provide only Haskell version since I don't have F# present on my notebook, it should be similar. The principle is to convert your sequence to sequence like

[(0.7,"a"),(1.3,"b"),(1.8,"c"),(1.9,"d")]

where each first element in the tuple is representing not probablity but something like range. Then it is easy, pick one random number from 0 to last number (1.9) and check in which range it belongs to. For example if 0.5 is chosen, it will be "a" because 0.5 is lower than 0.7.

Haskell code -

probabilitySeq = [("a", 0.7), ("b", 0.6), ("c", 0.5), ("d", 0.1)]

modifySeq :: [(String, Double)] -> [(Double, String)]
modifySeq seq = modifyFunction 0 seq where 
    modifyFunction (_) [] = []
    modifyFunction (acc) ((a, b):xs) = (acc + b, a) : modifyFunction (acc + b) xs

pickOne :: [(Double, String)] -> IO String
pickOne seq = let max = (fst . last) seq in
    do 
     random <- randomRIO (0, max)
     return $ snd $ head $ dropWhile (\(a, b) -> a < random) seq

result :: [(String, Double)] -> IO String
result = pickOne . modifySeq

Example -

*Main> result probabilitySeq
"b"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"d"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"b"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"c"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"c"

Answer 3

The simplest solution is to use ref to store state between calls to iterator for any suitable function from Seq module:

let probabilitySeq = seq [ ("a", 0.7); ("b", 0.6); ("c", 0.5); ("d", 0.1) ]

let randomPick probSeq =
    let sum = Seq.fold (fun s (_,v) -> s + v) 0.0 probSeq 
    let random = ref (System.Random().NextDouble() * sum)
    let aux = function
        | _,v when !random >= v ->
            random := !random - v
            None
        | s,_ -> Some s
    match Seq.first aux probSeq with
        | Some r -> r
        | _ -> fst (Seq.hd probSeq)

Answer 4

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...

Answer 5

The way I understand it, you're logic works like this:

Sum all the weights, then select a random double somewhere between 0 and the sum of all the weights. Find the item which corresponds to your probability.

In other words, you want to map your list as follows:

Item    Val    Offset    Max (Val + Offset)
----    ---    ------    ------------------
a       0.7    0.0       0.7
b       0.6    0.7       1.3
c       0.5    1.3       1.8
d       0.1    1.8       1.9

Transforming a list of (item, probability) to (item, max) is straightforward:

let probabilityMapped prob =
    [
        let offset = ref 0.0
        for (item, probability) in prob do
            yield (item, probability + !offset)
            offset := !offset + probability
    ]

Although this falls back on mutables, its pure, deterministic, and in the spirit of readable code. If you insist on avoiding mutable state, you can use this (not tail-recursive):

let probabilityMapped prob =
    let rec loop offset = function
        | [] -> []
        | (item, prob)::xs -> (item, prob + offset)::loop (prob + offset) xs
    loop 0.0 prob

Although we're threading state through the list, we're performing a map, not a fold operation, so we shouldn't use the Seq.fold or Seq.scan methods. I started writing code using Seq.scan, and it looked hacky and strange.

Whatever method you choose, once you get your list mapped, its very easy to select a randomly weighted item in linear time:

let rnd = new System.Random()
let randomPick probSeq =
    let probMap =
        [
            let offset = ref 0.0
            for (item, probability) in probSeq do
                yield (item, probability + !offset)
                offset := !offset + probability
        ]

    let max = Seq.maxBy snd probMap |> snd
    let rndNumber = rnd.NextDouble() * max    
    Seq.pick (fun (item, prob) -> if rndNumber <= prob then Some(item) else None) probMap

Answer 6

I would use your functional, list-based version, but adapt it to use LazyList from the F# PowerPack. Using LazyList.of_seq will give you the moral equivalent of a list, but without evaluating the whole thing at once. You can even pattern match on LazyLists with the LazyList.(|Cons|Nil|) pattern.

Answer 7

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).
:-)