Verificando parênteses, colchetes e chaves correspondentes com Elixir

🏴󠁧󠁢󠁥󠁮󠁧󠁿 English version of this text here!

Eu comecei a estudar a linguagem Elixir e decidi resolver alguns exercícios de programação pra conseguir entender melhor alguns conceitos.
Como eu acabei gostando da minha solução, decidi fazer esse post explicando o pensamento por trás dela. Sugestões pra melhorar ainda mais o código ou pra melhor seguir os padrões e convenções do Elixir são mais do que bem-vindos! (:

O Problema

Quero fazer uma função que recebe uma string de entrada, supostamente uma expressão matemática ou um trecho de código, e que me diga se todos os seus abre parênteses/colcehetes/chaves são corretamente fechados.
Algumas expressões de exemplo:

1 * 2 (3 + [4 / 5])
# deveria retornar true
9 / [(8 + 7] - 6)
# deveria retornar false

Faça um plano

Antes de começar a escrever código, eu acho que é uma boa ideia resolver o problema de maneira teórica, para aí sim tentar implementá-lo.

Pra esse exercício, eu acredito que usar o conceito de pilha seja uma boa ideia.
Basicamente, uma pilha é um conjunto de itens que tem duas operações: push e pop.

• O push vai colocar um novo item no conjunto
• O pop vai remover o último item adicionado

Ou seja, a pilha segue o princípio do "Last In, First Out" (LIFO), ou seja, "o último a entrar será o primeiro a sair".

Mas como podemos usar uma pilha aqui? Bom, minha solução teórica seria de iterar sobre todos os caracteres na string de entrada e:

• Se for uma "abertura" ((, [ ou {), colocamos na pilha
• Se for um "fechamento" (), ] ou }), temos que verificar o último item adicionado na pilha. Se forem correspondentes (( com ), por exemplo), nós removemos ele da pilha (pop) e seguimos a iteração. Do contrário, a string de entrada era inválida
• Se for outra coisa, ignoramos

Se iterarmos sobre a expressão inteira e nunca acharmos um erro, isso significa que todos os fechamentos tiveram uma abertura apropriada, mas isso não significa necessariamente que a string era válida. Veja esse exemplo:

1 + (2 * [3]

Aqui, todos os fechamentos tiveram uma abertura correta, mas nem todas as aberturas foram fechadas.
Isso significa que, caso sobrevivamos à iteração, temos que verificar também se no final a nossa pilha está vazia. Se sim, então todas as aberturas foram corretamente fechadas. Se não, o valor de entrada era inválido.

A Implementação

Boa, temos um plano. Agora, temos que traduzir isso para Elixir.
Pra começar, vou criar um módulo chamado Parens com a função check, que vai receber uma string.
Essa função check terá que iterar sobre todos os caracteres desse valor de entrada, então podemos separar essa string usando a função split/2, do módulo String. Nosso primeiro trecho de código então é algo assim:

defmodule Parens do
  def check(expression) do
    expression
    |> String.split("")
  end
end

Usei aqui o operador pipe |>. O que ele faz é que ele usa o que vem antes como o primeiro argumento do que vier depois. Nesse caso, expression será o primeiro argumento para String.split.
O segundo argumento nesse caso é uma string vazia, o que significa que vamos separar expression em todos os caracteres.
O resultado final será uma lista, tipo assim:

"a + b * (c / d)" |> String.split("")
# ["", "a", " ", "+", " ", "b", " ", "*", " ", "(", "c", " ", "/", " ", "d", ")", ""]

Na nossa solução teórica, todos os caracteres diferentes de aberturas/fechamentos deveriam ser ignorados. Podemos removê-los da nossa lista agora usando um filter (filtro). Pra fazer isso, podemos chamar Enum.filter/2, que recebe dois argumentos.
O primeiro deve ser algo "enumerável", que significa que deve ser algo que implementa o "protocolo" Enum.
Felizmente, listas fazem isso, então podemos usar nosso resultado como primeiro argumento do filtro.
O segundo argumento é uma função que recebe um elemento da nossa lista e decide se ele deveria ou não estar no resultado filtrado. Mais especificamente, essa função vai retornar um valor, e se ele for falsy (false ou nil), o filtro vai remover esse item do resultado final. Do contrário, ele vai estar na lista resultante.

No nosso caso, essa função vai ter que verificar cada elemento e dizer se ele é ou uma abertura ou um fechamento, que são os únicos caracteres que nos importam. Uma maneira de se fazer isso é assim:

fn x -> x in ["{", "[", "(", "}", "]", ")"] end

Essa função anônima vai receber algo (x) e ver se essa coisa pertence ou não àquela lista especificada, que contém somente os caracteres importantes (aberturas e fechamentos).
Também poderíamos usar a notação de captura, assim:

&(&1 in ["{", "[", "(", "}", "]", ")"])

Essa notação é parecida, mas ao invés de declarar o x, a gente usa &1, &2, &3... para todos os argumentos que podem chegar.

Beleza, então nosso código até aqui está assim:

defmodule Parens do
  def check(expression) do
    expression
    |> String.split("")
    |> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
  end
end

O próximo passo é iterar sobre nossa listra resultante (depois do filtro) e usar a nossa estratégia da pilha.
Pra fazer isso, decidi criar uma função privada chamada iterate, onde vou recursivamente andar sobre nossos elementos, levando a pilha de um lado para o outro, até termos verificado todos os nossos elementos.
Já que eu vou precisar da pilha, essa função terá uma aridade de 2, ou seja, ela terá 2 argumentos.
A primeira coisa que eu faço quando estou pensando sobre recursão é de escrever a condição de parada. Nesse caso, a função deveria parar assim que a nossa lista de caracteres estiver vazia.
Vou usar a funcionalidade maravilhosa de pattern matching aqui pra fazer isso:

defp iterate([], stack), do: stack

Isso significa que essa função só vai ser executada quando o primeiro elemento for uma lista vazia, e o segundo elemento pode ser qualquer coisa aqui (que será colocado numa variável chamada stack, que significa pilha em inglês).
Nesse caso, a função não está fazendo nada, apenas retornando a pilha. Mais tarde podemos verificar se ela está vazia ou não.

Um ponto muito importante pra perceber aqui é que também temos que passar a pilha quando chamamdos a função iterate pela primeira vez. Nossa pilha começa vazia, então nossa pipeline ficou assim:

def check(expression) do
  expression
  |> String.split("")
  |> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
  |> iterate([])
end

Obs: Também podemos usar um valor padrão aqui, mas deixarei assim.

Agora, a parte difícil. Depois de escrever a condição de parada da nossa recursão, temos que escrever o passo recursivo (ou passos).

Vamos relembrar nosso plano outra vez. Temos que olhar pra cada elemento, e se for uma abertura, colocamos na pilha e seguimos em frente. Vamos fazer essa parte primeiro.

Eu amo pattern matching, então vou estar usando aqui de novo. E pra ajudar-nos ainda mais, também usarei algumas guardas (ou guard, em inglês), pra decidir se a função será executada ou não:

defp iterate([head | tail], stack) when head in ["{", "[", "("] do
end

Essa função somente será executada se a variável head estiver naquela lista de aberturas. Mas de onde essa variável está vindo?
Estamos fazendo o pattern matching do primeiro argumento com [head | tail], então essa função vai precisar que o primeiro argumento seja uma lista que tenha um primeiro elemento. Esse elemento então vai ser vinculado/ligado (bind) a head. O resto da lista será vinculado a tail. Sempre que estiver em dúvida, podemos abrir o shell interativo do Elixir e fazer alguns testes.
Escreva iex no terminal e aperte enter, e tente alguns códigos como esses:

[head | tail] = [1,2,3,4]
head
#=> 1
tail
#=> [2,3,4]

[head2 | tail2] = [0]
head2
#=> 0
tail2
#=> []

[head3 | tail3] = []
# Vai levantar um "matching error"!

Os conceitos de "cabeça" e "cauda" de uma lista são bastante importantes (head e tail, respectivamente). O primeiro elemento de uma lista é sua cabeça, e a cauda será o resto da lista. Perceba que a cauda é também uma lista!

Okay, de volta pra nossa função. O que ela deveria fazer se o elemento sendo verificado for uma abertura?
Ela deveria colocar na pilha (push) e seguir iterando. Podemos fazer isso simplesmente chamando iterate com os argumentos certos.
Como já verificamos o primeiro elemento, temos que passar a lista sem o primeiro elemento, certo? E isso é exatamente o que tail é! Ótimo, mas como podemos adicionar (fazer o push) esse elemento na pilha?
O Elixir oferece uma maneira muito fácil de colocar um item no começo de uma lista, e é simplesmente assim:

[elemento_novo | pilha]

Isso é uma lista cuja cabeça é elemento_novo, e a cauda é pilha. Sempre podemos ir no iex e fazer alguns experimentos:

[1 | 9,8,7]
#=> [1,9,8,7]

Então, nossa função pode ficar meio assim:

defp iterate([head | tail], stack) when head in ["{", "[", "("],
  do: iterate(tail, [head | stack])

Quando head for uma abertura, a gente chama iterate passando tail como primeiro argumento e a pilha com um novo elemento adicionado como segundo elemento.

Legal! Agora que temos essa parte feita, vamos recapitular:

Já sabemos parar a recursão;
Já lidamos com os casos dos caracteres que não são nem aberturas, nem fechamentos;
Já sabemos adicionar um item na pilha e seguir adiante;

Agora temos que fazer alguma coisa quando o elemento é um fechamento. Quando isso acontece, a ideia era olhar o último item adicionado na nossa pilha, que por construção, vem a ser exatamente a cabeça da nossa pilha!

A próxima parte do código foi fortemente refatorada, mas eu vou mostrar como eu fiz inicialmente.

Pra cada fechamento possível, eu fiz uma declaração específica, fazendo o pattern match na cabeça dos elementos que vão ser iterados, assim:

defp iterate(["}" | tail], stack)
defp iterate(["]" | tail], stack)
defp iterate([")" | tail], stack)

E daí pra cada uma delas, eu fiz um if/else simples:

defp iterate(["}" | tail], stack) do
  if hd(stack) == "{" do
    iterate(tail, tl(stack))
  else
    false
  end
end

Primeiro de tudo, aqui eu usei as funções hd e tl, que retornam a cabeça e a cauda de uma lista, respectivamente. Seria a mesma coisa que escrever isso:

defp iterate(["}" | tail], [stack_head | stack_tail]) do
  if stack_head == "{" do
    iterate(tail, stack_tail)
  else
    false
  end
end

Essa função, então, só vai executar se o primeiro elemento da lista for exatamente }. Daí a gente verifica se o último elemento adicionado na pilha, sua cabeça (estamos adicionando as coisas "pela cabeça" na lista!) é {, que seria a correspondência correta.
Se for, temos que fazer o pop desse elemento, era o nosso plano. Perceba que a versão "popada" da pilha é simplesmente sua cauda, então é por isso que não passamos a pilha pra próxima iteração, e sim sua cauda (representada por stack_tail, veja o pattern matching nos argumentos da função).
Se não for a correspondência correta, a gente sabe que a string de entrada não era válida, então estou retornando false aqui.

Note que a parte do else não é realmente necessária, pois se não entrássemos na parte do if, o valor retornado seria nil, mas vou deixar assim por enquanto. Depois podemos refatorar (:

Isso parece uma boa "versão alpha" da nossa função iterate. O que está faltando é verificar no final se a nossa pilha está vazia ou não após a condição de parada.
Poderíamos usar aqui Enum.empty?, que receberia a pilha e verificaria se está vazia ou não (true se estiver vazia, false caso contrário).
Uma outra maneira de fazer isso seria adicionar uma comparação com [] ou na condição de parada, ou na pipeline da nossa função check. Vou fazer a segunda opção primeiro pra poder falar rapidinho do módulo Kernel.

O módulo Kernel tem todas as funções "nativas", que podemos chamar sem escrever um módulo. Ou seja, se você quiser somar dois inteiros, podes fazer dos dois jeitos:

1+2
#=> 3
Kernel.+(1,2)
#=> 3

A comparação == também faz parte do módulo Kernel, então podemos fazer assim:

def check(expression) do
  expression
  |> String.split("")
  |> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
  |> iterate([])
  |> Kernel.==([])
end

Isso vai pegar o que quer que seja que tenha retornado de iterate e passar como primeiro argumento de Kernel.==. O segundo argumento é [], então vamos retornar a comparação entre o resultado de iterate com [].
Se a entrada for uma expressão inválida, iterate pode retornar false, e daí a comparação com [] também será falsa.
Outra possibilidade é que iterate vai retornar uma pilha não vazia, ou seja, uma lista com algum elemento. Neste caso, a comparação com [] também será falsa.

Isso até resolve o problema, mas pra mim é bastante feio.

Pra começo de conversa, às vezes iterate retorna um booleano, mas às vezes retorna uma lista, seja vazia ou não.
Agora que eu já escrevi um pouquinho sobre o módulo Kernel, acho que podemos não utilizá-lo aqui (:
Pra evitá-lo, podemos simplesmente colocar a comparação na nossa condição de parada:

defp iterate([], stack), do: stack == []

Outro jeito é de usar o pattern matching no segundo argumento, também!

defp iterate([], []), do: true
defp iterate([], _stack), do: false

Se o primeiro argumento for uma lista vazia e o segundo, também, retornamos true.
Se o primeiro argumento for uma lista vazia e o segundo for qualquer coisa, retornamos false.
O underline(_) em _stack denota que que essa variável não será usada. Poderíamos escrever simplesmente _, sem a palavra "stack" junto, mas acho que quando não é óbvio o que pode ser esse segundo parâmetro, é uma boa ideia dar um nome melhor para a variável, em nome da legibilidade.

Okay, então isso aparentemente funciona, certo?

Se tentarmos rodar nosso código agora, de vez em quanto tomaremos um erro!
Pra testá-lo, podemos usar nosso módulo dentro do iex. Pra fazer isso, salve o código em um arquivo, por exemplo, parens.ex. Agora, execute iex parens.ex. Conseguimos agora usar o módulo Parens, que criamos, dentro do iex!
Se tentarmos verificar uma string onde um fechamento foi encontrado num momento em que não há nenhuma abertura na nossa pilha, estaríamos tentando pegar a cabeça de uma lista vazia, o que levanta um erro para nós. Podes verificar com esses exemplos:

Parens.check("a}")
#> Levanta um erro!

Parens.check("(a}")
#=> false

Podemos arrumar isso se verificarmos se a pilha está vazia antes de tentarmos pegar a cabeça.

Ou...

Poderíamos simplesmente declarar uma função fazendo pattern matching no segundo argumento para uma lista vazia quando o elemento a ser analisado é um fechamento, assim:

defp iterate([head | _], []) when head in ["}", "]", ")"], do: false

A guarda vai garantir que o elemento em questão é um fechamento, e quando a pilha está vazia, retornamos direto false antes de tentar pegar a cabeça de uma lista vazia (que jogaria um erro em nós).

A primeira versão da nossa solução, portanto, poderia ser isso:

defmodule Parens do
  def check(expression) do
    expression
    |> String.split("")
    |> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
    |> iterate([])
  end

  defp iterate([], []), do: true
  defp iterate([], _stack), do: false

  defp iterate([head | tail], stack) when head in ["{", "[", "("],
    do: iterate(tail, [head | stack])

  defp iterate([head | _], []) when head in ["}", "]", ")"],
    do: false

  defp iterate(["}" | tail], stack) do
    if hd(stack) == "{" do
      iterate(tail, tl(stack))
    else
     false
    end
  end

  defp iterate(["]" | tail], stack) do
    if hd(stack) == "[" do
      iterate(tail, tl(stack))
    else
     false
    end
  end

  defp iterate([")" | tail], stack) do
    if hd(stack) == "(" do
      iterate(tail, tl(stack))
    else
     false
    end
  end
end

Show! Então agora nosso código realmente funciona!
Mas ele não me passa uma vibe muito boa...

Refatoração!

Primeiro, estamos usando listas como ["{", "[", "("], ["{", "[", "("] e ["{", "[", "(", "}", "]", ")"] algumas vezes, que poderiam ser extraídas para atributos de módulo.
Um atributo de módulo é um valor que pode ser usado por qualquer método dentro de um módulo. Pra definí-los, podemos escrever algo como @nome_do_atributo logo em seguida o seu valor.
No nosso caso, podemos fazer algo assim:

defmodule Parens do
  @opener ["{", "[", "("]
  @closer ["}", "]", ")"]
end

Com essa pequena adição, podemos reescrever nossas guardas e nosso filtro, desta maneira:

Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
Enum.filter(&(&1 in @opener || &1 in @closer))

defp iterate([head | tail], stack) when head in ["{", "[", "("]
defp iterate([head | tail], stack) when head in @opener,

defp iterate([head | _], []) when head in ["}", "]", ")"], do: false
defp iterate([head | _], []) when head in @closer, do: false

Isso é legal, mas ainda temos 3 grandes funções que são basicamente a mesma coisa, que são as que decidem o que fazer quando o elemento checado é um fechamento.

Vou escrever aqui a maneira como podemos melhorá-las, usando apenas um outro atributo de módulo e uma única função, e vou explicar depois o que ela faz:

defmodule Parens do
  @pairs %{"{" => "}", "[" => "]", "(" => ")"}

  defp iterate([head | tail], [stack_head | stack_tail]) when head in @closer,
    do: @pairs[stack_head] == head && iterate(tail, stack_tail)
end

Primeiro, eu criei o atributo @pairs, que é um mapa. Cada chave desse mapa é um caracter de abertura que é mapeado para o seu caracter de fechamento correspondente (mapas são como hashes e dicionários, se você está vindo do Ruby ou Python).
Então, eu fiz uma outra definição para iterate/2 que tem uma guarda. Essa guarda vai nos assegurar que a variável head (elemento a ser verificado) é um caracter de fechamento (então é ou ), ou ], ou }).
Eu também usei uma operação booleana && aqui:

@pairs[stack_head] == head && iterate(tail, stack_tail)

Se o lado esquerdo dessa operação for falsy, então este valor é retornado e o lado direito não é executado (o que para a nossa recursão).
Se o lado esquerdo for truthy, então seja lá o que for que está do lado direito é retornado. Nesse caso, o lado direito é uma chamada recursiva da nossa própria função iterate, continuando o ciclo.

Agora olhemos para @pairs[stack_head]. Lembra que @pairs é um mapa? Ou seja, se tivéssemos, por exemplo, @pairs["{"], isso retornaria "}".
Se seja lá o que for que estiver na cabeça da nossa pilha for um caracter de abertura, então estamos mapeando-o para o seu respectivo fechador quando consultamos o valor de @pairs[stack_head]. Se esse fechador for o mesmo que está na variável head, então essa comparação retorna true, que fará com que aquela operação booleana retorne o lado direito, isto é, a chamada recursiva da função, passando o resto da lista (tail) e a versão "popada" da pilha (stack_tail).
Se o que estiver na cabeça da pilha não for uma abertura, @pairs[stack_head] vai retornar nil, e nil == head vai ser falso, logo, a recursão morre aí.
Também pode acontecer que o que está na cabeça da pilha é uma abertura, mas @pairs[stack_head] não é igual a head. Logo, a comparação vai ser falsa também. Esse é o caso em que estamos tentando fechar algo que ainda não foi aberto, e como deu falso naquela comparação, a recursão para por aí.

Portanto, isso basta para verificar se os caracteres correspondem e parar a recursão caso contrário.

Então, a nossa segunda versão do programa seria:

defmodule Parens do
  @pairs %{"{" => "}", "[" => "]", "(" => ")"}
  @opener ["{", "[", "("]
  @closer ["}", "]", ")"]

  def check(expression) do
    expression
    |> String.split("")
    |> Enum.filter(&(&1 in @opener || &1 in @closer))
    |> iterate([])
  end

  defp iterate([], []), do: true
  defp iterate([], _stack), do: false

  defp iterate([head | tail], stack) when head in @opener,
    do: iterate(tail, [head | stack])

  defp iterate([head | _], []) when head in @closer, do: false

  defp iterate([head | tail], [stack_head | stack_tail]) when head in @closer,
    do: @pairs[stack_head] == head && iterate(tail, stack_tail)
end

Isso é tudo por hoje

Obrigado por lerem isso. Estou gostando bastante de Elixir! Pattern matching é bastante poderoso e divertido, também.
Por favor, corrijam erros que eu possa ter feito (:
Espero que vocês tenham aprendido algo hoje, e que tenham um bom dia.