F# State Monad implementation for n-ary tree (based on "The Zen of Stateless State" video by Brian Beckman)

NaryTreeStateMonad

open System

type Tree<'a> =
    | Leaf of 'a
    | Branch of Tree<'a> list

type StateMonad<'state, 'content> = StateMonad of ('state -> ('state * 'content))

let testTree = 
    Branch [
        Leaf "Mike"
        Branch [
            Leaf "Car"
            Leaf "Door"
            Branch [
                Branch [
                    Leaf "Woof"
                ]
                Branch [
                    Leaf "Foo"
                    Leaf "Baar"
                    Leaf "Ding"
                ]
                Leaf "ALing"
            ]
        ]
        Leaf "Doh"
        Branch [
            Leaf "Flanders"
            Leaf "Stupid"
        ]
    ]

let wrap content = StateMonad (fun state -> (state, content))

let bind monad monadMaker = 
    StateMonad (fun state -> 
        let (StateMonad monadFunction) = monad
        let (state1, content1) = monadFunction state
        let (StateMonad newMonad) = monadMaker content1
        newMonad state1
    )

let updateState = StateMonad (fun state -> (state + 1, state))

let rec makeMonad tree =
    match tree with
    | Leaf content -> bind updateState (fun currentState -> wrap <| Leaf(currentState, content))
    | Branch leaves -> 
        let folder monadList leaf =
            bind monadList (fun list -> bind (makeMonad leaf) (fun lLeaf -> wrap <| lLeaf::list))
        let monadList = leaves.Tail |> List.fold folder (bind (makeMonad leaves.Head) (fun head -> wrap [ head ]))
        bind monadList (fun labelledLeaves -> Branch (List.rev labelledLeaves) |> wrap)

let printTree tree = 
    let rec printTreeWithIndent indent tree =
        let indentStr = new System.String(' ', indent)
        match tree with
        | Leaf content -> printfn "%s|───%A" indentStr content
        | Branch leaves ->
            printfn "%s|───\\" indentStr
            leaves |> List.iter (printTreeWithIndent (indent + 4))
    printTreeWithIndent 0 tree

[<EntryPoint>]
let main argv = 
    printTree testTree
    Console.WriteLine()
    Console.WriteLine("--------")
    Console.WriteLine()
    let (StateMonad (monad)) = makeMonad testTree
    let state, tree = monad 0
    printTree tree

    Console.WriteLine()
    Console.WriteLine("DONE")

    Console.ReadLine() |> ignore
    0 // return an integer exit code

As an early adopter of Channel 9 videos, I have always enjoyed the contributions of Brian (and Erik Meijer) as they cropped up over the years.

I thank iskeld for this splendid translation of Brian's thoughts into F#. I watched the original video when it came out, and I couldn't be bothered actually trying to run (as opposed to just viewing) the Haskell or C# code.

I have just spent most of the last year trying to get better at F# and the functional mindset, and your code above got me out of a corner on a recent stumble.

Someone at Microsoft should find a way to get Brian and Erik to promote F#. (despite E's stated views since leaving MS), I believe they both know that F# is and could be an even better force for good.