sequence in OCaml

module type Monad = sig
    type 'a t
    val map : ('a -> 'b) -> 'a t -> 'b t
    val pure : 'a -> 'a t
    val bind : 'a t -> ('a -> 'b t) -> 'b t
end

module Sequence (M : Monad) : sig
    val sequence : 'a M.t list -> 'a list M.t
end = struct
    let rec sequence = function
        | [] -> M.pure []
        | x :: xs -> M.bind x (fun x' -> M.map (fun xs' -> x' :: xs')
                                               (sequence xs))
end

module Option_monad : Monad with type 'a t = 'a option = struct
    type 'a t = 'a option
    let map f = function
        | None -> None
        | Some x -> Some (f x)
    let pure x = Some x
    let bind x k = match x with
        | None -> None
        | Some x' -> k x'
end

module Option_sequence = Sequence (Option_monad)

let dump = function
    | Some x -> print_endline ("Some [" ^ String.concat "; " (List.map string_of_int x) ^ "]")
    | None -> print_endline "None"

let () =
    let open Option_sequence in
    dump (sequence [Some 1; Some 2; Some 3]);
    dump (sequence [Some 1; None; Some 3])