Introdução a Haskell

Funções

Uma função é a definição de uma expressão matemática que recebe um ou mais variáveis de entrada e retorna um valor de saída. No Haskell as funções contém apenas uma única instrução (embora possamos fragmentar tal instrução em múltiplas linhas). Ex.:

media :: Double -> Double -> Double
media x y = (x + y) / 2.0

A função média é descrita em apenas uma linha, recebe dois parâmetros do tipo Double e retorna um Double que é a média aritmética dos valores de entrada.

Um outro exemplo é o cálculo das raízes de uma equação do segundo grau, definida pelos valores de a, b, c:

raizSegGrau :: Double -> Double -> Double -> (Double, Double)
raizSegGrau a b c = ((-b - (sqrt (b**2 - 4*a*c)))/(2*a), (-b + (sqrt (b**2 - 4*a*c)))/(2*a))

A definição da função em uma linha, para esse caso, se torna confusa e repetitiva. A leitura dessa solução torna difícil sua manutenção e validação. Uma forma de quebrar essa expressão em múltiplas linhas é com a instrução where que permite a descrição da expressão principal de forma clara e a explicação detalhada de cada parte da expressão nas linhas seguintes:

raizSegGrau :: Double -> Double -> Double -> (Double, Double)
raizSegGrau a b c = (x1, x2)
  where
    x1 = (-b - sqrt delta) / (2*a)
    x2 = (-b + sqrt delta) / (2*a)
    delta = b**2 - 4*a*c

Nesse caso lemos que a função raizSegGrau recebe como parâmetro os valores a, b, c e retorna uma tupla (x1, x2), sendo que x1 é definido por (-b - sqrt delta) / (2*a), x2 por (-b + sqrt delta) / (2*a) e delta por b**2 - 4*a*c. Dessa forma, a expressão matemática se torna mais clara e melhor definida.

Para o Haskell entender a hierarquia das definições, a instrução where deve estar indentada em relação ao nome da função e as definições seguintes indentadas em relação ao where. Por convenção, indentamos com dois espaços o where e quatro espaços os demais.

Essa função irá retornar as raízes reais de qualquer equação do segundo, porém, nos casos em que a raíz é negativa, ela retornará (NaN, NaN) que significa Not a number. Podemos tratar esses casos específicos com o uso de guards, que são definições condicionais de padrões possíveis esperados da expressão:

raizSegGrau :: Double -> Double -> Double -> (Double, Double)
raizSegGrau a b c
  | delta < 0 = error "Raízes negativas!"
  | otherwise = (x1, x2)
  where
    x1 = (-b - sqrt delta) / (2*a)
    x2 = (-b + sqrt delta) / (2*a)
    delta = b**2 - 4*a*c

O guard representado por |, define condições especiais para a função. Devemos ler a função agora como a função raizSegGrau recebe como parâmetro os valores a, b, c e, se o delta for negativo emite uma mensagem de erro, caso contrário retorna a tupla contendo as raízes.

Note que a primeira linha de definição da função não contém o símbolo =, sendo esse utilizado apenas após as condições necessárias para a escolha do retorno da função. A instrução error emite uma mensagem de erro e encerra o programa.

Exercício 01: Escreva uma função para calcular a média entre dois valores x e y ponderado por w e definida por \(w \cdot x + (1 - w) \cdot y\). Note que para essa expressão funcionar, w deve ser definido no intervalo \([0, 1]\).

mediaPond :: Double -> Double -> Double -> Double

Exercício 02: Escreva uma função que recebe três valores numéricos e retorna uma tripla com esses valores em ordem crescente. Utilize os guards para definir todas as 6 possibilidades. Repare que a assinatura da função deve conter a classe Ord que define todos os números que permitam comparação.

crescente3 :: (Ord a, Num a) => a -> a -> a -> (a, a, a)

Uma outra forma de definir funções com casos especiais é através do pattern matching. Considere uma função chamada numero7 que retorna a string “Você ganhou!” sempre que a entrada for igual a 7 e “Você perdeu :(“, caso contrário. Podemos introduzir múltiplas definições da função para cada caso:

numero7 :: Integer -> String
numero7 7 = "Você ganhou!"
numero7 x = "Você perdeu :("

Em outro exemplo, imagine que queremos simplificar a função soma para os casos em que um dos valores seja igual a zero:

soma :: (Eq a, Num a) => a -> a -> a 
soma 0 y = y
soma x 0 = x
soma x y = x + y

A classe Eq indica que queremos aplicar a função para todos os valores numéricos que possam ser comparados com o operador de igualdade. Isso é necessário pois comparamos o valor de x e y com 0.

Similarmente, vamos definir uma função mult:

mult :: (Eq a, Num a) => a -> a -> a 
mult 1 y = y
mult x 1 = x
mult 0 _ = 0
mult _ 0 = 0
mult x y = x * y

O símbolo _ indica que não nos importamos com o valor dessa variável, uma vez que o resultado será sempre o mesmo independente do valor dela.

É importante notar que no Haskell os padrões e os guards são avaliados na ordem. Considere as seguintes funções:

maiorMenor1 :: (Ord a, Num a) => a -> String
maiorMenor1 x
  | x <= 5 = "Menor"
  | x >= 5 = "Maior"
  
maiorMenor2 :: (Ord a, Num a) => a -> String
maiorMenor2 x
  | x >= 5 = "Maior"  
  | x <= 5 = "Menor"

Essas duas funções retornarão um resultado diferente para x = 5 pois a igualdade é prioritária na primeira ocorrência.

Exercício 03: Crie uma função que retorne True caso o ano seja bissexto e False caso contrário. Um ano é bissexto se ele for divisível por 400 ou se ele for divisível por 4 mas não por 100. Crie três guards para essa definição.

bissexto :: Integer -> Bool
bissexto ano

Composição de Funções

Vamos imaginar que temos duas funções: uma para calcular a média ponderada das provas e outra para transformar a média final em conceito:

mediaFinal :: Double -> Double -> Double
mediaFinal p1 p2 = 0.4*p1 + 0.6*p2

conceito :: Double -> Char
conceito media
  | media < 5 = 'F'
  | media < 6 = 'D'
  | media < 7 = 'C'
  | media < 8 = 'B'
  | otherwise = 'A'

Digamos que queremos agora definir uma função chamada geraConceito que retorna o conceito final a partir das notas p1, p2. Podemos criar essa função como uma composição de funções. Podemos criar:

geraConceito :: Double -> Double -> Char
geraConceito p1 p2 = conceito $ mediaFinal p1 p2

O símbolo $ indica a prioridade de avaliação, primeiro o lado direito é avaliado e o resultado passado para a função do lado esquerdo.

Quando queremos compor funções de uma variável, podemos utilizar a notação matemática \((g \circ f)(x) = g(f(x))\), utilizando o símbolo .:

nota :: Double -> Double
nota x = x*2

conceito :: Double -> Char
conceito x
  | x > 5 = 'A'
  | otherwise = 'F'

calcConceito = conceito . nota

main = do
  print (calcConceito 5) -- imprime 'A'

Recursão

Um conceito bastante poderoso para abstração e definição de funções é a recursão, ou seja, funções definidas por um caso base e um caso de redução que é definida pela própria função. Vimos um exemplo na definição do algoritmo de Euclides para determinar o máximo divisor comum:

mdc :: Integer -> Integer -> Integer
mdc 0 b = b
mdc a 0 = a
mdc a b = mdc b (a `rem` b)

Os casos bases desse algoritmo são definidos quando um dos dois parâmetros é igual a zero, nesse caso existindo uma resposta bem definida. Para os outros casos, reduzimos o problema definindo a função através da própria mas com parâmetros reduzidos.

A ideia por trás dessa definição é de que, a cada chamada da função mdc os parâmetros a, b se tornem cada vez menores até que eventualmente um deles se torne 0 permitindo a obtenção do resultado.

Considere a definição do fatorial:

Podemos definir essa função recursivamente como:

Temos as definições bases para os casos com resultado conhecido e a definição genérica para calcularmos casos desconhecidos. Ao tentar calcular $4!$ seguindo tal definição, faríamos os seguintes passos:

No Haskell temos:

fatorial :: Integer -> Integer
fatorial 0 = 1
fatorial 1 = 1
fatorial n = n * fatorial (n-1)

Exercício 04: O número de Fibonacci é definido por:

Escreva a função correspondente em Haskell.

fibonacci :: Integer -> Integer

Nota: as linguagens de programação imperativas e orientadas a objeto implementam a recursão com o conceito de pilhas. Para isso a cada chamada recursiva da função todo o estado atual da memória é armazenado, a chamada atual é suspensa enquanto aguarda o retorno da função recursiva. Considere o caso do fatorial(5):

fatorial(5) = 5 * fatorial(4) // armazena todo o estado da função na pilha fatorial(4) = 4 * fatorial(3) // armazena mais esse estado na pilha, etc.

Isso ocasiona o chamado estouro de pilha (stack overflow) quando armazenamos muitas chamadas recursivas na memória através da pilha. No Haskell, por conta da avaliação preguiçosa, ele não armazena o estado da chamada anterior, mas apenas expande a expressão como uma promessa de cálculo realizando o cálculo de forma similar ao que fazemos manualmente. Ao invés de pilha de estado, ele usa uma pilha de expressão a ser avaliada, o que na prática aumenta a capacidade de avaliar expressões maiores sem ocorrer estouro de pilha. Para evitar tais problemas utilizamos o conceito de recursão caudal.

Recursão caudal

A recursão caudal ocorre quando a expressão de retorno de uma função recursiva consiste apenas da chamada recursiva. Ex.:

fatorial n = n * fatorial (n-1) -- não é caudal, pois existe um n * a ser avaliado
gcd a b = gcd b (a `rem` b)     -- caudal, pois o retorno consiste apenas da chamada de gcd

Muitas funções recursivas podem ser facilmente convertidas para uma recursão caudal. Considere a função fatorial:

fatorial :: Integer -> Integer
fatorial 0 = 1
fatorial 1 = 1
fatorial n = fatorial' n 1
  where
    fatorial' 1 r = r
    fatorial' n r = fatorial' (n-1) (n*r)

A função fatorial passou a definir uma função auxiliar fatorial' de dois parâmetros, um do número que queremos calcular o fatorial e outro armazenando os resultados parciais. Vamos simular a execução de fatorial' 4 1 para entendermos como o cálculo é realizado:

fatorial' 4 1 = fatorial' 3 4 = fatorial' 2 12 = fatorial' 1 24 = 24

Essa forma de recursão é facilmente otimizada pelo compilador para evitar problemas de estouro de pilha. Quando tratarmos do conceito de Listas aprenderemos uma forma simples de calcular o número de fibonacci sem utilizar recursão não-caudal.

Exercício 05: Crie a função multEtiope que define o conceito de Multiplicação Etíope. A multiplicação etíope pode ser descrita como, dados dois valores inteiros m, n, se m for ímpar, o resultado será n adicionado do resultado de multEtiope (m `div` 2) (n*2), caso contrário será igual o resultado de multEtiope (m `div` 2) (n*2). Quando m = 1 o resultado será n. Tente modificar a função recursiva para se tornar caudal.