module Memo : sig
  type 'a endo
  val id : 'a endo
  val (++) : 'a endo -> 'a endo -> 'a endo

  val lift : 'b endo -> ('a -> 'b) endo
  val memo : ('a -> 'b) endo

  val apply : 'a endo -> 'a -> 'a
end = struct
  type 'a endo = 'a -> 'a
  let id x = x
  let (++) f g x = f (g x)
  let lift m f x = m (f x)

  let memo f =
    let cache = Hashtbl.create 10 in
    fun x ->
      try Hashtbl.find cache x
      with Not_found ->
        let y = f x in
        Hashtbl.add cache x y;
        y

  let apply m x = m x
end

let z = Memo.id
let s n = Memo.(memo ++ lift n)

let test x y z = Printf.printf "%d %d %d\n" x y z; x + y + z

let t = Memo.(apply (s (s (s z))) test)