Free monad of Option<'t>

Nest.fs

/// Free monad of Option<'t>.
type Nest<'t> =

    /// Nested options.
    | Free of Option<Nest<'t>>

    /// Lifts a value directly into the monad.
    | Pure of 't

module Nest =

    /// Binds two nests together.
    let rec bind f = function
        | Free opt ->
            opt
                |> Option.map (bind f)   // try to pass the given function along
                |> Free
        | Pure value -> f value          // we're at the end: access the wrapped value

/// Workflow builder.
type NestBuilder() =
    member __.Bind(nest, func) = nest |> Nest.bind func
    member __.Return(value) = Pure value
    member __.ReturnFrom(value) = value

/// Workflow builder.
let nest = NestBuilder()

/// Lifts the given value into the monad as a two-level nest.
let some value =
    value |> Pure |> Some |> Free

/// Free (Some (Free (Some (Free (Some (Pure "ABC"))))))
let example1 =
    nest {
        let! a = some "A"
        let! b = some (a + "B")
        return! some (b + "C")
    }

/// Free (Some (Free (Some (Free None))))
let example2 =
    nest {
        let! a = some "A"
        let! b = some (a + "B")
        do! Free None
        return! some (b + "C")
    }

/// Output:
[<EntryPoint>]
let main argv =
    printfn "%A" example1
    printfn "%A" example2
    0