Сохранение состояния при хождении по древовидной структуре

Следующий код создает простую древовидную структуру, а затем проходит по дереву в поисках узла со значением 9, который появляется после того, как мы увидели узел со значением 1 и узел со значением 4 (порядок 1 и 4 не иметь значение).

type N = Value of int  | Children of N list
type S = {oneFound:bool; fourFound:bool}

let walk () =
    let mutable state = {oneFound = false; fourFound = false}
    let rec walkImpl curNode =
        match curNode with
        | Value n ->    match n with
                        | 1 -> state <- {state with oneFound = true }
                        | 4 -> state <- {state with fourFound = true }
                        | 9 -> if state.oneFound && state.fourFound then
                                printfn "Found a good 9"
                               else 
                                printfn "Found a bad 9"
                        | _ -> () 
                        printfn "Node value %d" n
        | Children c -> c |> List.iter (fun n -> walkImpl n)
    walkImpl (Children [Value 1; Value 2 ; Children [Value 9; Children [Value 4; Value 5]; Value 9]])
    
walk ()

Когда я запускаю, он дает правильный результат:

Node value 1
Node value 2
Found a bad 9
Node value 9
Node value 4
Node value 5
Found a good 9
Node value 9

Есть ли способ сделать это, который передает состояние через рекурсивные вызовы функций, а не делает его изменяемой переменной? Изменчивость ограничена моей функцией, но я продолжаю думать, что должен быть способ структурировать это, чтобы сделать это ненужным.

В реальной жизни древовидная структура будет намного больше, несколько тысяч узлов и 10 уровней в глубину, в то время как код не выходит за рамки каких-либо ограничений рекурсии, но есть ли улучшения, которые уменьшили бы это?

На первом этапе я удалил жестко закодированные входные данные функции, чтобы их можно было проверить.

   ...
   walkImpl (Children [Value 1; Value 2 ; Children [Value 9; Children [Value 4; Value 5]; Value 9]])
    
walk ()

let walk n =
    ...
    walkImpl n

walk (Children ...)

Затем избавьтесь от типа, который существует только для одной функции, и замените его на анонимная запись.

    let initialState = {| oneFound = false; fourFound = false |}

Затем следует самая сложная часть рефакторинга: удалить изменчивость. Чтобы использовать изменчивый в функциональном состоянии, мы должны использовать рекурсию и передавать состояние в качестве параметра функции, которая должна возвращать обновленное состояние, поэтому подпись должна быть State -> State вместо () -> () (curNode опущено для ясности).

      | Value n ->
            let patched =
                match n with
                | 1 -> {| state with oneFound = true |}
                | 4 -> {| state with fourFound = true |}
                | 9 ->
                    if state.oneFound && state.fourFound then
                        printfn "Found a good 9"
                    else
                        printfn "Found a bad 9"
                    state
                | _ -> state
            printfn "Node value %d" n
            patched

Теперь у нас есть часть функции, которая соответствует более чем curNode и преобразует state если Value ветка оценивается. Мы также должны передать state при прохождении по разным детям при повторении списка. List.fold — это функция, которая выполняет итерацию по списку, отслеживая изменения состояния. Вся функция списка может быть реализована с помощью свертки, такой мощной абстракции.

        | Children c -> c |> List.fold walkImpl state

Теперь у нас есть полный рабочий пример без мутаций.

type N = Value of int  | Children of N list

let walk n =
    let rec walkImpl (state : {| oneFound: bool; fourFound: bool |}) curNode = // explicit type required here
        match curNode with
        | Value n ->
            let patched =
                match n with
                | 1 -> {| state with oneFound = true |}
                | 4 -> {| state with fourFound = true |}
                | 9 ->
                    if state.oneFound && state.fourFound then
                        printfn "Found a good 9"
                    else
                        printfn "Found a bad 9"
                    state
                | _ -> state
            printfn "Node value %d" n
            patched
        | Children c ->
            c |> List.fold walkImpl state

    let initialState = {| oneFound = false; fourFound = false |}
    walkImpl initialState n
    |> ignore // don't care about state, because it's for internal use only

[<EntryPoint>]
let main argv =
    walk (Children [Value 1; Value 2 ; Children [Value 9; Children [Value 4; Value 5]; Value 9]])
    0