递归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 ss = ...行中失败并且出现KeyNotFoundException.对我来说,为什么这行代码甚至在这种情况下被执行是没有意义的,但......

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