实现F#回溯

Question

我一直在玩一个着名的背包问题.这一次 - 然而 - 我决定在F#中实现它,因为我正在学习语言并且发现它特别有趣.

我已经成功实现了算法的主要部分,但我也需要回溯.不幸的是,我在网上找到的所有信息都使用了Haskell,我不知道(还有)).

作为占位符,我使用可变变量实现了回溯(没有详细说明,"组合(i,k)"返回i项的部分解和k的容量):

let output = 
    List.rev
        [
            let i = ref N
            let k = ref K
            // analize items starting with the last one
            for item in Array.rev items do
                match !k - item.Size with
                // if size of i-th item is greater than current capacity...
                | x when x <  0 -> i := !i - 1
                       // ... this means we haven't taken this item
                                   yield 0
                // otherwise we've got two cases
                | x when x >= 0 -> let v1 = combinations (!i-1, !k) id
                                   let vc = combinations (!i, !k) id
                                   if v1 = vc then 
                                    // case 1: item hasn't been taken
                                    i := !i - 1
                                    yield 0
                                   else
                                     // case 2: item is contained in the optimal solution
                                    i := !i - 1
                                    k := x
                                    yield 1
        ]

List.iter (fun x -> printf "%A " x) output

我相信在F#中有更好的方法(例如使用计算表达式).我很高兴听到有关如何在功能风格中实现这一点的任何提示/信息.

最后一件事:请记住我是函数式编程的新手,并尽量避免使用我发现的一些魔术表达式:

"monad是endofunctors类别中的幺半群,问题是什么？" :)

Answer 1

在这种情况下您可以使用的一般模式是折叠.当你需要步行一个列表(就像这是有用的items,你的情况),并保持一定的状态,当您去(i和k,你的情况).这可以使用高阶函数实现Array.fold(当您使用数组时):

let results, _, _ = items |> Array.rev |> Array.fold (fun (resultsSoFar, i, k) item ->
  match k - item.Size with
  // if size of i-th item is greater than current capacity...
  | x when x <  0 -> 
      // ... this means we haven't taken this item
      (0::resultsSoFar, i - 1, k)
  // otherwise we've got two cases
  | x when x >= 0 -> 
      let v1 = combinations (i-1, !k) id
      let vc = combinations (i, !k) id
      if v1 = vc then 
        // case 1: item hasn't been taken
        (0::resultsSoFar, i - 1, k)
      else
        (1::resultsSoFar, i - 1, x) ) ([], N, K)

这个想法是函数获得先前状态(resultsSoFar, i, k)和当前状态并且item应该返回新状态 - 例如,如果我们想要生成0和减少i,我们可以返回,(0::resultsSoFar, i - 1, k)如第一种情况所示.

初始状态是最后一个参数([], N, K),你会得到包含所有三个值的结果,所以我使用模式results, _, _忽略的最后一个值i和k.

请注意,您的代码不完整,因此我无法运行代码段(可能存在错误!)但我希望它能够证明一般的想法.您也可以使用递归函数或递归序列表达式来实现相同的功能(在这两种情况下,您都会将状态保存在参数中,并且您可以在列表上使用模式匹配来处理空白或非空时的情况空).

使用递归序列表达式的方法可能更接近您的命令式版本:

let rec lookup (i, k) items = seq {
  match items with
  | [] -> ()
  | item::items ->
      match k - item.Size with
      // if size of i-th item is greater than current capacity...
      | x when x <  0 -> 
          // ... this means we haven't taken this item
          yield 0
          yield! lookup (i - 1, k) items
      // otherwise we've got two cases
      | x when x >= 0 -> 
          let v1 = combinations (i-1, !k) id
          let vc = combinations (i, !k) id
          if v1 = vc then 
            // case 1: item hasn't been taken
            yield 0
            yield! lookup (i - 1, k) items
          else
            yield 1
            yield! lookup (i - 1, x) items }