F # replace ref variable with something funny

Question

I have the following F # function, which uses the ref variable for the seed and keeps track of the current total, something tells me that this is not in the spirit of fp or even a separate clarity. I would like some direction to be clearer (maybe fp, but if the imperative approach becomes clearer, I would open it) to express this in F #. Note that selectItem implements a selective weighted selection algorithm.

type WeightedItem(id: int, weight: int) = member self.id = id member self.weight = weight let selectItem (items: WeightedItem list) (rand:System.Random) = let totalWeight = List.sumBy (fun (item: WeightedItem) -> item.weight) items let selection = rand.Next(totalWeight) + 1 let runningWeight = ref 0 List.find (fun (item: WeightedItem) -> runningWeight := !runningWeight + item.weight !runningWeight >= selection) items let items = [new WeightedItem(1,100); new WeightedItem(2,50); new WeightedItem(3,25)] let selection = selectItem items (new System.Random()) 

Answer 1

Here is a version of a search algorithm using a recursive function. My F # is very rusty and I don’t know what to return when we can’t find anything:

 let rec find list item total = match list with | h::t -> if h > total then h else find t item total+h | [] -> 0 //<-- return some sort of default to say can't find the item 

EDIT

Full code:

 type WeightedItem(id: int, weight: int) = member self.id = id member self.weight = weight let selectItem (items: WeightedItem list) (rand:System.Random) = let totalWeight = List.sumBy (fun (item: WeightedItem) -> item.weight) items let selection = rand.Next(totalWeight) + 1 let rec find runningWeight ((h:WeightedItem)::t) = let newRunningWeight = runningWeight + h.weight if newRunningWeight >= selection then h else find newRunningWeight t find 0 items let items = [new WeightedItem(1,100) new WeightedItem(2,50) new WeightedItem(3,25)] let selection = selectItem items (new System.Random()) 

Answer 2

Hm, here alone with Seq.scan, but it also feels very ugly ...

 type WeightedItem(id: int, weight: int) = member self.id = id member self.weight = weight let selectItem (items: WeightedItem list) (rand:System.Random) = let totalWeight = List.sumBy (fun (item: WeightedItem) -> item.weight) items let selection = rand.Next(totalWeight) + 1 Seq.scan (fun (runningWeight,found,itemO) (item: WeightedItem) -> if not found then let newRunningWeight = runningWeight + item.weight newRunningWeight, newRunningWeight >= selection, Some(item) else (runningWeight,found,itemO)) (0,false,None) items |> Seq.find (fun (rw,f,i) -> f) |> (fun (rw,f,i) -> i.Value) let items = [new WeightedItem(1,100) new WeightedItem(2,50) new WeightedItem(3,25)] let selection = selectItem items (new System.Random()) 

Answer 3

The answer to the answer is probably the best for items stored in the list in terms of efficiency, but since the Brian scanning approach is a recursive sequence manipulation pattern, I suggest a slightly more compact change:

 let selectItem (items: WeightedItem list) (rand:System.Random) = let totalWeight = List.sumBy (fun (item: WeightedItem) -> item.weight) items let selection = rand.Next(totalWeight) + 1 items |> Seq.scan (fun acc (item : WeightedItem) -> acc + item.weight) 0 |> Seq.skip 1 |> Seq.zip items |> Seq.find (fun (i, rw) -> rw >= selection) |> fst 

Answer 4

Use Seq.unfold to create an on-demand sequence that accumulates runningWeight and then searches for the first element with a sufficiently large runningWeight using Seq.pick :

 let gen = function | _, [] -> None | runningWeight, item::items -> let runningWeight = runningWeight + item.weight Some((if runningWeight >= selection then Some item else None), (runningWeight, items)) Seq.unfold gen (0, xs) |> Seq.pick id 

Answer 5

Hm, here is one way to do this with fold , but it feels inelegant and always goes through the whole list ...

 type WeightedItem(id: int, weight: int) = member self.id = id member self.weight = weight let selectItem (items: WeightedItem list) (rand:System.Random) = let totalWeight = List.sumBy (fun (item: WeightedItem) -> item.weight) items let selection = rand.Next(totalWeight) + 1 List.fold (fun (runningWeight,found) (item: WeightedItem) -> if not found then let newRunningWeight = runningWeight + item.weight newRunningWeight, newRunningWeight >= selection else (runningWeight,found)) (0,false) items |> fst let items = [new WeightedItem(1,100) new WeightedItem(2,50) new WeightedItem(3,25)] let selection = selectItem items (new System.Random()) 

Answer 6

Hm, here are some mutables and a loop; still going through the whole list though ...

 type WeightedItem(id: int, weight: int) = member self.id = id member self.weight = weight let selectItem (items: WeightedItem list) (rand:System.Random) = let totalWeight = List.sumBy (fun (item: WeightedItem) -> item.weight) items let selection = rand.Next(totalWeight) + 1 let mutable runningWeight = 0 let mutable found = None for item in items do match found with | None -> runningWeight <- runningWeight + item.weight if runningWeight >= selection then found <- Some(item) | _ -> () found.Value let items = [new WeightedItem(1,100) new WeightedItem(2,50) new WeightedItem(3,25)] let selection = selectItem items (new System.Random()) 

This is my favorite of the three. I look forward to the day when F # adds break . Of course, you can call GetEnumerator and get full control, but this is also ugly.