OCaml: ¿Emparejar expresión dentro de otra?

Question

Actualmente estoy trabajando en un pequeño proyecto con OCaml; un simple simplificador de expresiones matemáticas. Se supone que debo encontrar ciertos patrones dentro de una expresión, y simplificarlos para que el número de paréntesis dentro de la expresión disminuya. Hasta ahora he podido implementar la mayoría de las reglas excepto dos, para lo cual he decidido crear una función recursiva de "filtro" de coincidencia de patrones. Las dos reglas I necesidad de implementar son:

-Girar todas las expresiones de la forma a - (b + c) o similar en a - b - c

-Girar todas las expresiones de la forma a/(b * c) o similar en a/b/c

... que sospecho que sería bastante simple, y una vez que he logrado implementar uno, puedo implementar el otro fácilmente. Sin embargo, estoy teniendo problemas con la función de coincidencia de patrones recursiva. Mi expresión de tipo es la siguiente:

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

Y en lo que principalmente tengo problemas, es en la expresión del partido. Por ejemplo, yo estoy tratando de hacer algo como esto:

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

Sin embargo, parece que la expresión de coincidencia en la línea marcada está siendo reconocido como parte de la anterior "juego interno" en lugar del "juego principal" , por lo que todas las expresiones "Quot (...)" nunca se reconocen. ¿Es posible incluso tener expresiones de coincidencia dentro de otras expresiones coincidentes como esta? ¿Y cuál sería la forma correcta de terminar la pareja interna para poder seguir combinando las otras posibilidades?

Ignore la lógica, ya que es más o menos lo que primero se me ocurrió, es solo que no he podido probarlo ya que tengo que lidiar primero con este error de "coincidencia", aunque cualquier recomendación sobre cómo manejar la recursividad o la lógica sería bienvenida.

Answer 1

Solución rápida

Sólo tiene que añadir entre paréntesis, o begin/end, todo el partido interno:

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

simplificaciones

En su caso particular, no hay necesidad de una coincidencia anidada. Puedes usar patrones más grandes. También puede eliminar la duplicación en las reglas anidadas utilizando patrones "|" ("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 
;; 

Puede que sea aún más fácil de leer mediante la sustitución de variables del patrón no utilizadas con _ (subrayado). Esto también funciona para los patrones sub integrales, tales como el (e3,e4) tupla:

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

De la misma manera, se puede proceder simplificar.Por ejemplo, los primeros tres casos (Var, Sum, Prod) se devuelven sin modificar, que se puede expresar directamente:

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

Por último, se puede reemplazar e2 por e y reemplazar match con el function atajo:

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 sintaxis del patrón de OCaml es agradable, ¿no?

Answer 2

Puede hacer que este terser (y yo diría más claro) mediante el uso juicioso de guiones bajos, as y o-patrones. El código resultante también es más eficiente porque asigna menos (en los casos Var, Sum y 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 
;;