Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

F# replace ref variable with something fun

I have the following F# function which makes use of a ref variable to seed and keep track of a running total, something tells me this isn't in the spirit of fp or even particular clear on its own. I'd like some direction on the clearest (possible fp, but if an imperative approach is clearer I'd be open to that) way to express this in F#. Note that selectItem implements a random 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())
like image 511
Stephen Swensen Avatar asked Dec 17 '22 00:12

Stephen Swensen


2 Answers

Here is a version of the 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()) 
like image 131
Igor Zevaka Avatar answered Jan 02 '23 09:01

Igor Zevaka


Hm, here's one 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()) 
like image 34
Brian Avatar answered Jan 02 '23 07:01

Brian