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

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

-Поверните все выражения вида a - (b + c) или аналогичные в - 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
;;

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

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

Ответ 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 хорош, не правда ли?

Ответ 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
;;