OCaml: сопоставить выражение внутри другого?
В настоящее время я работаю над небольшим проектом с 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 *)
;;
И в основном у меня проблемы с выражением match. Например, я пробую что-то вроде этого:
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 (...)» никогда не распознаются. Возможно ли вообще иметь выражения соответствия внутри других выражений соответствия, подобных этому? И как правильно завершить внутреннее сопоставление, чтобы я мог продолжить сопоставление других возможностей?
Игнорируйте логику, так как это в значительной степени то, что я придумал в первую очередь, просто я не смог попробовать, так как сначала мне нужно разобраться с этой ошибкой "совпадения", хотя есть какие-либо рекомендации о том, как справиться с рекурсивностью или логика приветствовалась бы.
Ответы 2
Быстрое решение
Вам просто нужно добавить круглые скобки или 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 хорош, не правда ли?
Вы можете сделать это более лаконичным (и я бы сказал, более понятным), разумно используя символы подчеркивания, как и шаблоны or. Результирующий код также более эффективен, потому что он выделяет меньше (в случаях 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
;;
Это решение недействительно. Ошибка: конструктор Diff ожидает 2 аргумента (ов), но здесь применяется к 1 аргументу (ам)