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?!
