OCaml: ¿Coincide la expresión dentro de otra?


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 sido capaz de implementar la mayoría de las reglas excepto dos, para lo cual he decidido crear una función recursiva de "filtro" que coincida con el patrón. Las dos reglas que necesito implementar son:

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

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

...lo 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 lo que principalmente estoy teniendo problemas, es en la expresión de coincidencia. Por ejemplo, estoy intentando 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 la expresión de coincidencia en la línea marcada se reconoce como parte de la "coincidencia interna" anterior en lugar de la "coincidencia principal", por lo que todos "Quot(...) "las expresiones nunca son reconocidas. ¿Es posible tener expresiones coincidentes dentro de otras expresiones coincidentes como esta? ¿Y cuál sería la forma correcta de terminar la coincidencia interna para que pueda seguir coincidiendo con las otras posibilidades?

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

Author: Matthias Braun, 2008-11-03

2 answers

Solución Rápida

Solo necesita agregar paréntesis, o begin/end, alrededor del partido interior:

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 hacerlo aún más legible reemplazando las variables de patrón no utilizadas con _ (subrayado). Esto también funciona para patrones de sub enteros como 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
;;

De la misma manera, puede proceder simplificando. Por ejemplo, los tres primeros casos (Var, Sum, Prod) se devuelven sin modificar, que 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
;;

Finalmente, puedes reemplazar e2 por e y reemplazar match con el atajo 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 sintaxis del patrón de OCaml es agradable, ¿no?

 61
Author: vog,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-06-17 06:35:00

Puede hacer esto más conciso (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
;;
 11
Author: zrr,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-11-05 04:34:42