来自 for 循环内部的递归 C# 函数 returns - 如何转换为 F#？

Question

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

此函数是解决类似于 "LonPos 101" 的程序的一部分，您可以在 Amazon 等网站上找到该程序。求解器中使用的策略是基于认识到只有 30 个有效位置拼图 space，所以 "solution so far" 可以用一个整数表示，每块的每个有效位置也可以用一个整数表示，完整的解决方案是包含一个可能位置的集合来自 7 件中的每件，其中 7 件中的 "weights" 加起来等于解决方案权重 (2^30-1)。在给定的函数中，"key" 是棋子的 "primary key"，wbk 是 "weights by key" - 由键索引，包含相应棋子的有效位置列表，而 "w"就是前面提到的"solution-so-far"。 return 值是从键到所选位置的映射，并填充在成功递归导致解决方案的退出路径上。我在开发 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#ish，但我仍然觉得我应该能够摆脱更多类型注释并更多地使用 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])

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

来自 for 循环内部的递归 C# 函数 returns - 如何转换为 F#？

Recursive C# function returns from inside a for-loop - how to translate to F#?

c#

f#

loops

return

c#-to-f#