Programação, Scala

Loops funcionais e foldLeft

No paradigma de programação funcional os tradicionais loops while e for não possuem aplicabilidade. O motivo disso é o fato destes loops não retornarem um valor usável, logo eles precisam alterar valores existentes e, obviamente, isso implica no uso de dados mutáveis. Qualquer função agregadora realizada através de um loop while implica na necessidade de termos pelo menos uma variável para conter os dados agregados. Assim, loops while são uma construção tipicamente imperativa e até mesmo em Scala este tipo de loop não tem valor de retorno: retorna apenas o valor Unit que não podemos usar para qualquer finalidade prática.

No entanto, Scala manteve os loops imperativos(while e do-while) como parte da linguagem de modo a tornar mais fácil a migração de código legado para Scala, assim como para torná-la mais atrativa para programadores que seguem outros paradigmas. Ao permitir várias abordagens aos problemas, Scala não impõe uma grande barreira de entrada a sua plataforma.

Scala permite a programação funcional, imperativa, imperativa orientada a objetos(tradicional de Java,C#,Python) e sua característica mais inovadora é a forma como permite a programação funcional orientada a objetos. Scala também adaptou o loop for para permitir que este seja usado como expressão. De fato, em Scala não o chamamos apenas de loop for; temos uma sintaxe diferente para o loop imperativo e outra para a expressão for, a qual substitui o corpo do loop pela palavra-chave yield. Falaremos mais sobre a expressão for em um post específico.

Como o paradigma funcional aborda loops e repetições?
É evidente que loops e estruturas de repetição são imprescindíveis para qualquer tipo de programação, porém a forma de realizar a repetição é diferente de acordo com o paradigma seguido. Em linguagens funcionais, os loops são executados através da recursão: funções que chamam a si mesmas passando dados distintos a cada iteração, dando origem a “loops funcionais”.

Nota: A origem da distinção entre loops funcionais e loops imperativos nos remete aos primórdios da Ciência da Computação, quando o Cálculo Lambda de Alonso Church foi contraposto à Máquina de Turing, de Alan Turing. Posteriormente foi provado que o Cálculo de Lambda e as Máquinas de Turing são equivalentes, logo tudo que é possível de ser realizado no paradigma funcional pode ser realizado de forma imperativa, e vice-versa

Vejamos um exemplo clássico de loop funcional:
def fatorial(i: Int) = {
def ajudanteFatorial(i2: Int, acumulador: Int): Int = {
if (i2 <= 1) acumulador
else ajudanteFatorial(i2 - 1, i2 * acumulador)
}
ajudanteFatorial(i, 1)
}
fatorial(5)
//SAIDA: 120

O que aconteceu neste trecho de código? Primeiro definimos uma função fatorial, a qual recebe um Int como parâmetro. Logo definimos a função auxiliar ajudanteFatorial, que é interna e restrita apenas ao escopo de fatorial(), a qual recebe dois Int‘s, um para o fatorial que desejamos calcular e outro para um acumulador. O acumulador e o parâmetro principal trabalham juntos para formar um loop funcional.

Logo adiante a função fatorial() chama ajudanteFatorial com os parâmetros iniciais: o inteiro que nos foi passado, e o valor inicial do acumulador.

Nota: O valor inicial do acumulador, coincidentemente, é muitas vezes igual ao caso de base ou “condição de terminação” da função recursiva. Ou seja, é ao chegar a este caso que devemos encerrar a recursão e retornar o valor acumulado. Esta é uma dica que pode nos ajudar a determinar qual o caso de terminação de recursões: quando estamos desenhando um algoritmo recursivo, o caso de terminação da recursão frequentemente é o mesmo valor que usamos para iniciar a função auxiliar do loop funcional.

A função fatorial poderia também ser definida apenas em termos de si própria, assim:
def fatorial(i: Int) = {
if (i <= 1) 1
else i * fatorial(i - 1)
}
fatorial(5)
//SAIDA: 120

No entanto repare que o valor de retorno recursivo envolve um Int que multiplica o retorno da função. Esta multiplicação impede que o compilador aplique a otimização da recursão de valores-fins(tail recursion). Quando o compilador detecta apenas uma chamada a uma função em posição final, este transforma a construção em um loop while no momento da compilação, eliminando as várias chamadas recursivas na pilha do programa. Quando uma função se encontra em posição de ser otimizada por ser valor-final, dizemos que esta se encontra em posição de “tail”. Por isso na primeira implementação criamos uma função auxiliar, a qual era chamada sem uma multiplicação externa.

O loop foldLeft
A solução utilizando função auxiliar e acumulador é tão comum que recebeu um nome específico na programação funcional: fold. Fold é um idioma funcional que envolve tornar genérica a solução que encontramos para o primeiro exemplo de fatorial deste artigo.

O nome “fold” faz alusão ao fato de estarmos dobrando(folding) recursivamente uma estrutura de dados para tratar de suas várias iterações. É como se tivéssemos um mapa para turistas de uma certa cidade, o qual se dobra e desdobra, e estivéssemos estudando cada face e logo dobrando a mesma para examinar a próxima. Como o leitor pode notar, é uma analogia totalmente distinta daquela usada nas linguagens imperativas.

Em Scala este idioma é implementado de algumas formas distintas. As mais usadas são foldLeft e foldRight. Conforme o nome sugere, foldLeft começa a “dobrar” a coleção de dados da esquerda para a direita(o que normalmente se traduz em começar do menor índice de um Vetor ou da cabeça de uma lista), e sua contrapartida, foldRight, segue no sentido oposto. Apesar de aparentarem ser equivalentes, na prática não o são. Algumas estruturas de dados são fácilmente visitadas em uma direção, e dificilmente na outra. Mas esse tópico foge ao escopo deste post, logo concentraremos apenas em foldLeft, que é o idioma que usamos no loop de fatorial descrito acima.

Vejamos a implementação de fatorial usando foldLeft em Scala:
def fatorial2(i: Int) =
(1 to i).foldLeft(1)((acumulador, valorAtual) => acumulador * valorAtual)
fatorial2(5)
//SAIDA: 120

Como podemos notar, nosso loop funcional foi convertido em uma linha apenas. Primeiro transformamos o valor inteiro recebido para uma lista através da construção 1 to i, depois chamamos foldLeft sobre esta lista. foldLeft visita cada valor da lista passando-lhe o valor atual do item da lista e o atual acumulador. O segundo parâmetro de foldLeft é uma função auxiliar, a qual trabalha o valor acumulado e o valor atual. O leitor atento notará que a função auxiliar é análoga à nossa função auxiliar que definimos no primeiro exemplo de fatorial, ajudanteFatorial, a qual recebia também o valor atual e um acumulador. Este fato torna mais claro como foldLeft está executando nosso código.

Números astronômicos e a “explosão” recursiva
O leitor poderia questionar: se o valor de i for suficientemente grande, o fatorial dos valores da lista gerada por 1 to i não poderia extrapolar a capacidade de memória do computador? Sim! Na verdade, todos os processos que envolvem números fatoriais são recursivos, e números fatoriais calculados a partir de valores iniciais relativamente pequenos podem sim extrapolar facilmente a capacidade de qualquer computador existente. De fato o fatorial sofre uma “explosão” de magnitude logo nas primeiras recursões. No entanto esta é uma característica matemática do fatorial e não uma limitação do idioma funcional em si.

Conclusão
Loops funcionais podem ser implementados através do idioma fold. Praticamente todas as soluções que são possíveis com loops while imperativos podem ser traduzidas para fold, efetuando as devidas alterações nas estruturas de dados usadas. Para trabalhar com fold, devemos decidir quem será nosso acumulador(que vai ditar o tipo do retorno) e qual será nossa lista de dados a serem processados. Após termos esses dados, basta aplicar foldLeft e o loop funcional fará o resto por nós, sem precisar de código imperativo como os loops while e do-while.

Standard