实现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是内函子范畴中的么半群，有什么问题吗？”:)

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的最后一个值。

请注意，您的代码不完整，因此我无法运行代码片段(可能有bug！)但我希望它能说明一般的想法。您也可以使用递归函数或递归序列表达式来实现相同的功能(在这两种情况下，您都可以将状态保存在参数中，并在列表为空或非空时使用模式匹配来处理这种情况)。

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

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 }