OCaml: Dopasuj wyrażenie do innego?

Question

Obecnie pracuję nad małym projektem z OCaml; prosty uproszczacz wyrażeń matematycznych. Powinienem znaleźć pewne wzorce wewnątrz wyrażenia i uprościć je, aby liczba nawiasów wewnątrz wyrażenia zmalała. Do tej pory udało mi się wdrożyć większość reguł, z wyjątkiem dwóch, dla których postanowiłem stworzyć rekursywną funkcję "filtra" dopasowującą do wzorca. Te dwie reguły trzeba zaimplementować to:

-Skręć wszystkie wyrażenia w postaci - (B + C), lub podobnego do A - B - C

-Skręć wszystkie wyrażenia Postać A/(B * c) lub podobne do/b/c

... które, jak podejrzewam, byłyby dość proste, a gdy już uda mi się je zrealizować, mogę łatwo wdrożyć drugie. Mam jednak problem z funkcją rekursywnego dopasowywania wzorca. Moja ekspresja to:

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 *) 
;; 

I to, w czym głównie mam problemy, jest w wyrażeniu dopasowania. Na przykład, próbuję coś takiego:

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 
;; 

Wydaje się jednak, że wyrażenie mecz na zaznaczonej linii jest uznawane za część poprzedniego meczu „wewnętrznej” zamiast „głównym meczu” , więc wszystkie wyrażenia "Quot (...)" nigdy nie są rozpoznawane. Czy w innych wyrażeniach pasujących jest to możliwe? I jaki byłby właściwy sposób zakończenia wewnętrznego pojedynku, aby móc dalej dopasowywać inne możliwości?

Ignoruj ​​logikę, ponieważ jest to dość dużo, co wymyśliłem pierwszy, to po prostu, że nie udało nam się spróbować, ponieważ mam do czynienia z tym „meczu” błąd pierwszy, chociaż wszelkie zalecenia, w jaki sposób obsłużyć rekursywność lub logika byłyby mile widziane.

Answer 1

Szybkie rozwiązanie

Wystarczy dodać nawiasy lub begin/end, wokół wewnętrznego meczu:

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) 
;; 

Uproszczenia

w danym przypadku nie ma to potrzeba zagnieżdżonego dopasowania. Możesz po prostu użyć większych wzorów. Można również wyeliminowanie powielania zagnieżdżonych zasad korzystania „|” („lub”) wzory:

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 
;; 

można uczynić go jeszcze bardziej czytelny, zastępując nieużywanych zmiennych wzór z _ (podkreślenie). Działa to także dla całych wzorów cząstkowych, takich jak (e3,e4) krotki:

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 
;; 

W ten sam sposób można postępować uproszczenie.Na przykład, pierwsze trzy przypadki (Var, Sum, Prod) są zwracane niemodyfikowana, które można wyrazić bezpośrednio:

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 
;; 

Wreszcie, można zastąpić e2 przez e i zastąpić match z function skrótu:

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 
;; 

Składnia wzoru OCamla jest przyjemna, prawda?

Answer 2

Możesz sprawić, że ten terser (a ja będę twierdził, że będzie bardziej przejrzysty) przez rozważne użycie podkreśleń, takich jak i wzorce. Wynikowy kod jest również bardziej wydajny, ponieważ alokuje mniej (w przypadkach Var, Sum i 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 
;;