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

Question

Long time C# developer, learning F#. I picked a fairly functional-styled bit of C# code that I'd written as a learning exercise - translate it to F#. I've done a lot of reading about functional programming and use the functional constructs in C# regularly, but I'm only a few hours into learning F#.

This function is part of a program that solves a puzzle similar to "LonPos 101" which you can find on Amazon, etc. The strategy used in the solver was based on recognizing that there are only 30 valid positions in the puzzle space, so a "solution so far" could be represented by a single integer, and every valid position of each piece could also be represented by a single integer and that a complete solution is a set containing one possible position from each of the 7 pieces where the "weights" of the 7 pieces add up to the solution weight (2^30-1). In the given function, "key" is the "primary key" of the piece, wbk is "weights by key" - indexed by key, containing a list of valid positions for the corresponding piece, while "w" is the aforementioned "solution-so-far". The return value is a map from key to chosen position and is filled-in on the exit path from a successful recursion that resulted in a solution. I found when developing the C# solution that making this a sorted list made the solution finder an order of magnitude faster, but it's equally valid with an ordinary list.

Here's the C# function I'm having trouble with:

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;
}

Here's my attempt at an F# version - it compiles, but it doesn't work correctly - it ends up failing with a KeyNotFoundException in the let ss=... line when executing the case where w is not solutionWeight and key does equal 8. It makes no sense to me why this line of code is even being executed in this case, but...

    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

Point me in the right direction! My next attempt will be to re-write the C# code in a more functional style first, but it feels like this version is on the verge of working (while perhaps still far from idiomatic F#).

UPDATE:

I re-wrote the F# function to eliminate the loop by using a pair of mutually recursive functions. It does work, but it's ~2X slower than the non-mutually-recursive C# version.

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

How can I further improve it?

UPDATE: I tweaked it more - feeling a bit more F#ish, but I still feel like I should be able to get rid of more type annotations and use F# native types more. It's a work in progress.

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

The key to translating this function was to turn the for loop into recursion, as shown in the first update.

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

The subsequent update just cleaned up the style a bit - pushed it a little closer to idiomatic 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])