F # remove imperative code - quick help

Question

I am new to the functional world and appreciate help on this.

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

I want the random selection of an element from IEnumerable (seq in F #) taking into account the probability value - the second element in the tuple (so that an element with a "probability" of 0.7 will be selected 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 randomPick pretty simple to implement imperatively, but functionally? Hmm ?:-)

Thanks.

---

Edit: This is functional, but take a non- seq list (required).

 //('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 the cfern suggestion is actually the easiest (? = Best) solution for this.

The entire entry must be evaluated, so in any case the loss of benefit on demand is lost. It seems that the easiest way is to take a sequence as input and convert it to a list and total amount at the same time. Then use the list for part of the list-based algorithm (the 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 

Thank you for your decisions, especially Juliet and Johan (I have to read this several times in order to actually get this).
:-)

Answer 2

F # solution using the principle proposed 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 ​​must be pre-calculated ...

Answer 3

I will only provide a version of Haskell, since I do not have F # present on my laptop, it should be similar. The principle is to convert a sequence to a sequence, for example

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

where every first element in a tuple is not a probability, but something like a range. Then it’s easy, select one random number from 0 to the last number (1.9) and check in which range it belongs. For example, if 0.5 is selected, it will be "a" because 0.5 is less 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 4

The way I understand it, logically works as follows:

Sum all weights, then select a random double somewhere between 0 and the sum of all weights. Find the item that matches your likelihood.

In other words, you want to display 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 

Converting a list (item, probability) to (item, max) is simple:

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

Although this applies to mutables, its clean, deterministic and readable code. If you insist on avoiding a volatile state, you can use this (rather than tail recursively):

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

Despite the fact that we list the state through a list, we are executing a map, not a bend operation, so we should not use the Seq.fold or Seq.scan methods. I started writing code with Seq.scan and it looked hacked and weird.

Whichever method you choose, once you get your list, it is very easy to select a random weighted element 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 5

I would use Seq.to_list to convert the input sequence to a list, and then use a list-based approach. The list quoted is short enough that this should not be unreasonable overhead.

Answer 6

The simplest solution is to use ref to store the state between iterator calls for any suitable function from the 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 7

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