Monad evaluator with bind operator, not able to get what the syntax is about

Question

I have the following:

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

module IdMonad : MONAD_SIG = 
  struct
    type 'a t = Id of 'a
    let return v = Id v
    let bind (Id v) f = f v
    let (>>=) = bind (* always the case *)
  end
    
type term = Const of int | Div of term * term

let e1 = Div (Div (Const 1972, Const 2), Const 23)

let e2 = Div (Const 1, Const 0)

module EvalIdMonad = struct
  include IdMonad

  let divM a b = return (a / b) (* will be different for each monad; type ?? *)

  let evalM t = (* will be the same across all monads; type ?? *)
    let rec evalMrec t = 
      match t with
    | Const c -> return c
    | Div(a,b) -> evalMrec a >>= fun n -> evalMrec b >>= fun d -> divM n d
  in evalMrec t
end

let _ = EvalIdMonad.evalM e1

This: evalMrec a >>= fun n -> evalMrec b >>= fun d -> divM n d I have trouble understanding what it means or how it evaluates given that there is no parenthesis at least to illustrate.

What I get is that, first let's assume we reach the recursive basis and we have this: return c >>= fun n -> return c' >>= fun d -> divM n d, how this will work? My guess is that we go innermost first, so, return c' >>= fun d -> divM n d evaluates first, and we get divM n c' and then return c >>= fun n -> divM n c' will return divM c c', is that correct?

Also, can you illustrate how monad is helping here?

Answer 1

Since the monad that you are using is the identity monad, it is not helping in any way, it is just a layer of syntactic boilerplate. In particular, >>= is just a version of |> (left-to-right) function evaluation that destructure the Id _ constructor on this left side

evalMrec a >>= fun n -> evalMrec b >>= fun d -> divM n d

reads

evalMrec a |> (fun (Id n) ->
  evalMrec b |> (fun (Id d) ->
    divM n d
  )
)

which can be rewritten using let as

let Id n = evalMRec a in
let Id d = evalMRec b in
divM n d

Presumably, this is just an intermediary step in your textbook/homework before moving to more interesting examples. But you should not spend too much time trying to find deep meaning, at this point there are none.

Similarly

return c >>= fun n -> return c' >>= fun d -> divM n d

reads

(return c) >>= (fun n -> return c' >>= fun d -> divM n d)

and like any operators both sides of the operators are evaluated before the operator is applied to the results.