OCaml: Abbina l'espressione dentro un'altra?

Question

Attualmente sto lavorando a un piccolo progetto con OCaml; un semplice semplificatore di espressioni matematiche. Dovrei trovare alcuni schemi all'interno di un'espressione e semplificarli in modo che il numero di parentesi all'interno dell'espressione diminuisca. Finora sono stato in grado di implementare la maggior parte delle regole tranne due, per le quali ho deciso di creare un filtro "ricorsivo" che corrisponda al modello funzione. Le due regole che devo implementare sono:

-Trasforma tutte le espressioni del modulo a - (b + c) o simili in a - b - c

-Trasforma tutte le espressioni del modulo a / (b * c) o simili in a / b / c

... che sospetto sarebbe abbastanza semplice, e una volta che sono riuscito a implementarne uno, posso implementare l'altro facilmente. Tuttavia, ho problemi con la funzione ricorsiva di pattern matching. La mia espressione di tipo è questa:

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

E ciò su cui ho principalmente problemi è nell'espressione della corrispondenza. Ad esempio, sto provando qualcosa del genere:

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

Tuttavia, sembra che l'espressione di corrispondenza sulla linea contrassegnata venga riconosciuta come parte della precedente "corrispondenza interna" anziché la "corrispondenza principale", quindi tutto "Quot (...)" le espressioni non vengono mai riconosciute. È anche possibile avere espressioni di corrispondenza all'interno di altre espressioni di corrispondenza come questa? E quale sarebbe il modo corretto di terminare la partita interiore in modo da poter continuare ad abbinare le altre possibilità?

Ignora la logica, dal momento che è praticamente quello che mi è venuto in mente per primo, è solo che non sono stato in grado di provarlo da quando ho a che fare con questo " match " errore per primo, anche se qualsiasi raccomandazione su come gestire la ricorsività o la logica sarebbe benvenuta.

Answer 1

Soluzione rapida

Devi solo aggiungere parentesi o inizio / fine , attorno alla corrispondenza interna:

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

semplificazioni

Nel tuo caso particolare non è necessaria una corrispondenza nidificata. Puoi semplicemente usare schemi più grandi. Puoi anche eliminare la duplicazione nelle regole nidificate usando " | " Pattern (" o "):

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

Puoi renderlo ancora più leggibile sostituendo le variabili di pattern inutilizzate con _ (trattino basso). Funziona anche con interi sottotitoli come la tupla (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
;;

Allo stesso modo, puoi procedere con la semplificazione. Ad esempio, i primi tre casi ( Var , Sum , Prod ) vengono restituiti non modificati, che è possibile esprimere direttamente:

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

Infine, puoi sostituire e2 con e e sostituire match con la scorciatoia 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
;;

La sintassi del pattern di OCaml è buona, vero?

Answer 2

Puoi rendere questo terser (e direi più chiaro) con un uso giudizioso dei caratteri di sottolineatura, come's e or-pattern. Il codice risultante è anche più efficiente, perché alloca meno (nei casi Var, Sum e 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
;;