Um avaliador de expressões matemáticas em F# (usando Active Patterns)

Este post foi originalmente publicado em 2015 (infelizmente, a postagem original não está mais disponível)

Nesse post vamos implementar, passo-a-passo, um avaliador de expressões matemáticas em F#. Para isso, utilizaremos “Active Patterns” – um dos conceitos mais interessantes da linguagem.

Se não está familiarizado com o conceito de “Active Patterns” recomendo fortemente que leia a documentação antes de prosseguir.

Reconhecendo dígitos

Vamos começar a implementação de nosso avaliador de expressões por algo bastante trivial: reconhecer um dígito.

open System

let (|Digit|_|) = function
    | x::xs when Char.IsDigit(x) -> 
        Some(Char.GetNumericValue(x), xs)
    | _ -> None

"10" |> List.ofSeq |> (|Digit|_|)

O que fizemos? Criamos um “active pattern” que verifica se o primeiro caractere de uma lista de caracteres é um dígito. Em caso positivo, retorna uma tupla com a versão “numérica” e a lista dos caracteres que completam a cadeia.

Reconhecendo a parte inteira de um número

Agora que conseguimos reconhecer um dígito, já podemos reconhecer a parte inteira de um número.

let (|IntegerPart|_|) input = 
    match input with 
    | Digit(h, t) ->
        let rec loop acc = function 
            | Digit(x, xs) -> loop ((acc * 10.) + x) xs
            | xs -> Some(acc, xs)
        loop 0. input
    | _ -> None

"10" |> List.ofSeq |> (|IntegerPart|_|)
".34" |> List.ofSeq |> (|IntegerPart|_|)

Bacana! Começamos aqui a ver o poder dos “Active Patterns”. Começamos nossa implementação verificando se a lista de caracteres começa com um dígito. Em caso positivo, iniciamos um loop acumulando um “inteiro” enquanto forem encontrados outros dígitos.

Reconhecendo a parte fracionária de um número

Para reconhecer a parte fracionária usamos uma lógica bem semelhante.

let (|FractionalPart|_|) = function
    | '.'::t-> 
        let rec loop acc d = function 
            | Digit(x, xs) -> loop ((acc * 10.) + x) (d * 10.) xs
            | xs -> (acc/d, xs)
        Some(loop 0. 1. t)
    | _ -> None

"10" |> List.ofSeq |> (|FractionalPart|_|)
".34" |> List.ofSeq |> (|FractionalPart|_|)

A única diferença é que começamos verificando se o primeiro caractere é um ‘.’.

Reconhecendo números

Agora que já conseguimos reconhecer a parte inteira e a parte fracionária, vamos criar mais um “Active Pattern” para juntar as duas partes.

let (|Number|_|) = function
    | IntegerPart(i, FractionalPart(f, t)) -> Some(i+f, t)
    | IntegerPart(i, t) -> Some(i, t)
    | FractionalPart(f, t) -> Some(f, t)
    | _ -> None

"10" |> List.ofSeq |> (|Number|_|)
".35" |> List.ofSeq |> (|Number|_|)
"10.35" |> List.ofSeq |> (|Number|_|)

Um número é criado se a cadeia de caracteres 1) começar com uma parte inteira seguida de uma parte fracionária; 2) começar com uma parte inteira; 3) começar com uma parte fracionária.

Implementando a avaliação de expressões

Temos números. Agora chegou a hora de suportarmos operações matemáticas com eles.

Esse código é baseado no exemplo disponível no site F# News. Entretanto, um pouquinho aprimorado 😉

let evaluate expression = 
    let rec (|Expr|_|) = function
        | Mult(e, t) -> 
            let rec loop l = function 
                | '+'::Mult(r, t) -> loop (l + r) t
                | '-'::Mult(r, t) -> loop (l - r) t
                | [] -> Some(l, [])
                | _ -> None
            loop e t
        | _ -> None
    and (|Mult|_|) = function
        | '+'::Atom(e, t) -> Some(e, t)
        | '-'::Atom(e, t) -> Some(-e, t)
        | Atom(l, '*'::Mult(r, t)) -> Some(l * r, t)
        | Atom(l, '/'::Mult(r, t)) -> Some(l / r, t)
        | Atom(e, t) -> Some(e, t)
        | _ -> None
    and (|Atom|_|) = function
        | Number(e, t) -> Some(e, t)
        | '('::Expr(e, ')'::t) -> Some(e, t)
        | _ -> None

    expression |> List.ofSeq |> (|Expr|_|)

evaluate "2+2/2"

Lindo, não?!