Я получаю ошибки, когда использую монады

Question

Я пытаюсь написать код, используя монаду. Я делаю что-то неправильно? Я не могу понять, почему я получаю ошибку. Msgstr "Ошибка: это выражение имеет тип (expr -> 'a) ->' a, но ожидалось выражение типа expr". Эта ошибка есть в тестовых примерах. Кажется, работает нормально, когда я не использую монады. Это неправильный способ его использования?

type var = X | Y | Z;;  
type expr = N of int    
          | V of var
          | Add of expr * expr
          | Mul of expr * expr;;

let add a b = 
    match (a, b) with
    | ((N 0), y) -> y
    | (x, (N 0)) -> x
    | ((N x), (N y)) -> N (x + y)
    | _ -> Add (a, b)

let mul a b = 
    match (a, b) with
    | ((N 0), y) -> N 0
    | ((N 1), y) -> y
    | (x, (N 0)) -> N 0
    | (x, (N 1)) -> x
    | ((N x), (N y)) -> N (x * y)
    | _ -> Mul (a, b)

let id x = x 

module Cont = struct
    let ret x = fun k -> k x
    let (>>=) m f = fun k -> m (fun x -> (f x) k)
end

let rec deriv expr var =
    let open Cont in
    match expr with
    | N x -> ret (N 0)
    | V v -> if v = var then ret (N 1) else id ret (N 0)
    | Add (a, b) -> deriv a var >>= fun x -> 
                    deriv b var >>= fun y -> 
                    ret (add x y)
    | Mul (a, b) -> deriv b var >>= fun x -> 
                    deriv a var >>= fun y -> 
                    ret (add (mul a x)(mul b y))
    | _ -> assert false

let rec to_str expr =
    let open Printf in
    let open Cont in
    let var_to_str = function
        X -> "x" | Y -> "y" | Z -> "z" | _ -> assert false in
    match expr with
        | N a -> ret (sprintf "%d" a)
        | V v -> ret (var_to_str v)
        | Add (a, b) -> to_str a >>= fun x -> to_str b 
                                 >>= fun y -> 
                                 ret (sprintf "(%s + %s)" x y)
        | Mul (a, b) -> to_str a >>= fun x -> to_str b 
                                 >>= fun y -> 
                                 ret (sprintf "%s * %s" x y)
        | _ -> assert false

(*test cases*)    
let a = add (V X) (N 3)
let _ = to_str a                (* "(x + 3)" *)
let _ = to_str (deriv a X)      (* "1" *)
let _ = to_str (deriv a Y)      (* "0" *)

let b = add (mul (N 2) (V X)) (mul (V Y) (N 3))
let _ = to_str b                (* "(2 * x + y * 3)" *)
let _ = to_str (deriv b X)      (* "2" *)
let _ = to_str (deriv b Y)      (* "3" *)

let c = mul (mul (V X) (V Y)) (add (V X) (N 3))
let _ = to_str c                (* "x * y * (x + 3)" *)
let _ = to_str (deriv c X)      (* "(x * y + y * (x + 3))" *)
let _ = to_str (deriv c Y)      (* "x * (x + 3)" *)

Answer 1

В ваших тестовых случаях вы звоните по to_str в прямом стиле -

(*test cases*)    
let a = add (V X) (N 3)
let _ = to_str a
let _ = to_str (deriv a X) (* deriv returns a Cont *)
let _ = to_str (deriv a Y) (* deriv returns a Cont *)

let b = add (mul (N 2) (V X)) (mul (V Y) (N 3))
let _ = to_str 
let _ = to_str (deriv b X) (* deriv returns a Cont *)
let _ = to_str (deriv b Y) (* deriv returns a Cont *)

let c = mul (mul (V X) (V Y)) (add (V X) (N 3))
let _ = to_str c
let _ = to_str (deriv c X) (* deriv returns a Cont *)
let _ = to_str (deriv c Y) (* deriv returns a Cont *)

Но, как мы знаем, deriv возвращает продолжение ! Вы должны передать to_str как продолжение ...

(*test cases*)    
let a = add (V X) (N 3)
let _ = to_str a
let _ = (deriv a X) to_str (* (deriv ...) then continue with to_str *)
let _ = (deriv a Y) to_str (* (deriv ...) then continue with to_str *)

let b = add (mul (N 2) (V X)) (mul (V Y) (N 3))
let _ = to_str b
let _ = (deriv b X) to_str (* (deriv ...) then continue with to_str *)
let _ = (deriv b Y) to_str (* (deriv ...) then continue with to_str *)

let c = mul (mul (V X) (V Y)) (add (V X) (N 3))
let _ = to_str c
let _ = (deriv c X) to_str (* (deriv ...) then continue with to_str *)
let _ = (deriv c Y) to_str (* (deriv ...) then continue with to_str *)

---

Обратите внимание, to_str также возвращает конинацию! Так как же это распечатать? -

let _ = print_endline ((to_str a) id)          (* (x + 3) *)
let _ = print_endline ((deriv a X) to_str id)  (* 1 *)
let _ = ...

Продолжения переворачивают вашу программу вверх дном и наизнанку! Вместо того, чтобы разматывать id и передавать результат в print_endline, вы можете передать print_endline в качестве продолжения -

let a = add (V X) (N 3)
let _ = (to_str a) print_endline
let _ = (deriv a X) to_str print_endline
let _ = (deriv a Y) to_str print_endline

let b = add (mul (N 2) (V X)) (mul (V Y) (N 3))
let _ = (to_str b) print_endline
let _ = (deriv b X) to_str print_endline
let _ = (deriv b Y) to_str print_endline

let c = mul (mul (V X) (V Y)) (add (V X) (N 3))
let _ = (to_str c) print_endline
let _ = (deriv c X) to_str print_endline
let _ = (deriv c Y) to_str print_endline

Выход

(x + 3)
1
0
(2 * x + y * 3)
2
3
x * y * (x + 3)
(x * y + (x + 3) * y)
(x + 3) * x

---

Я также посмотрите это -

... else id ret (N 0)

Где id можно безопасно отбросить -

... else ret (N 0)