Monads, Applicatives & Binding Operators

Monad laws: left identity, right identity, associativity.

33.1 Binding operators (OCaml 4.08+)

let ( let* ) = Option.bind
let ( and* ) a b = match a, b with Some x, Some y -> Some (x, y) | _ -> None
let ( let+ ) o f = Option.map f o

let add_strings a b =
  let* x = int_of_string_opt a in
  let* y = int_of_string_opt b in
  Some (x + y)

let both a b =
  let+ x = int_of_string_opt a
  and+ y = int_of_string_opt b in     (* needs ( and+ ) defined like and* *)
  x + y

33.2 Result monad

module Result_syntax = struct
  let ( let* ) = Result.bind
  let ( let+ ) r f = Result.map f r
end

let process input =
  let open Result_syntax in
  let* age = parse_age input in
  let* () = if age >= 18 then Ok () else Error (Negative age) in
  Ok (Printf.sprintf "Adult aged %d" age)

33.3 Generic monad signature

Monad laws: left identity, right identity, associativity.

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

module Monad_utils (M : MONAD) = struct
  let ( >>= ) = M.bind
  let ( let* ) = M.bind
  let map f m = M.bind m (fun x -> M.return (f x))
  let rec sequence = function
    | [] -> M.return []
    | m :: ms -> let* x = m in let* xs = sequence ms in M.return (x :: xs)
end

33.4 State monad

module State (S : sig type t end) = struct
  type 'a t = S.t -> 'a * S.t
  let return x s = (x, s)
  let bind m f s = let (a, s') = m s in f a s'
  let get s = (s, s)
  let put s _ = ((), s)
  let run m s = m s
  let ( let* ) = bind
end

module Counter = State (struct type t = int end)
let tick = Counter.(let* n = get in let* () = put (n + 1) in return n)
let (_, final) = Counter.run Counter.(let* _ = tick in let* _ = tick in tick) 0   (* final = 3 *)

33.5 Other common monads

List monad (non-determinism): let ( let* ) l f = List.concat_map f l.

Reader (dependency injection), Writer (logging), Continuation.

Lwt.t / Eio promises for async (§37).

Parser combinators (angstrom) — monadic parsing.

33.6 Applicatives & functors

map : ('a -> 'b) -> 'a t -> 'b t, both : 'a t -> 'b t -> ('a * 'b) t. Applicatives enable *parallel/independent* composition (e.g., validation collecting all errors, Cmdliner terms).

33.7 Parser combinators from scratch

type 'a parser = string -> int -> ('a * int) option

let return x : 'a parser = fun _ i -> Some (x, i)
let ( let* ) (p : 'a parser) (f : 'a -> 'b parser) : 'b parser =
  fun s i -> match p s i with None -> None | Some (a, j) -> f a s j
let ( <|> ) p q = fun s i -> match p s i with None -> q s i | r -> r
let satisfy pred : char parser = fun s i ->
  if i < String.length s && pred s.[i] then Some (s.[i], i + 1) else None
let char c = satisfy (( = ) c)
let rec many p = (let* x = p in let* xs = many p in return (x :: xs)) <|> return []
let many1 p = let* x = p in let* xs = many p in return (x :: xs)
let digit = satisfy (function '0' .. '9' -> true | _ -> false)
let number =
  let* ds = many1 digit in
  return (int_of_string (String.of_seq (List.to_seq ds)))

let rec expr s = (let* a = term in (let* _ = char '+' in let* b = expr in return (a + b)) <|> return a) s
and term s = (let* a = factor in (let* _ = char '*' in let* b = term in return (a * b)) <|> return a) s
and factor s = (number <|> (let* _ = char '(' in let* e = expr in let* _ = char ')' in return e)) s

let _ = expr "2*(3+4)" 0    (* Some (14, 7) *)