cost of monads

[Warren Harris <warrensomebody@gmail.com>]

I'm considering writing a moderate sized program with high performance  
needs in a monad / monad transformer style in ocaml. Although I  
believe that this abstraction will offer me benefits in hiding some  
complexity, some of the monad transformers I would like to "stack" are  
quite simple (e.g. a state-transition monad), and I'm concerned that  
my program will be paying a high performance cost due to high function  
call overhead -- ones which cannot be optimized away due to module  
boundaries.

I know that the real answer here is "profile it and find out"... but I  
thought that asking for other's experience might be a good first step.  
Perhaps someone can offer a technique to make this work well, or a  
word of caution on why this should be avoided. I realize that most of  
the monad work happens in haskell (and I sometimes feel that I'm  
reinventing the wheel -- although it's very educational!), but I'd  
prefer to stick with ocaml if possible.

Warren


(* -*- Mode: Caml; tab-width: 4; indent-tabs-mode: nil -*- *)
(******************************************************************************)

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

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

module IdM : ID_MONAD =
struct
   type 'a t = 'a
   let return a = a
   let (>>=) m f = f m
   let run a = a
end

(******************************************************************************)

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

   type s
   type 'a m
   val lift : 'a m -> 'a t
   val run : 'a t -> s -> 'a m
   val gets : s t
   val puts : s -> unit t
end

module type STATE = sig type s end

module StateT(M:MONAD)(S:STATE) : STATE_MONAD with type s = S.s =
struct
   type 'a m = 'a M.t
   type s = S.s
   type 'a t = s -> ('a * s) M.t
   let return a s = M.return (a, s)
   let (>>=) m f s = M.(>>=) (m s) (fun (a, s) -> f a s)

   let lift m s = M.(>>=) m (fun a -> M.return (a,s))
   let run m s = M.(>>=) (m s) (fun (a, _) -> M.return a)
   let gets s = M.return (s, s)
   let puts s _ = M.return ((), s)
end

(******************************************************************************)

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

   type 'a m
   type ans
   val lift : 'a m -> 'a t
   val run : ans t -> ans m
   val callcc : (('a -> 'b t) -> 'a t) -> 'a t
end

module type K = sig type ans end

module KMonadT(M:MONAD)(K:K) : KMONAD with type ans = K.ans =
struct
   type ans = K.ans
   type 'a m = 'a M.t
   type 'a t = ('a m -> ans m) -> ans m
   let lift m k = k m
   let return a k = k (M.return a)
   let (>>=) m f k = m (fun am -> M.(>>=) am (fun a -> f a k))
   let run m = m (fun a -> a)
   let callcc f k = f (fun a _ -> return a k) k
end

(******************************************************************************)