How to remove imperative code from a function?

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 imperative开发者_开发问答ly, 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

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

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"

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

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.

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)

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.

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