Алгоритм откат в F #: Как работает неизменяемость?

Question

Хорошо, таким образом я пытаюсь написать алгоритм поиска с возвратом, который может принимать входной сигнал, как:

0 2 3 1 (top-right location, length, horizontal or vertical) 
1 0 4 0 
2 2 4 0 
1 3 3 1 
top (the actual words) 
that 
toga 
cat 

И выплюнуть кроссворд, как:

**c*** 
that** 
**toga 
***p** 

код, который я до сих пор:

//prints the puzzle 
let printPuzzle (puzzle : char[,]) = 
    printfn "%s" "" 
    printfn "%A" puzzle 
    printfn "%s" "" 

//checks if the words fits 
let rec doesItFit place (puzzle : char[,]) (word : seq<char>) = 
    let (row, col, length, isVertical) = place 
    if length <> (Seq.length word) then 
     (puzzle, false) 
    else 
     match (Seq.toList word) with 
     | [] -> (puzzle, true) 
     | letter::rest -> 
      printfn "%c" letter 
      printPuzzle puzzle 
      if isVertical = 0 then 
       if puzzle.[row, col] = '*' || puzzle.[row, col] = letter then 
        puzzle.[row, col] <- letter 
        doesItFit (row, col+1, length-1, isVertical) puzzle rest 
       else 
        (puzzle, false) 
      else 
       if puzzle.[row, col] = '*' || puzzle.[row, col] = letter then 
        puzzle.[row, col] <- letter 
        doesItFit (row+1, col, length-1, isVertical) puzzle rest 
       else 
        (puzzle, false) 

//the actual backtracking algorithm... goes through all places and all words 
//trying to make stuff fit 
let rec sort words places (puzzle : char[,]) = 
    match places with 
    | [] -> (puzzle, true) 
    | place::rest -> 
     let rec checkWords words place puzzle = 
      match words with 
      | [] -> 
       printfn "%s" "failure, backtracking" 
       puzzle, false 
      | word::otherWords -> 
       let attempt = doesItFit place puzzle word 
       if snd attempt then 
        printfn "%s" "success, entering if block" 
        let nextLevel = sort words rest (fst attempt) 
        if (snd nextLevel) then 
         nextLevel 
        else 
         checkWords otherWords place puzzle 
       else 
        checkWords otherWords place puzzle 
     checkWords words place puzzle 

//line for testing 
printPuzzle (fst (sort ["cat"; "that"; "toga"; "top"] [(0, 2, 3, 1); (1, 0, 4, 0); (2, 2, 4, 0); (1, 3, 3, 1)] (Array2D.create 6 6 '*')));; 

Вот результат от запуска тестовой линии:

c 

[['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

a 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['*'; '*'; 'a'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

success, entering if block 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['*'; '*'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

h 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; '*'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

a 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

success, entering if block 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

h 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

a 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

success, entering if block 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

o 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

o 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

o 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

I думаю моя проблема в том, что я не уверен, как неизменяемость работает в F #. Похоже, что моя программа делает это, когда головоломка проходит после неудачной попытки, головоломка была изменена. Это не имеет большого значения для меня, поскольку я думал, что F # не позволит его изменить. Я бы хотел объяснить, почему этот код использует измененную головоломку при тестировании слова после отступления, а не оригинальную, немодифицированную головоломку.

Answer 1

Ваш код использует изменяемый массив char[,] представлять загадку, так что, когда вы мутировать его в doesItFit функции (с помощью оператора <-), вы на самом деле изменения состояния объекта. Когда код возвращается из функции doesItFit, массив изменился.

Есть по существу три пути решения проблемы:

• Используйте неизменные типов для представления головоломки - если вы используете F # список (список списков), чтобы представить головоломки, то вы не можете мутировать его (потому что списки являются неизменными), и поэтому вы не попадаете в эту ситуацию.

• Клонировать объекты по мере необходимости - вам не нужно использовать неизменяемые типы для написания кода в функциональном стиле. Просто клонируйте массив, прежде чем передавать его функции, которая может мутировать ее. Вы можете использовать для этого Array.copy.

• Восстановление состояние перед возвратом - когда функция терпит неудачу, он должен отменить все изменения
  (Это не чисто функциональный подход, но это могло бы быть более эффективным, - думать об этом как оптимизация)