OCaml Monadic Buffers

Implementing Monadic Buffers

This is our implementation of monadic buffers. It has a typical monad signature, the type α MonadicBuffer.t

represents the current computation, giving a value of the type α

that can be written to the buffer as a side effect. A unit MonadicBuffer.t

then represents the completed computation. Monadic functions add_string

and add_char

can be used to write to a monadic buffer, and contents

encodes the pattern you describe.

module MonadicBuffer : sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
  val add_char : char -> unit t
  val add_string : string -> unit t
  val contents : int -> unit t -> string
  val lift : ('a -> 'b) -> ('a t -> 'b t)
  val ( >>= ) :'a t -> ('a -> 'b t) -> 'b t
  val ( >> ) : 'a t -> 'b t -> 'b t
end = struct

  type 'a t = Buffer.t -> 'a

  let return x =
    fun _ -> x

  let bind m f =
    fun buf -> f (m buf) buf

  let add_string s buf =
    Buffer.add_string buf s

  let add_char c buf =
    Buffer.add_char buf c

  let contents sz m =
    let buf = Buffer.create sz in
    m buf;
    Buffer.contents buf

  let lift f m =
    bind m (fun x -> return (f x))

  let ( >>= ) =
    bind

  let ( >> ) m1 m2 =
    bind m1 (fun _ -> m2)
end

      

        
        
        
      

    

Monadic alist to string conversion

As an example, let's implement the conversion alists

to a string in this monad:

let rec add_alist lst =
  let open MonadicBuffer in
  match lst with
    | [] -> return ()
    | (k,v) :: tl -> add_key k v >> add_alist tl
and add_key k v =
  let open MonadicBuffer in
  return ()
  >> add_string k
  >> add_string ": "
  >> add_string v
  >> add_char '\n'

      

        
        
        
      

    

Converting higher order alists to string

It's incredible to compare this version to the classic higher order solution:

let rec buffer_add_alist buf alist =
  match alist with
    | [] -> ()
    | (k,v) :: tl -> buffer_add_key buf k v; buffer_add_alist buf tl
and buffer_add_key buf k v =
  let open Buffer in
  add_string buf k;
  add_string buf ": ";
  add_string buf v;
  add_char buf '\n'

      

        
        
        
      

    

Then your template is executed by with_buffer

a higher order function:

let with_buffer sz f x =
  let buf = Buffer.create sz in
  f buf x;
  Buffer.contents buf

      

        
        
        
      

    

At the code level, the main difference is that the monadic version doesn't need to pass a variable buf

. At the performance level, the advantage over the version higher-order

. For what it's worth, the following graph represents the execution time of each method versus the size of the processed one alist

(each pair is the same all over the place): This displays two very noisy structures, however the linear trend in each series is clearly distinguishable, with the monadic corpus having the highest slope ...