Emulating higher kinds with F# inline functions.

MonadExamples.fs

(* F# lacks proper support for higher-kinded abstraction such as ML
functors or Haskell typeclasses. In particular it makes it seemingly 
impossible to define functions that work for every type constructor.
The code below demonstrates that this functionality can be partially
recovered by using inline functions with static member constraints.
The approach requires explicitly passing typeclass instance values.
Error messages and derived types are horrible. Nonetheless, there is
some type safety - if the typeclass instances have been defined right,
type-unsafe code will be rejected by the typechecker, albeit with a
hairy message. Another disadvantage is the need to invent operators. *)

type ListFunctor = | ListFunctor with
    static member ( >--> ) (ListFunctor, (f, x)) = List.map f x

type OptionFunctor = | OptionFunctor with
    static member ( >--> ) (OptionFunctor, (f, x)) = Option.map f x

type OptionMonad = | OptionMonad with
    static member (|!!|) (OptionMonad, x)       = Some x
    static member (|>>=|) (OptionMonad, (x, f)) = Option.bind f x

type ListMonad = | ListMonad with
    static member (|!!|) (ListMonad, x)       = [x]
    static member (|>>=|) (ListMonad, (x, f)) = List.collect f x

let inline fmap def f x =
    def >--> (f, x)

let inline ret monad x =
    monad |!!| x

let inline bind monad x f =
    monad |>>=| (x, f)

/// sequence : ('m :> Monad) -> List<'m<'a>> -> 'm<List<'a>>
let inline sequence monad ms =
    let k e es =
        bind monad e (fun x ->
            bind monad es (fun xs ->
                ret monad (x :: xs)))
    List.foldBack k ms (ret monad [])

/// mapM : ('m :> Monad) -> ('a -> 'm<'b>) -> List<'a> -> 'm<List<'b>>
let inline mapM monad f xs =
    sequence monad (List.map f xs)

let test () =
    let f = mapM OptionMonad (fun x -> if x % 2 = 0 then Some (x / 2) else None)
    printfn "%A" (f [2; 4; 6])
    printfn "%A" (f [1; 2; 3])