c# - 递归 C# 函数从 for 循环内部返回 - 如何转换为 F#？

Question

资深 C# 开发人员，正在学习 F#。我选择了一段相当实用的 C# 代码，我将其作为学习练习编写 - 将其转换为 F#。我阅读了大量有关函数式编程的书籍，并定期使用 C# 中的函数结构，但我只花了几个小时就开始学习 F#。

此函数是解决类似于“LonPos 101”谜题的程序的一部分，您可以在亚马逊等网站上找到该程序。求解器中使用的策略是基于识别谜题空间中只有 30 个有效位置，因此“到目前为止的解决方案”可以用一个整数表示，并且每件作品的每个有效位置也可以用一个整数表示，并且完整的解决方案是一个包含 7 件作品中每件作品的一个可能位置的集合，其中7 个部分的“重量”加起来就是解决方案的重量 (2^30-1)。在给定的函数中，“key”是棋子的“主键”，wbk 是“键的权重”——由键索引，包含相应棋子的有效位置列表，而“w”是前面提到的“解决方案” -至今”。返回值是从键到所选位置的映射，并填充在成功递归导致解决方案的退出路径上。我在开发 C# 解决方案时发现，将其设为排序列表会使解决方案查找器的速度提高一个数量级，但它对于普通列表同样有效。

这是我遇到问题的 C# 函数:

int solutionWeight;

Dictionary<int,int> Evaluate(int w, Dictionary<int, SortedSet<int>> wbk, int key)
{
  if (w == solutionWeight)
    return new Dictionary<int, int>();  

  if (key == 8)
    return null;

  foreach (var w2 in wbk[key])
  {
    if ((w & w2) != 0)
      continue;
    var s = Evaluate(w | w2, wbk, key + 1);
    if (s != null)
    {
      s.Add(key, w2);
      return s;
    }
  }

  return null;
}

这是我对 F# 版本的尝试 - 它可以编译，但不能正常工作 - 当执行 w 不是 solutionWeight 且 key 是等于 8。我不明白为什么在这种情况下甚至要执行这行代码，但是...

    let rec Evaluate(w:int, wbk:Dictionary<int, SortedSet<int>>, key:int):Dictionary<int,int> =
    if w = solutionWeight then 
        Dictionary<int,int>()
    else if key = 8 then 
        null
    else
        // ... this is wrong - runs off the end of some collection - fails with key not found exception
        let ws = wbk.[key] |> Seq.filter (fun w2 -> (w2 &&& w) = 0) 
        /// ... for some reason, execution resumes here after the key = 8 clause above
        let ss = ws |> Seq.map (fun w -> (w,Evaluate(w, wbk, key+1))) 
        let sw = ss |> Seq.find (fun sw -> snd sw <> null) 
        let s = snd sw 
        s.Add(key, fst sw)
        s

给我指明正确的方向!我的下一次尝试将首先以更函数式的风格重写 C# 代码，但感觉这个版本即将运行(虽然可能离惯用的 F# 还很远)。

更新:

我重新编写了 F# 函数，通过使用一对相互递归的函数来消除循环。它确实有效，但比非相互递归的 C# 版本慢 ~2 倍。

let rec Evaluate(w:int, wbk:Dictionary<int, SortedSet<int>>, key:int):Dictionary<int,int> =
    if w = solutionWeight then 
        Dictionary<int,int>()
    else if key = 8 then 
        null
    else
        EvalHelper(w, wbk, key, wbk.[key].GetEnumerator())

and EvalHelper(w:int, wbk:Dictionary<int, SortedSet<int>>, key:int, ws:IEnumerator<int>):Dictionary<int,int> =
    if ws.MoveNext() then
        let w2 = ws.Current
        if (w &&& w2) = 0 then
            let s = Evaluate(w ||| w2, wbk, key+ 1)
            if s <> null then
                s.Add(key, w2)
                s
            else
                EvalHelper(w, wbk, key, ws)
        else
            EvalHelper(w, wbk, key, ws)
    else
        null

我怎样才能进一步改进它？

更新:我对它进行了更多调整 - 感觉有点像 F#，但我仍然觉得我应该能够摆脱更多类型注释并更多地使用 F# native 类型。这是一项正在进行的工作。

let rec Evaluate(w, wbk:Dictionary<int, SortedSet<int>>, key):Dictionary<int,int> option =
    let rec EvalHelper(ws) =
        match ws with
        | w2 :: mws ->
            match w &&& w2 with
            | 0 ->
                let s = Evaluate(w ||| w2, wbk, key+ 1)
                match s with
                | None -> EvalHelper(mws)
                | Some s ->
                    s.Add(key, w2)
                    Some(s)
            | _ -> EvalHelper(mws)
        | _ ->
            None

    if w = solutionWeight then 
        Some (Dictionary<int,int>())
    else if key = 8 then 
        None
    else
        EvalHelper(List.ofSeq wbk.[key])

Answer 1

翻译这个函数的关键是把 for 循环变成递归，如第一次更新所示。

let rec Evaluate(w:int, wbk:Dictionary<int, SortedSet<int>>, key:int):Dictionary<int,int> =
    if w = solutionWeight then 
        Dictionary<int,int>()
    else if key = 8 then 
        null
    else
        EvalHelper(w, wbk, key, wbk.[key].GetEnumerator())

and EvalHelper(w:int, wbk:Dictionary<int, SortedSet<int>>, key:int, ws:IEnumerator<int>):Dictionary<int,int> =
    if ws.MoveNext() then
        let w2 = ws.Current
        if (w &&& w2) = 0 then
            let s = Evaluate(w ||| w2, wbk, key+ 1)
            if s <> null then
                s.Add(key, w2)
                s
            else
                EvalHelper(w, wbk, key, ws)
        else
            EvalHelper(w, wbk, key, ws)
    else
        null

随后的更新只是稍微清理了样式 - 使其更接近惯用的 F#。

let rec Evaluate(w, wbk:Dictionary<int, SortedSet<int>>, key):Dictionary<int,int> option =
    let rec EvalHelper(ws) =
        match ws with
        | w2 :: mws ->
            match w &&& w2 with
            | 0 ->
                let s = Evaluate(w ||| w2, wbk, key+ 1)
                match s with
                | None -> EvalHelper(mws)
                | Some s ->
                    s.Add(key, w2)
                    Some(s)
            | _ -> EvalHelper(mws)
        | _ ->
            None

    if w = solutionWeight then 
        Some (Dictionary<int,int>())
    else if key = 8 then 
        None
    else
        EvalHelper(List.ofSeq wbk.[key])