Skip to content

Instantly share code, notes, and snippets.

@madidier
Last active July 16, 2017 11:15
Show Gist options
  • Save madidier/84e21607d00a4705e0da73e50fd8f592 to your computer and use it in GitHub Desktop.
Save madidier/84e21607d00a4705e0da73e50fd8f592 to your computer and use it in GitHub Desktop.
Oh, god ! I did it !
module Typeclass
type __<'f, 'a> = interface end
// __<fμ, 'a> -> f<'a>
let inline ω (x: __<'f, 'a>) = (^f: (static member ω : __<'f, 'a> -> 'b) x)
// f<'a> -> __<fμ, 'a>
let inline μ (x: 'a) = (x :> __<'f, 'b>)
// A more constrained version that may help type inference
let inline ω'< ^f, ^a, ^b when ^f : (static member ω : __<'f, 'a> -> 'b)
and ^b :> __<'f, 'a> >
(x: __<'f, 'a>) = ω x
type Functor<'f> =
abstract Map : ('a -> 'b) -> __<'f, 'a> -> __<'f, 'b>
let inline map f (x: __<'f, 'a>)
= ω <| (^f: (static member Functor : Functor<'f>) ()).Map f x
type Applicative<'f> =
inherit Functor<'f>
abstract Pure : 'a -> __<'f, 'a>
abstract Ap : __<'f, 'a -> 'b> -> __<'f, 'a> -> __<'f, 'b>
let inline pure' (x: 'a) : 'b
= ω' <| (^f: (static member Applicative : Applicative<'f>) ()).Pure x
let inline ap (f: __<'f, 'a -> 'b>) (x: __<'f, 'a>)
= ω <| (^f: (static member Applicative : Applicative<'f>) ()).Ap f x
type Monad<'f> =
inherit Applicative<'f>
abstract Bind : __<'f, 'a> -> ('a -> #__<'f, 'b>) -> __<'f, 'b>
let inline bind (x: __<'f, 'a>) (f: 'a -> #__<'f, 'b>)
= ω <| (^f: (static member Monad : Monad<'f>) ()).Bind x f
[<AbstractClass>]
type ApplicativeBuilder<'f>() =
abstract Pure : 'a -> __<'f, 'a>
abstract Ap : __<'f, 'a -> 'b> -> __<'f, 'a> -> __<'f, 'b>
interface Applicative<'f> with
member this.Map f x = this.Ap (this.Pure f) x
member this.Pure x = this.Pure x
member this.Ap f x = this.Ap f x
[<AbstractClass>]
type MonadBuilder<'f>() =
inherit ApplicativeBuilder<'f>()
abstract Bind : __<'f, 'a> -> ('a -> #__<'f, 'b>) -> __<'f, 'b>
override this.Ap f x = this.Bind f <| fun f' -> (this :> Functor<_>).Map f' x
interface Monad<'f> with
member this.Bind x f = this.Bind x f
[<Sealed>]
type LinkedListμ private () =
static member ω (x: __<LinkedListμ, 'a>)
= x :?> LinkedList<'a>
and LinkedList<'a> =
| Empty
| Cons of ('a * LinkedList<'a>)
interface __<LinkedListμ, 'a>
let rec concat xs ys =
match xs with
| Empty -> ys
| Cons(x, xs') -> Cons(x, concat xs' ys)
let rec fromList = function
| x :: xs -> Cons(x, fromList xs)
| [] -> Empty
type LinkedListμ with
static member Functor = LinkedListμ.Monad :> Functor<_>
static member Applicative = LinkedListμ.Monad :> Applicative<_>
static member Monad =
{
new MonadBuilder<LinkedListμ>() with
member this.Pure x = Cons(x, Empty) |> μ
member this.Bind xs f =
match ω xs with
| Empty -> Empty
| Cons(x, xs') -> concat (ω <| f x) (bind xs' f)
|> μ
} :> Monad<_>
let x : LinkedList<int> = pure' 1
printfn "%A" <| bind (pure' 42) (fun n -> fromList [n; n * 2])
// Let's bring Haskell's do notation too!
type MonadComputationBuilder() =
member inline this.Return x = pure' x
member this.ReturnFrom x = x
member inline this.Bind(x, f) = bind x f
let monad = new MonadComputationBuilder()
printfn "%A" <| monad {
let! a = fromList [1..10]
let! b = fromList [a..10]
let! c = fromList [b..10]
if a * a + b * b = c * c
then return a, b, c
else return! fromList []
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment