Polimorfismo, classes e inferência de tipos

trocar (x,y) = (y,x) pode trocar um caráter e um booleano sem saber o que significam. O tipo (a,b) -> (b,a) conserva essa liberdade. Em duplicar x = (x,x), as duas posições recebem o mesmo valor, por isso têm o mesmo tipo: a -> (a,a). As letras são variáveis de tipo, distintas dos nomes x e y no programa.

Generalidade sem operações específicas

trocar (x,y) = (y,x)
duplicar x = (x,x)
primeiro (x:_) = x

As funções apenas deslocam ou selecionam valores, por isso os tipos mais gerais são (a,b) -> (b,a), a -> (a,a) e [a] -> a. A última função é parcial: a generalidade do tipo não resolve a ausência de uma equação para []. Um tipo pode estar certo mesmo que a função falhe ou não termine para certas entradas.

Uma lista impõe o mesmo tipo aos elementos. Uma lista de funções também segue essa regra: [reverse,tail] pode ter tipo [[a] -> [a]]. Cada elemento é uma função de lista para lista; a lista exterior não é uma função. Já (reverse,length) é um par e pode juntar resultados de tipos diferentes.

Operações acrescentam restrições

contem x xs = x `elem` xs
maior x y = if x >= y then x else y
media x y = (x+y)/2

elem compara valores, por isso contem :: Eq a => a -> [a] -> Bool. A comparação >= pede Ord a, dando maior :: Ord a => a -> a -> a. A divisão / pede Fractional a, que já exige Num a; por isso media :: Fractional a => a -> a -> a. Não é preciso acumular a restrição redundante Num a nessa assinatura.

Uma classe agrupa tipos com operações comuns, ou seja não é uma classe de objetos com herança e campos. Num nos GHC atuais não tem Eq como superclasse. Precisar de aritmética e de igualdade pode portanto exigir (Num a, Eq a). Uma árvore da hierarquia antiga não deve ser usada para retirar essa restrição.

Deduzir um tipo passo a passo

Aplicação repetida

Para duas f x = f (f x), começa com x :: a e f :: b -> c. As duas chamadas usam o mesmo f:

As igualdades dão a = b = c, logo duas :: (a -> a) -> a -> a. Não há operações sobre os valores, por isso não precisamos de uma classe; instanciar a com Int permite usar (+1) e com Bool permite usar not.

Duas medianas com restrições diferentes

Compara duas formas de calcular a mediana de três valores. Por comparações, basta ordenar só com (<=):

inserirOrd :: Ord a => a -> [a] -> [a]
inserirOrd x [] = [x]
inserirOrd x (y:ys)
  | x <= y    = x : y : ys
  | otherwise = y : inserirOrd x ys

ordenar3 :: Ord a => a -> a -> a -> [a]
ordenar3 a b c = inserirOrd c (inserirOrd b [a])

medianaOrd :: Ord a => a -> a -> a -> a
medianaOrd x y z = head (tail (ordenar3 x y z))

ordenar3 3 1 2 insere 1 em [3] para [1,3] e depois 2 para [1,2,3], dando mediana 2; só usa (<=), por isso só pede Ord a. Se calculares pela soma e pelos extremos, como (x + y + z - minimum [x,y,z] - maximum [x,y,z]), usas (+) e (-) e o tipo passa a (Ord a, Num a) => a -> a -> a -> a, excluindo tipos ordenados sem aritmética como listas de carateres. Lê a restrição como registo das operações usadas.

A versão aritmética também depende das operações concretas do tipo. Em vírgula flutuante, o arredondamento pode perder informação. Com x=1e20, y=1 e z=2, a soma dos três arredonda para 1e20; retirar o máximo e o mínimo já não recupera a mediana 2.

O tipo permite a operação, mas não prova a equivalência matemática para todos os valores. Lê a restrição como registo das operações usadas, não como garantia de que duas fórmulas coincidem em todos os tipos.

Em selecionar p xs = [x | x <- xs, p x], se xs :: [a] então cada x :: a. Como a condição da compreensão tem tipo Bool, p :: a -> Bool e o resultado volta a ser [a], dando (a -> Bool) -> [a] -> [a]. A compreensão não acrescenta restrições: lê-as nas funções usadas dentro dela.

Em f x y = [x,y+1], a lista iguala os tipos de x e y, por isso + acrescenta Num a sem obrigar a Int. O tipo mais geral é Num a => a -> a -> [a]. Uma assinatura mais específica pode compilar, mas não responde ao pedido de tipo mais geral.

Aplicação e setas

a -> b -> c significa a -> (b -> c): a função recebe um a e devolve uma função de b para c. A aplicação associa no sentido oposto: f x y significa (f x) y. O tipo (a -> b) -> a -> b recebe uma função no primeiro argumento; retirar esses parênteses muda o tipo.

O operador . exige que a saída da segunda função possa entrar na primeira:

(.) :: (b -> c) -> (a -> b) -> a -> c

length . filter even recebe uma lista de inteiros e devolve Int, com a restrição Integral a vinda de even, pois length não inspeciona os elementos; o tipo especializado a listas é Integral a => [a] -> Int.

Números e conversões

O literal 3 pode ser usado em qualquer instância de Num; 3.5 exige Fractional, por isso a expressão length xs + 0.5 falha porque length xs :: Int, e Int não é Fractional. Usa fromIntegral (length xs) para obter um valor compatível com a divisão ou soma fracionária. A conversão não acontece automaticamente.

div e mod arredondam o quociente para baixo; quot e rem truncam-no para zero. Para -7 e 3, temos div=-3, mod=2, quot=-2, rem=-1. Em ambos os pares vale a = q*b+r, com b diferente de zero. Escolher um par e depois usar o resto do outro quebra essa relação.

duasVezes :: (a -> a) -> a -> a
duasVezes f x = f (f x)
main :: IO ()
main = do
  print (duasVezes (+1) (4::Int))
  print (duasVezes not True)
  print ((-7) `div` 3, (-7) `mod` 3, (-7) `quot` 3, (-7) `rem` 3)

Para conferir a tua dedução, usa :t nome no GHCi. Dependendo da versão, funções como length e elem podem aparecer generalizadas a Foldable, em vez de listas. A instância especializada a [a] usada nas aulas continua válida; não interpretes essa diferença como um erro da tua dedução.