OCaml: Совпадение выражения внутри другого?

Question

В настоящее время я работаю над небольшим проектом с OCaml; простое математическое упрощение выражений. Я должен найти определенные шаблоны внутри выражения и упростить их, чтобы уменьшить количество скобок внутри выражения. До сих пор я был в состоянии реализовать большинство правил, кроме двух, для которых я решил создать рекурсивную функцию фильтра по сопоставлению с образцом. Мне нужно реализовать два правила:

- превратить все выражения вида a - (b + c) или аналогичные в a - b - c

- превратить все выражения вида a / (b * c) или аналогичные в a / b / c

... что, я подозреваю, будет довольно простым, и как только мне удастся реализовать одно, я могу легко реализовать другое. Однако у меня возникли проблемы с рекурсивной функцией сопоставления с образцом. Мое выражение типа это:

type expr =
 | Var of string            (* variable *)
 | Sum of expr * expr       (* sum  *)
 | Diff of expr * expr      (* difference *)
 | Prod of expr * expr      (* product *)
 | Quot of expr * expr      (* quotient *)
;;

И то, с чем у меня в основном проблемы, в выражении матча. Например, я пытаюсь что-то вроде этого:

let rec filter exp =   
    match exp with       
    | Var v -> Var v                        
    | Sum(e1, e2) -> Sum(e1, e2)          
    | Prod(e1, e2) -> Prod(e1, e2)
    | Diff(e1, e2) ->
        match e2 with
        | Sum(e3, e4) -> filter (diffRule e2)
        | Diff(e3, e4) -> filter (diffRule e2)      
        | _ -> filter e2         
    | Quot(e1, e2) ->                                 ***this line***
        match e2 with  
        | Quot(e3, e4) -> filter (quotRule e2)        
        | Prod(e3, e4) -> filter (quotRule e2)        
        | _ -> filter e2
;;

Однако, похоже, что выражение соответствия на отмеченной строке распознается как часть предыдущего «внутреннего соответствия» вместо «основного соответствия», поэтому все выражения «Quot (...)» никогда не распознаются , Можно ли даже иметь выражения совпадения внутри других выражений совпадения, подобных этому? И как правильно завершить внутреннее сопоставление, чтобы я мог продолжить сопоставление с другими возможностями?

Не обращайте внимания на логику, так как это во многом то, что я придумал первым, просто я не смог ее попробовать, так как сначала мне приходится иметь дело с этой ошибкой "соответствия", хотя и есть рекомендации по ее обработке Рекурсивность или логика приветствуются.

Answer 1

Быстрое решение

Вам просто нужно добавить круглые скобки или begin / end вокруг внутреннего соответствия:

let rec filter exp =
    match exp with
    | Var v -> Var v
    | Sum (e1, e2) -> Sum (e1, e2)
    | Prod (e1, e2) -> Prod (e1, e2)
    | Diff (e1, e2) ->
            <b>(</b>match e2 with
             | Sum (e3, e4) -> filter (diffRule e2)
             | Diff (e3, e4) -> filter (diffRule e2)
             | _ -> filter e2<b>)</b>
    | Quot (e1, e2) ->
            (match e2 with
             | Quot (e3, e4) -> filter (quotRule e2)
             | Prod (e3, e4) -> filter (quotRule e2)
             | _ -> filter e2)
;;

Упрощения

В вашем конкретном случае нет необходимости во вложенном совпадении. Вы можете просто использовать большие шаблоны. Вы также можете устранить дублирование во вложенных правилах, используя шаблоны "|" ("или"):

let rec filter exp =
    match exp with
    | Var v -> Var v
    | Sum (e1, e2) -> Sum (e1, e2)
    | Prod (e1, e2) -> Prod (e1, e2)
    | Diff (e1, (Sum (e3, e4) | Diff (e3, e4) as e2)) -> filter (diffRule e2)
    | Diff (e1, e2) -> filter e2
    | Quot (e1, (Quot (e3, e4) | Prod (e3, e4) as e2)) -> filter (quotRule e2)
    | Quot (e1, e2) -> filter e2
;;

Вы можете сделать его еще более читабельным, заменив неиспользуемые переменные шаблона на _ (подчеркивание). Это также работает для целых подшаблонов, таких как кортеж (e3,e4):

let rec filter exp =
    match exp with
    | Var v -> Var v
    | Sum (e1, e2) -> Sum (e1, e2)
    | Prod (e1, e2) -> Prod (e1, e2)
    | Diff (_, (Sum _ | Diff _ as e2)) -> filter (diffRule e2)
    | Diff (_, e2) -> filter e2
    | Quot (_, (Quot _ | Prod _ as e2)) -> filter (quotRule e2)
    | Quot (_, e2) -> filter e2
;;

Таким же образом вы можете продолжить упрощение. Например, первые три случая (Var, Sum, Prod) возвращаются без изменений, которые можно выразить напрямую:

let rec filter exp =
    match exp with
    | Var _ | Sum _ | Prod _ as e -> e
    | Diff (_, (Sum _ | Diff _ as e2)) -> filter (diffRule e2)
    | Diff (_, e2) -> filter e2
    | Quot (_, (Quot _ | Prod _ as e2)) -> filter (quotRule e2)
    | Quot (_, e2) -> filter e2
;;

Наконец, вы можете заменить e2 на e и заменить match на function ярлык:

let rec filter = function
    | Var _ | Sum _ | Prod _ as e -> e
    | Diff (_, (Sum _ | Diff _ as e)) -> filter (diffRule e)
    | Diff (_, e) -> filter e
    | Quot (_, (Quot _ | Prod _ as e)) -> filter (quotRule e)
    | Quot (_, e) -> filter e
;;

Синтаксис шаблона OCaml хорош, не так ли?

Answer 2

Вы можете сделать это более кратким (и я бы сказал более ясным) разумным использованием подчеркиваний, а также и-или-образцов. Результирующий код также более эффективен, поскольку он выделяет меньше (в случаях Var, Sum и Prod)

let rec filter = function
| Var _ | Sum _ | Prod _ as e -> e
| Diff (_, (Sum _ | Diff _) as e) -> filter (diffRule e)
| Diff (_,e) -> e
| Quot (_, (Quot _| Prod _) as e) -> filter (quoteRule e)
| Quot (_,e) -> filter e
;;