/// Canonical list definition, just for comparison. type List<'item> = | Cons of 'item * List<'item> | Nil /// A link consists of an item followed by a tail of some type. type Link<'item, 'tail> = /// Just like Cons, but not recursive. | Link of 'item * 'tail /// Just like Nil. | Done module Link = /// An example of length 0. let example0 = Done /// An example of length 1. let example1 = Link ('A', Done) /// An example of length 2. let example2 = Link ('A', Link ('B', Done)) /// We can map over a link (which means it's a functor). Since the item /// and the tail are two different types, we choose to leave the item /// alone and map over the tail. let map f = function | Link (item, tail) -> Link (item, f tail) | Done -> Done /// A recursive chain of links (i.e. its free monad). type Chain<'item, 'next> = /// Link's "fixed point". | Free of Link<'item, Chain<'item, 'next>> /// Lifts a value directly into the monad. | Pure of 'next module Chain = /// Binds two chains together. let rec bind f = function | Free link -> link |> Link.map (bind f) // pass the given function along to the next link |> Free | Pure next -> f next // we're at the end: glue the two chains together /// Workflow builder for chains. type ChainBuilder() = member __.Bind(chain, func) = chain |> Chain.bind func member __.Return(value) = Pure value member __.ReturnFrom(value) = value member __.Zero() = Pure () /// Workflow builder for chains. let chain = ChainBuilder() /// Creates a one-link chain with the given item, ready for binding. let toChain item = Free (Link (item, Pure ())) /// Example: Creates a chain the verbose way. let chainPlain = toChain 'A' |> Chain.bind (fun () -> toChain 'B') // replace chain A's tail with chain B /// Example: Creates a chain using the builder. let chainSugar = chain { do! toChain 'A' do! toChain 'B' return () } /// These two chains are the same. /// /// Output: /// Free (Link ('A', Free (Link ('B', Pure ())))) /// Free (Link ('A', Free (Link ('B', Pure ())))) [] let main argv = printfn "%A" chainPlain printfn "%A" chainSugar 0 // For more information: // * http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html // * https://blog.ploeh.dk/2017/08/07/f-free-monad-recipe/