Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
F# State Monad implementation for n-ary tree (based on "The Zen of Stateless State" video by Brian Beckman)
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
@halfAbee

This comment has been minimized.

Copy link

@halfAbee halfAbee commented Apr 16, 2015

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.