Free monad interpreter in F# (based on: http://programmers.stackexchange.com/a/242803/145941)

Free.fsx

type DSL<'next> =
    | Get of string * (string -> 'next)
    | Set of string * string * 'next
    | End
    with static member fmap f = function
                | Get (k, c)    -> Get (k, f << c)
                | Set (k, v, c) -> Set (k, v, f c)
                | End           -> End

type FreeDSL<'a> =
    | Free   of DSL<FreeDSL<'a>>
    | Return of 'a
    with static member fmap f x =
            let rec go = function
                | Return a -> Return (f a)
                | Free  fa -> Free (DSL<FreeDSL<'a>>.fmap go fa)
            go x

let ex1 = Set ("alma", "bela", (Get ("alma", (fun s -> End))))
let exF1 = Free (Set ("alma", "bela", (Free (Get ("alma", (fun s -> Return End))))))

let flip f a b = f b a

let rec bindFreeDSL<'a, 'b> (ma : FreeDSL<'a>) (f : 'a -> FreeDSL<'b>) =
    match ma with
    | Return x -> f x
    | Free dsl -> Free (DSL<FreeDSL<'a>>.fmap ((flip bindFreeDSL) f) dsl)

type FreeDSLBuilder () =
    member this.Return = Return
    member this.ReturnFrom x = x
    member this.Bind (ma, f) = bindFreeDSL ma f

let domain = FreeDSLBuilder ()

let liftFreeDSL (action : DSL<'a>) = Free (DSL<FreeDSL<'a>>.fmap Return action)

let get key       = liftFreeDSL (Get (key, id))
let set key value = liftFreeDSL (Set (key, value, ()))
let end'<'a>      = liftFreeDSL End

let exF2 = domain.Bind(set "foo" "bar", (fun _ -> get "foo"))

let app<'a> = domain {
    do! set "foo" "bar"
    let! value = get "foo"
    do! set "x" value
    return! end'
}

// val it : FreeDSL<obj> =
//   Free (Set ("foo","bar",Free (Get ("foo",<fun:fmap@11-1>))))