Функция OCaml для дифференциации

Question

В настоящее время я изучаю язык OCaml, и решал проблему с упражнениями, когда натолкнулся на вопрос, который, кажется, не может обернуться. Вот вопрос:

"Написать функцию differentiate : expression * string -> expression который получает алгебраическое уравнение и строку в качестве аргумента и возвращает дифференцированную версию уравнения аргумента.

Например, diff (Add [Mult [Int 3 ; Exp("x", 2)] ; Mult [Int 6 ; Variable "x"], "x") должен дать результат:

Add [Mult [Int 6 ; Variable "x"] ; Int 6] "

Вот код, который я написал:

type expression =
  | Int of int
  | Variable of string
  | Exponent of string * int
  | Mult of expression list
  | Add of expression list


let rec differentiate : expression * string -> expression
= fun (exp, x) ->
  match exp with
  | Int a -> Int 0
  | Variable a -> if (a = x) then Int 1 else Variable a
  | Exponent (a, b) -> if (a = x) then
                      match b with
                      | 2 -> Mult [Int 2; Variable a]
                      | _ -> Mult [Int b; Exponent (a, b - 1)]
                    else Int 0
  | Mult [Int a; Int b] -> Const (a * b)
  | Mult (Int a::[Variable b]) -> Mult (Int a::[differentiate (Variable b, x)])
  | Mult (Int a::[Exponent (e1, e2)]) -> Mult (Int a::[differentiate (Exponent (e1, e2), 
x)])
  | Mult (Int a::[Mult (Int b :: l)]) -> Mult (Int (a * b) :: l)
  | Add l -> match l with
             | [] -> l
             | hd::tl -> Add ((differentiate (hd, x)) :: tl)
;;

Мой алгоритм в основном выполняет строгое сопоставление с образцом. Более конкретно, для Mult первый элемент всегда является целым числом, поэтому я выполнил сопоставление с шаблоном для второго элемента. За Add Я планировал написать функцию, чтобы она выполняла эту функцию. differentiate на каждом элементе. Вот конкретные проблемы, о которых я хотел бы спросить.

1. Этот код на самом деле дает мне ошибку на Add l часть сопоставления с образцом. Сообщение об ошибке гласит: Error: This expression has type (expression list) but an expression was expected of type (expression). Насколько мое понимание достигает, я уверен, что Add l является expression тип, а не expression list тип. Почему появляется это сообщение об ошибке?

2. Я не уверен, как выполнить рекурсию в этом конкретном примере. Сначала я думал, что функция должна выполняться только один раз, иначе результат будет состоять в основном из Int 0 или Int 1 "S. Пожалуйста, поправьте меня, если я ошибаюсь.

Любая обратная связь с благодарностью. Спасибо!

Answer 1

type exp =
  | Int  of int
  | Var  of string
  | Exp  of string * int
  | Add  of exp list
  | Mult of exp list

let rec diff x = function
  | Int _ -> Int 0
  | Var y -> Int (if x = y then 1 else 0)
  | Exp (y, n) -> if x = y then Mult [Int n; Exp (y, n - 1)] else Int 0
  | Add  exp_list -> Add (List.map (diff x) exp_list)
  | Mult exp_list ->
     let rec terms acc (left, right) =
       match right with
       | [] -> acc
       | hd :: tl -> terms ((hd, left @ tl) :: acc) (hd :: left, tl) in
     Add (List.map (fun (f, g) -> Mult [diff x f; Mult g]) (terms [] ([], exp_list)))

let rec norm = function
  | Exp (_, 0) -> Int 1
  | Exp (x, 1) -> Var x
  | Add  exp_list ->
     let int_list, rest = List.fold_left (fun (int_list, rest) exp ->
       match exp with
       | Int i -> i :: int_list, rest
       | Add (Int i :: exp_list) -> i :: int_list, exp_list @ rest
       | Add exp_list -> int_list, exp_list @ rest
       | _ -> int_list, exp :: rest) ([], []) (List.map norm exp_list) in
     let sum = List.fold_left (+) 0 int_list in
     begin match sum, rest with
       | _, []  -> Int sum
       | 0, [e] -> e
       | 0, _   -> Add rest
       | _      -> Add (Int sum :: rest) end
  | Mult exp_list ->
     let int_list, rest = List.fold_left (fun (int_list, rest) exp ->
       match exp with
       | Int i -> i :: int_list, rest
       | Mult (Int i :: exp_list) -> i :: int_list, exp_list @ rest
       | Mult exp_list -> int_list, exp_list @ rest
       | _ -> int_list, exp :: rest) ([], []) (List.map norm exp_list) in
     let prod = List.fold_left ( * ) 1 int_list in
     begin match prod, rest with
       | _, []  -> Int prod
       | 0, _   -> Int 0
       | 1, [e] -> e
       | 1, _   -> Mult rest
       | _      -> Mult (Int prod :: rest) end
  | (Int _ | Var _ | Exp _) as e -> e

Это одно из возможных решений этой проблемы. Идея состояла в том, чтобы сначала реализовать алгоритм для проведения дифференцирования по рекурсии по структуре выражения. И мы должны быть простыми, то есть мы не заботимся об упрощениях синтаксического дерева, мы только заботимся о правильном вычислении дифференцирования. Затем, на втором этапе, мы упрощаем дерево до "нормальной" формы (не уверен, что оно всегда приводит к одному и тому же результату для эквивалентных выражений, но поскольку в задаче не указано, какие упрощения нам следует выполнить, я предполагаю, что мы свободный выбор).

Некоторые примеры:

# norm (diff "x" (Add [Mult [Int 3 ; Exp("x", 2)] ; Mult [Int 6 ; Var "x"]]));;
- : exp = Add [Int 6; Mult [Int 6; Var "x"]]

# norm (diff "y" (Mult [Var "x"; Mult[Int 2; Exp ("y", 3)]]));;
- : exp = Mult [Int 6; Var "x"; Exp ("y", 2)]

# norm (diff "y" (Mult [Var "x"; Var "y"]));;
- : exp = Var "x"