Capítulo 2  Programação Funcional, Valores e Tipos

Este capítulo provê uma introdução à programação funcional, e à definição e uso de tipos de dados e seus valores. No caso de tipos funcionais, os valores são funções. Uma introdução sobre o conceito de funções é dada no Apêndice A, e uma introdução sobre o conceito de tipos é dada no Apêndice B.

Um programa em Haskell consiste em definições de funções, uma em seguida da outra. Deve ser definido também um valor monádico main, para indicar o ponto de início da execução do programa (mas valores monádicos serão abordados na Seção 5.3.1).

A verificação e inferência de tipos, mais precisamente a verificação de que valores são usados corretamente, de acordo o conjunto de valores que podem ser usados, é o assunto do Capítulo 3. A próxima seção corrente aborda como tipos podem ser definidos em Haskell, e como valores desses tipos e funções que recebem e retornam valores desses tipos podem ser usados em Haskell.

Valores e tipos estão em níveis distintos em Haskell (e em linguagens de programação em geral). Entre os tipos e seus valores estão aqueles que são pré-definidos na linguagem, de modo a que o uso de operações e valores durante a execução de programas em computadores seja simples e eficiente. Tipos básicos (ou simples) pré-definidos em Haskell são o assunto da seção 2.3. Tipos compostos podem ser, em Haskell, tipos funcionais e tipos algébricos e suas variações, como tuplas e listas, introduzidos na seção 2.1.2.

2.1  Introdução: Definições de Funções

Uma programa funcional é constituído por definições de valores e de funções. Uma função recebe um valor e retorna um valor. Esse valor pode ser um valor composto, de modo que retornar um ou mais valores não é uma questão relevante. Por exemplo, uma função pode receber e retornar um valor que é um par de valores.

Definições ocorrem no texto de um programa, uma em seguida da outra. Por exemplo, abaixo temos duas definições de funções:

Uma definição de função define o nome, os parâmetros e o corpo da função. O corpo é separado dos parâmetros pelo sinal (símbolo) =.

Dizemos que a função (de nome) quadrado tem um parâmetro (de nome) x, e um corpo — igual à expressão x*x, separados do nome da função e do parâmetro pelo símbolo =.

A definição e a chamada de uma função em Haskell podem ou não especificar parênteses entre os parâmetros e os argumentos. Uma definição equivalente de quadrado é:

Em vez de quadrado 3, podemos usar também quadrado(3). No entanto, muitas vezes o programa torna-se mais legível sem o uso de parênteses. A linguagem torna parênteses frequentemente desnecessários com uma regra simples que especifica que aplicações de funções têm precedência sobre operadores infixados. Por exemplo, quadrado 2 +   quadrado 3 não precisa de parênteses, quando se quer escrever (quadrado 2) + (quadrado 3).

Haskell é uma linguagem estaticamente tipada, como discutido no Capítulo 3. Em Haskell, toda expressão e toda definição, e em particular toda definição de função, tem um tipo. Esse tipo não precisa mas pode ser explicitamente especificado, antes da definição.

A função quadrado tem um tipo polimórfico restrito (tipos polimórficos são tratados na Seção 3 e tipos polimórficos restritos na Seção 3.2.2). Vamos iniciar apresentando tipos monomórficos. Uma instância do tipo polimórfico de quadrado é o tipo funcional monomórfico a seguir (esse tipo pode ser anotado antes da definição, como visto a seguir):

Um tipo funcional (i.e. tipo de uma função) tem a forma tp->tr, sendo tp o tipo do parâmetro e tr o tipo do resultado. Uma função com tipo tp -> tr precisa ser chamada com um argumento de tipo tp, e o valor retornado tem tipo tr (no caso de tipos polimórficos, veremos que o argumento e o resultado são de tipos que são respectivamente instâncias de tp e tr).

Por exemplo, quadrado 3 é uma expressão bem-tipada, porque a função quadrado pode ser chamada com argumento 3, uma vez que 3 é um valor que tem tipo Integer. A chamada retorna 3*3, que tem tipo Integer. Ao contrário, por exemplo quadrado '3' não é uma expressão bem-tipada, pois '3' tem tipo Char (Seção 2.3), não Integer.

O tipo de uma função pode ser anotado explicitamente, antes da sua definição propriamente dita; a anotação usa ::, entre o nome sendo definido e o tipo, como mostrado a seguir:

Se não for anotado, um tipo em Haskell é inferido (a não ser, em Haskell, no caso de anotações de tipos de nomes sobrecarregados: os tipos de nomes sobrecarregados têm que ser anotados, em classes de tipos; isso será explicado na Seção 3.2.2). Verificação e inferência de tipos são tratados no Capítulo 3. Ao longo do texto, fora de programas Haskell (e em matemática em geral), é comum o uso de : apenas, em vez de ::, para separar um nome de seu tipo. Um tipo anotado tem que ser instância do tipo da função, que é inferido se o tipo não for anotado (esse tipo é também chamado de tipo principal), mas vamos neste livro chamar apenas de tipo da função.

Informalmente, é comum dizer que a função somaDosQuadrados tem dois parâmetros x e y, mas de fato isso não é estritamente correto: toda função em Haskell tem apenas um parâmetro e retorna apenas um resultado; a função somaDosQuadrados tem um parâmetro x e denota função que, ao receber um argumento (denotado por x), retorna uma função que recebe um argumento (denotado por y) e retorna quadrado x + quadrado y. O tipo de somaDosQuadrados é:

O argumento é de tipo Integer e o resultado tem tipo Integer -> Integer. Por exemplo, para o argumento 3 o resultado é função que, ao receber y, retorna (3*3)+(y*y).

Chamadas de funções são associativas à esquerda. Por exemplo, somaDosQuadrados 3 4 é o mesmo que (somaDosQuadrados 3) 4. Essa associatividade evita frequentemente o uso de parênteses. No exemplo, pode-se escrever somaDosQuadrados 3 4 em vez de (somaDosQuadrados 3) 4.

De modo similar, o operador ->, escrito entre dois tipos, é associativo à direita. Por exemplo, Integer->Integer->Integer é o mesmo que Integer->(Integer->Integer). Os parênteses em casos como este também não precisam ser usados.

A função somaDosQuadrados é chamada de linearizada (ou “currificada”). Ela recebe o argumento x e retorna função que recebe y, em vez de receber x e y de uma vez só (como um par de argumentos). O adjetivo “currificado” é uma lembrança ao trabalho de Haskell Curry, que mostrou (de fato, após Moses Schönfinkel e, também, após Frege) que funções com vários argumentos (i.e. funções com argumento que é uma tupla) são desnecessárias, podendo ser transformadas em funções com um único argumento, que retornam uma função. Por exemplo, somaDosQuadrados poderia ser escrita de forma a receber um par de valores, como a seguir:

Chama-se em computação, em programação funcional, de corpo da função a expressão que define o valor retornado pela função, quando a função é chamada.

2.1.1  Nomes e Operadores

Em Haskell, um nome (ou identificador) começa com uma letra e pode ser seguido por letras, dígitos, sublinha e aspas simples.

O caractere sublinha (i.e. o caractere ’_’) é tratado como uma letra. No entanto, o caractere '_' sozinho é um nome reservado, do padrão chamado “coringa” (padrões são valores que não envolvem computação, i.e. não envolvem chamadas de funções; são tratados logo abaixo, nas seções 2.2.1 e 2.1.2).

Nomes usados em programas são divididos lexicamente em dois espaços: o primeiro, de variáveis, no qual cada nome começa com uma letra minúscula, e o segundo, de construtores, no qual cada nome começa com uma letra maiúscula. Vamos falar sobre nomes de construtores de valores, como os construtores True e False, do tipo Bool, na Seção 2.3.1.

Caixa alta e caixa baixa distinguem caracteres em nomes. Por exemplo, abc, aBc e Abc são nomes distintos: os dois primeiros são nomes distintos de variáveis e o último é um nome de um construtor.

Operatores como + e (*) são também nomes de funções, com a diferença de que, no caso de expressões com operadores binários, o nome é escrito entre os operandos, enquanto o nome de uma função é escrito antes do argumento. Mas a diferença é apenas sintática: um operador binário denota uma função, por exemplo os operadores binários + e * denotam funções que têm como instâncias o seguinte tipo (os tipos de + e * são polimórficos restritos, abordados na seção 3.2.2):

Qualquer operador binário pode ser escrito em forma pré-fixada em Haskell, bastando para isso escrevê-lo entre parênteses; por exemplo, em vez de 1+2 podemos escrever (+) 1 2. Analogamente, qualquer função não unária pode ser escrita como um operador infixado em Haskell, bastando para isso escrever o nome da função entre aspas invertidas; por exemplo somaDosQuadrados 2 3 pode ser escrito como 2 `somaDosQuadrados` 3. A diferença é apenas sintática.

2.1.2  Definições de Funções, Padrões, Tipos Algébricos

Em geral uma função é definida em Haskell por uma ou mais equações, sendo cada equação da seguinte forma:

Nesta equação f é o nome da função que está sendo definida, p1, p2, …, pk são padrões e e é uma expressão. Padrões são constantes ou variáveis que, quando são funcionais (i.e. quando o tipo é o de uma função) podem envolver outros sub-padrões.

Veja como primeiros exemplos as definições das funções quadrado e somaDosQuadrados acima, que usam apenas padrões que são variáveis. Uma variável usada para definição de uma função é chamada de parâmetro formal da função. Uma variável em uma linguagem funcional e um parâmetro formal em particular denota um valor qualquer, arbitrário, mas fixo; o valor é determinado quando a função é chamada. Por exemplo, a chamada quadrado 2 faz com o que o valor do parâmetro formal x seja igual a 2. O argumento da função, neste exemplo a expressao 2, é também chamado de parâmetro real.

Um padrão que é uma constante funcional usa uma constante introduzida em um tipo algébrico. Tipos algébricos podem ser polimórficos e recursivos. Em particular, listas têm um tipo algébrico polmórfico e definido recursivamente em Haskell. Tipos algébricos polimórfos e definidos recursivamente constituem ferramenta fundamental da programação em Haskell.

Um tipo lista é definido por um construtor de tipos (o construtor define um tipo ao receber um tipo): por exemplo o tipo de listas de inteiros, escrito em Haskell na forma [Int], é o tipo de listas de elementos de tipo Int. O construtor [_] recebe o tipo Int e constroi o tipo [Int] ([_] é um construtor que insere o argumento entre símbolos, em vez de após o nome do construtor, como é mais usual). O tipo de listas é um tipo algébrico polimórfico definido recursivamente, como mostrado abaixo:

A palavra data especifica o início da definição de um tipo algébrico. A variável a é um parâmetro desse tipo; a existência de uma variável de tipo caracteriza que se trata de um tipo polimórfico: um tipo no qual a variável de tipo pode ser instanciada para qualquer tipo. A instanciação ocorre no uso de expressões do tipo definido, construídas com um construtor de valores do tipo.

A definição de um tipo algébrico consiste em uma definição de construtores de valores desse tipo, especificados entre caracteres |. O caractere | delimita alternativas do tipo. Cada alternativa é iniciada com um nome (ou símbolo). No tipo acima, Nil e Cons são os nomes dos construtores de valores do tipo algébrico List a definido. Cada construtor pode ter ou não parâmetros: no tipo acima, Nil não tem parâmetros e Cons tem dois parâmetros. Mais precisamente, Cons tem um parâmetro de tipo a e retorna um tipo funcional: Cons a tem tipo tem [a] -> [a]. Ou seja, há duas formas de construir uma lista (qualquer lista): ou usando Nil (trata-se de uma lista vazia), ou usando Cons. Neste segundo caso, deve-se especificar um valor de tipo a — o primeiro elemento ou cabeça da lista, e um valor de tipo [a] — o restante ou rabo da lista.

Um tipo algébrico é assim uma soma de produtos de alternativas, onde cada alternativa é definida por um construtor, também chamado de etiqueta. O construtor distingue a alternativa de outras alternativas desse e dos demais tipos. A soma é também chamada de união disjunta. Os produtos podem ser produtos cartesianos linearizados (ou “currificados”, em referência e homenagem a Haskell Curry), isto é, com os componentes especificados um após o outro, em vez de todos de uma só vez, como em uma tupla.

2.2  Estratégia de avaliação preguiçosa

A estratégia usada na maioria das linguagens de programação é gulosa: em uma chamada de função, os argumentos são avaliados antes da função ser chamada. A chamada consiste na avaliação do corpo da função após a associação de cada parâmetro ao argumento correspondente, resultante da avaliação da expressão usada na chamada da função.

Em Haskell, a diferença consiste em que a associação ocorre sem que os argumentos sejam avaliados antes da chamada: os argumentos são avaliados se e somente se necessário, para realização de casamento de padrão quando e se o parâmetro for usado (em uma chamada de função que ocorre internamente ao corpo da função, durante a avaliação do resultado a ser retornado). A estratégia usada para avaliação de expressões em Haskell é chamada de preguiçosa.

A estratégia de avaliação preguiçosa é, mais precisamente, uma otimização da estratégia de avaliação normal, a qual consiste simplesmente em substituir toda ocorrência do parâmetro pela expressão correspondente usada na chamada da função. Por exemplo, considere o seguinte exemplo, da chamada à função quadrado com o argumento 2+3. Em vez de substituir 2+3 nas duas ocorrências de x, a

(que usa o parâmetro x duas vezes

…

2.2.1  Casamento de padrões

…

2.3  Tipos básicos

2.3.1  Tipo Bool