OCaml: Match expression dans un autre?

Question

Je travaille actuellement sur un petit projet avec OCaml; un simple simplificateur d'expression mathématique. Je suis censé trouver certains motifs dans une expression et les simplifier afin que le nombre de parenthèses à l'intérieur de l'expression diminue. Jusqu'à présent, j'ai été capable d'implémenter la plupart des règles, sauf deux, pour lesquelles j'ai décidé de créer un "filtre" récursif de correspondance de motifs. une fonction. Les deux règles que je dois implémenter sont les suivantes:

-Tourner toutes les expressions de la forme a - (b + c) ou similaire en a - b - c

-Tourner toutes les expressions de la forme a / (b * c) ou similaire en a / b / c

... ce que je soupçonne d’être assez simple, et une fois que j’ai réussi à en implémenter un, je peux facilement implémenter l’autre. Cependant, j'ai des problèmes avec la fonction d'appariement de motifs récursive. Mon expression de type est la suivante:

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

Et ce qui me pose le plus de problèmes, c’est dans l’expression du match. Par exemple, j'essaie quelque chose comme ceci:

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

Cependant, il semble que l'expression de correspondance sur la ligne marquée soit reconnue comme faisant partie de la précédente "correspondance interne". au lieu de la "correspondance principale", donc toutes les "quotations (...)" les expressions ne sont jamais reconnues. Est-il même possible d'avoir des expressions de correspondance dans d'autres expressions de correspondance comme celle-ci? Et quelle serait la bonne façon de mettre fin à la correspondance interne afin que je puisse continuer à faire correspondre les autres possibilités?

Ignorez la logique, car c’est à peu près ce que j’ai proposé en premier, c’est simplement que je n’ai pas été en mesure de l’essayer, car je dois traiter ce "match". erreur en premier, bien que toute recommandation sur la façon de gérer la récursivité ou la logique soit la bienvenue.

Answer 1

Solution rapide

Il vous suffit d'ajouter des parenthèses ou début / fin , autour de la correspondance interne:

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

Simplifications

Dans votre cas particulier, une correspondance imbriquée n'est pas nécessaire. Vous pouvez simplement utiliser de plus grands modèles. Vous pouvez également éliminer la duplication dans les règles imbriquées en utilisant " | ". (") motifs:

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

Vous pouvez le rendre encore plus lisible en remplaçant les variables de modèle inutilisées par _ (trait de soulignement). Cela fonctionne également pour des sous-modèles entiers tels que le tuple (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 même manière, vous pouvez procéder à la simplification. Par exemple, les trois premiers cas ( Var , Sum , Prod ) sont renvoyés sans modification, ce que vous pouvez exprimer directement:

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

Enfin, vous pouvez remplacer e2 par e et remplacer la correspondance par le raccourci fonction :

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 syntaxe de motif d'OCaml est agréable, n'est-ce pas?

Answer 2

Vous pouvez clarifier ce point (et je dirais qu'il est plus clair) en utilisant judicieusement les traits de soulignement, tels que and and or Le code résultant est également plus efficace, car il alloue moins (dans les cas Var, Sum et 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
;;