F # заменить переменную ref чем-то интересным

Question

У меня есть следующая функция F #, которая использует переменную ref для заполнения и отслеживания промежуточного итога, что-то подсказывает мне, что это не в духе fp или даже не совсем ясно само по себе. Я хотел бы получить какое-то указание на самый ясный (возможный fp, но если императивный подход яснее, я был бы открыт для этого) способ выразить это в F #. Обратите внимание, что selectItem реализует алгоритм случайного взвешенного выбора.

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

Вот версия алгоритма поиска с использованием рекурсивной функции. Мой F # очень ржавый, и я не знаю, что вернуть, когда мы ничего не можем найти:

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

Полный код:

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

Используйте Seq.unfold для построения последовательности по требованию, которая накапливает runningWeight, а затем найдите ее для первого элемента, который имел достаточно большой runningWeight, используя 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 3

Ответ Игоря, вероятно, является лучшим для элементов, хранящихся в списке, с точки зрения эффективности, но поскольку подход сканирования Брайана является репрезентативным шаблоном манипулирования последовательностью, я предлагаю несколько более компактный вариант:

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

Хм, вот один с Seq.scan, но он также кажется очень уродливым ...

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 5

Хм, вот несколько таблиц и петли; все еще перебирает весь список ...

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()) 

Это мой любимый из трех. Я с нетерпением жду того дня, когда F # добавит break. Конечно, вы можете позвонить GetEnumerator и получить полный контроль, но это тоже ужасно.

Answer 6

Хм, вот один из способов сделать это с fold, но он выглядит не элегантным и всегда перебирает весь список ...

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())