Maintaining state while walking a tree structure

Question

The following code creates a simple tree structure and then walks through the tree looking for node with the value 9 that appears after we have seen a node with the value 1 and a node with the value 4 (order of the 1 and 4 don't matter).

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

When I run it produces the correct output:

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

Is there a method to do this that threads the state through the recursive function calls rather than making it a mutable variable? The mutability is confined to my function but I keep thinking there must be a way to structure this that makes it unnecessary.

In real life the tree structure will be much larger, several thousand nodes and 10 levels deep, while the code has not run into any recursion limits yet are there improvements that would make this less likely?

Answer 1

At first step I've removed hardcoded into function input data, so it's become testable.

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

let walk n =
    ...
    walkImpl n

walk (Children ...)

Than get rid of type which exists only for one function and replaced it with anonymous record.

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

Afterwards comes hardest part of refactoring: remove mutability. In order to use mutable state in functional way we have to use recursion and pass state as parameter to function which must return updated state, so signature should be State -> State instead of () -> () (curNode omitted for clarity).

      | 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

Now we have part of function that matches over curNode and transforms state if Value branch is evaluated. We also must transfer state when walking across different children while iterating list. List.fold is function that iterates over list while keep tracking of state changes. All list function may be implemented with fold, such a powerful abstraction.

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

Now we have complete working example without mutations

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