How to lift a value into a monad

Question

I'm trying to use the Writer monad in OCaml.

module Writer : Monad = struct
  type 'a t = 'a * string

  let return x = (x, "")

  let (>>=) m f =
    let (x, s1) = m in
    let (y, s2) = f x in
    (y, s1 ^ s2)
end

The statement below works.

Writer.(>>=) (Writer.return 2) (fun x -> Writer.return 1);;

But the statement below does not.

Writer.(>>=) (Writer.return 2) (fun x -> (x, "inc"));;
Error: This expression has type 'a * 'b but an expression was expected of type
  'c Writer.t

I tried

Writer.(>>=) (Writer.return 2) (fun x -> ((x, "inc") : int Writer.t))
Error: This expression has type 'a * 'b but an expression was expected of type
  int Writer.t

What am I doing wrong here? How can I lift a value into a monad in OCaml?

Answer 1

As mentioned, the code works with:

Writer.(>>=) (Writer.return 2) (fun x -> Writer.return 1);;

This is because the signature that describes the monad, here Monad, probably has this form:

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

As the concrete implementation of 'a t is not yet known (the type module potentially serving several implementations), 'a t is "abstract".

One approach would therefore be to "de-abstract" it.

This is possible by reflecting in the signature of the Writer module that we want to implement the Monad module while not making the type 'a t abstract, in this way:

module Writer : Monad with type 'a t = 'a * string = struct
  type 'a t = 'a * string

  let return x = (x, "")

  let (>>=) m f =
    let (x, s1) = m in
    let (y, s2) = f x in
    (y, s1 ^ s2)
end

In this way, the type `'a t' will no longer be abstract.

As a side note, I personally think it's not particularly bad that the Writer (or Reader, or State) type is abstract. The fact that it's a couple seems to me to be an implementation detail, some piping that doesn't need to be leaked.

Answer 2

You're constraining your monad implementation to be a Monad but, in fact, you want its type to have the Writer signature. To put it in other words, you're upcasting your implementation and forgetting that it also have to implement operations specific to the Writer monad. Obviously, this renders your Writer monad useless as you can't write anything.

To get it fixed, we first need to define the Writer module type, a common definition might look something like this,

module type Writer = sig
    type state
    val write : state -> unit t
    val read : 'a t -> state t
    val listen : 'a t -> ('a * state) t
    val exec : unit t -> state
    include Monad with type 'a t := 'a t
  end

Now you need to implement the newly added operations with the state type set to string and then you will be able to use your Writer monad without breaking its abstraction,

module Writer : Writer with type state = string = struct
  type state = string
  type 'a t = 'a * string

  let return x = (x, "")

  let (>>=) m f =
    let (x, s1) = m in
    let (y, s2) = f x in
    (y, s1 ^ s2)

  let write x = (),x
  let read (_,x) = x
  let listen (x,s) = ((x,s),s)
  let exec (_,x) = x
end

There are few libraries that implement monads in OCaml, so you don't need to re-invent it by your own. You can try the monads library that we develop at CMU. It could be installed with

opam install monads

Answer 3

A more fundamental issue is that the signature constraint

module Any_monad : Monad

is almost always a mistake in OCaml.

Signature constraints remove information that stick out of the signature. Thus, after the constraint, Any_monad could be replaced by any other monads fulfilling the monad signature (if we temporarily exclude side-effectful monads). For instance, you could replace the Writer monad with this very useful monad:

module Nil = struct
  type 'a t = unit
  let bind x f = ()
  let (>>=) = bind
  let return x = ()
end

In other words, an useful monad needs to have functions that are not part of the monad interface. In the case of the Writer monad that would be a write function:

module Writer: sig
  include Monad
  val write: string -> unit t
  val read: 'a t -> string
end = struct
  ...
end

Notice that we have extended the signature before using it as a constraint. Once, those functions available, your original code can be rewritten as:

Writer.(return 2 >>= fun x -> write "inc" >>= fun () -> return x)