Correspondência de expressão dentro de outra: OCaml?

Question

Atualmente estou trabalhando em um projeto pequeno com OCaml; um simples simplificador expressão matemática. Eu tenho que encontrar certos padrões dentro de uma expressão, e simplificá-los de modo que o número de parênteses dentro da expressão diminui. Até agora tenho sido capaz de implementar a maioria das regras, exceto dois, para o qual eu decidi criar uma função recursiva, de correspondência de padrões "filtro". As duas regras Eu preciso implementar são:

Vire todas as expressões de uma forma - (b + c) ou semelhante para a - b - c

Vire todas as expressões de forma a / (b * c) ou semelhante para a / b / c

... que eu suspeito que seria bastante simples, e uma vez eu consegui implementar um, eu posso implementar o outro facilmente. No entanto, estou tendo problemas com a função recursiva de correspondência de padrões. Meu tipo de expressão é esta:

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 o que eu estou tendo problemas principalmente em diante, está na expressão de correspondência. Por exemplo, estou tentando algo como isto:

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

No entanto, parece que a expressão de correspondência na linha marcada está sendo reconhecido como sendo parte do "jogo interno" anterior em vez do "match principal", para que todos os "Quot (...)" expressões não são reconhecidos . Será que é mesmo possível ter expressões de correspondência dentro de outras expressões de correspondência como este? E qual seria a maneira correta de terminar o jogo interior, de modo que eu possa continuar combinando as outras possibilidades?

Ignorar a lógica, já que é muito bonito o que eu vim acima com o primeiro, é só que eu não tenho sido capaz de experimentar desde que eu tenho que lidar com esse erro "jogo" em primeiro lugar, embora qualquer recomendação sobre como lidar a recursividade ou a lógica seria bem-vinda.

Answer 1

Solução rápida

Você só precisa adicionar parênteses ou begin / end, em torno do jogo 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)
;;

Simplificações

No seu caso particular, não há necessidade para um jogo aninhada. Você pode apenas usar padrões maiores. Você também pode eliminar a duplicação nas regras aninhadas usando "|" ( "ou") padrões:

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

Você pode torná-lo ainda mais legível, substituindo variáveis ??de modelo não utilizados com _ (sublinhado). Isso também funciona para sub padrões integrais, tais como a 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
;;

Da mesma forma, você pode prosseguir a simplificação. Por exemplo, os primeiros três casos (Var, Sum, Prod) são devolvidos sem modificações, o que você pode expressar diretamente:

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, você pode substituir e2 por e e substituir match com o atalho 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
;;

sintaxe padrão de OCaml é bom, não é?

Answer 2

Você pode fazer este terser (e eu diria mais clara) pelo uso criterioso de sublinhados, como de e ou-padrões. O código resultante também é mais eficiente, porque ele aloca menos (nos casos 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
;;