5 people like it.

You might have heard that a "free" monad can be created from any functor. Unfortunately, that doesn't mean much if you're not already familiar with category theory. This example creates a free monad from a simple functor types

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: ``` ``````/// 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/ ``````
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member GetSlice : startIndex:int option * endIndex:int option -> 'T list
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
union case List.Cons: 'item * List<'item> -> List<'item>
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'item> =
| Cons of 'item * List<'item>
| Nil

Full name: Script.List<_>

Canonical list definition, just for comparison.
union case List.Nil: List<'item>
Multiple items

Just like Cons, but not recursive.

--------------------
| Link of 'item * 'tail
| Done

A link consists of an item followed by a tail of some type.

Just like Nil.
| Link of 'item * 'tail
| Done

A link consists of an item followed by a tail of some type.

An example of length 0.

An example of length 1.

An example of length 2.

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.
val f : ('a -> 'b)
val item : 'c
val tail : 'a
type Chain<'item,'next> =
| Pure of 'next

Full name: Script.Chain<_,_>

union case Chain.Free: Link<'item,Chain<'item,'next>> -> Chain<'item,'next>

Multiple items

Just like Cons, but not recursive.

--------------------

from Script

--------------------
| Link of 'item * 'tail
| Done

A link consists of an item followed by a tail of some type.
union case Chain.Pure: 'next -> Chain<'item,'next>

Lifts a value directly into the monad.
val bind : f:('a -> Chain<'b,'c>) -> _arg1:Chain<'b,'a> -> Chain<'b,'c>

Full name: Script.Chain.bind

Binds two chains together.
val f : ('a -> Chain<'b,'c>)
val next : 'a
Multiple items
type ChainBuilder =
new : unit -> ChainBuilder
member Bind : chain:Chain<'e,'f> * func:('f -> Chain<'e,'g>) -> Chain<'e,'g>
member Return : value:'c -> Chain<'d,'c>
member ReturnFrom : value:'b -> 'b
member Zero : unit -> Chain<'a,unit>

Full name: Script.ChainBuilder

Workflow builder for chains.

--------------------
new : unit -> ChainBuilder
member ChainBuilder.Bind : chain:Chain<'e,'f> * func:('f -> Chain<'e,'g>) -> Chain<'e,'g>

Full name: Script.ChainBuilder.Bind
val chain : Chain<'e,'f>
val func : ('f -> Chain<'e,'g>)
Multiple items
module Chain

from Script

--------------------
type Chain<'item,'next> =
| Pure of 'next

Full name: Script.Chain<_,_>

val __ : ChainBuilder
member ChainBuilder.Return : value:'c -> Chain<'d,'c>

Full name: Script.ChainBuilder.Return
val value : 'c
member ChainBuilder.ReturnFrom : value:'b -> 'b

Full name: Script.ChainBuilder.ReturnFrom
val value : 'b
member ChainBuilder.Zero : unit -> Chain<'a,unit>

Full name: Script.ChainBuilder.Zero
val chain : ChainBuilder

Full name: Script.chain

Workflow builder for chains.
val toChain : item:'a -> Chain<'a,unit>

Full name: Script.toChain

val item : 'a
val chainPlain : Chain<char,unit>

Full name: Script.chainPlain

Example: Creates a chain the verbose way.
val chainSugar : Chain<char,unit>

Full name: Script.chainSugar

Example: Creates a chain using the builder.
Multiple items
type EntryPointAttribute =
inherit Attribute
new : unit -> EntryPointAttribute

Full name: Microsoft.FSharp.Core.EntryPointAttribute

--------------------
new : unit -> EntryPointAttribute
val main : argv:string [] -> int

Full name: Script.main

These two chains are the same.

Output: