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) ->
            (match e2 with
             | Sum (e3, e4) -> filter (diffRule e2)
             | Diff (e3, e4) -> filter (diffRule e2)
             | _ -> filter e2)
    | 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
;;