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 (...)» никогда не распознаются. Возможно ли вообще иметь выражения соответствия внутри других выражений соответствия, подобных этому? И как правильно завершить внутреннее сопоставление, чтобы я мог продолжить сопоставление других возможностей?

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


pattern-matching ocaml
person Sergio Morales    schedule 02.11.2008    source источник

Ответы (2)


arrow_upward
82
arrow_downward

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

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

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

person vog    schedule 03.11.2008

arrow_upward
9
arrow_downward

Вы можете сделать это более лаконичным (и я бы сказал, более понятным), разумно используя символы подчеркивания, такие как и или-шаблоны. Полученный код также более эффективен, потому что он выделяет меньше (в случаях 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
;;
person zrr    schedule 05.11.2008
comment
Это решение недействительно. Ошибка: конструктор Diff ожидает 2 аргумента (ов), но здесь применяется к 1 аргументу (ам) - person vog; 11.02.2015