Lambda, currying e ordem superior

soma 5 pode ser usada como uma função que acrescenta cinco ao próximo argumento. Isto acontece porque soma :: Int -> Int -> Int recebe um inteiro e devolve uma função Int -> Int. Esta forma de representar vários argumentos chama-se currying, e fixar alguns deles chama-se aplicação parcial.

Uma função de ordem superior recebe ou devolve uma função. map, por exemplo, recebe a transformação a aplicar a cada elemento; filter recebe o teste a aplicar. É esta parametrização por operações, e não apenas por dados, que torna estas funções reutilizáveis.

Aplicação parcial

soma :: Int -> Int -> Int
soma x y = x + y

soma5 :: Int -> Int
soma5 = soma 5

soma 5 é uma função à espera do segundo argumento, por isso soma5 3 dá 8. O mesmo vale para operadores por meio de secções: (>= 9.5) é a função que testa se o seu argumento é maior ou igual a 9.5, e (* 2) é a função que dobra. Quando precisares de uma função pequena só uma vez, escreve-a anónima com lambda: (\x -> x * 2) lê-se “a função que a x associa x * 2”.

As lambdas, também usadas em FP, definem funções sem nome. A aplicação parcial permite especializar uma função já existente sem escrever outra lambda. Atenção à subtração: (-2) é o número negativo; para retirar dois ao argumento, usa \x -> x - 2 ou subtract 2.

map, filter e foldr

O Prelude, importado por omissão, inclui estas funções de ordem superior. Estes tipos são as versões especializadas a listas:

map    :: (a -> b) -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]
foldr  :: (a -> b -> b) -> b -> [a] -> b

map transforma cada elemento, filter conserva os que passam no teste e foldr substitui a estrutura da lista por aplicações de uma operação, associadas à direita. A associação não obriga a avaliar primeiro a cauda. sum é foldr (+) 0 e length é foldr (\_ n -> n + 1) 0. Quando o problema for “transformar cada um”, “ficar só com alguns” ou “resumir tudo”, começa por estas antes de escreveres recursão à mão.

Média das aprovações

Dada uma pauta, queremos calcular a média das notas de aprovação. As notas podem ter parte decimal, por isso usamos [Double]. O resultado é Maybe Double, porque uma pauta sem aprovações não tem essa média; Maybe a tem dois construtores, Nothing para ausência e Just x para presença, e a expressão case escolhe a equação pelo construtor, como os padrões das funções.

mediaAprovados :: [Double] -> Maybe Double
mediaAprovados notas = case filter (>= 9.5) notas of
  [] -> Nothing
  xs -> Just (sum xs / fromIntegral (length xs))

Em [8,12,6,15,10], filter conserva [12,15,10]. A soma é 37 e o comprimento é 3, dando Just 12.333333333333334, porque a soma já é Double e só precisamos de converter o comprimento, que é Int. Com [2,7], o filtro produz [] e o resultado é Nothing. Podes usar where para dar nome a etapas intermédias, enquanto esta versão usa case para tratar as duas formas do resultado do filtro.

mediaAprovados :: [Double] -> Maybe Double
mediaAprovados notas = case filter (>= 9.5) notas of
  [] -> Nothing
  xs -> Just (sum xs / fromIntegral (length xs))

main :: IO ()
main = do
  print (mediaAprovados [8,12,6,15,10])
  print (mediaAprovados [2,7])
  print (foldr (-) 0 [1,2,3::Int])
  print (foldl (-) 0 [1,2,3::Int])
  print (take 5 (map (^2) [1..] :: [Integer]))

Uma versão que calcula sum xs / fromIntegral (length xs) na lista vazia faz 0/0, que em Double dá NaN, ou seja não é uma média. Além disso, a assinatura [Int] é incompatível com o literal 9.5 no filtro, por isso um tipo correto e um caso de ausência explícito resolvem problemas diferentes.

Do caso recursivo ao foldr

Escreve primeiro a soma por recursão:

soma [] = 0
soma (x:xs) = x + soma xs

Substitui [] por z e (:) por f. Obténs foldr f z: o caso vazio devolve z e o caso recursivo aplica f à cabeça e ao resultado da cauda. Assim sum = foldr (+) 0 e length = foldr (\_ n -> n + 1) 0. Escolhe foldr quando cada passo só precisa da cabeça e do resumo da cauda. Escolhe filter para selecionar e takeWhile para parar no primeiro que falha.

foldr contra foldl

O foldr combina da direita e o foldl da esquerda, na forma como as aplicações ficam aninhadas. Ambos percorrem a lista da esquerda para a direita; “direita” e “esquerda” descrevem os parênteses, não o ponto de partida. A diferença aparece quando a operação não é associativa. Compara a subtração:

somaD :: [Int] -> Int
somaD = foldr (+) 0

somaE :: [Int] -> Int
somaE = foldl (+) 0

foldr (-) 0 [1,2,3] calcula 1 - (2 - (3 - 0)), que dá 2. Já foldl (-) 0 [1,2,3] calcula ((0 - 1) - 2) - 3, que dá -6. Com inteiros sem overflow e (+), os dois concordam, e é por isso que o exemplo da média não distingue; com (-), a direção muda o resultado. (:) cabe diretamente em foldr; em foldl, é preciso inverter a ordem dos argumentos, como em flip (:).

soma :: [Int] -> Int
soma = foldr (+) 0
-- soma [1,2,3] = 1 + (2 + (3 + 0)) = 6

soma :: [Int] -> Int
soma [] = 0
soma (x:xs) = x + soma xs
-- soma [1,2,3] = 1 + (2 + (3 + 0)) = 6

Listas infinitas e preguiça

Haskell só calcula o que é preciso para responder, por isso uma lista infinita é um valor legítimo enquanto só consumires um prefixo finito:

ghci> take 5 (iterate (+1) 0)
[0,1,2,3,4]
ghci> take 3 (repeat "ola")
["ola","ola","ola"]

iterate (+1) 0 começa em 0 e obtém cada elemento aplicando (+1) ao anterior. take 5 exige apenas cinco células; a continuação fica por avaliar. length precisa de encontrar o fim, por isso não termina nesta lista infinita.

Escolher a função de ordem superior

takeWhile p conserva apenas o prefixo que satisfaz p; filter p continua a procurar depois de um elemento falhar. Produzir todo o resultado de uma lista finita exige percorrê-la; pedir só um prefixo pode exigir menos. Em [2,4,1,6], takeWhile even dá [2,4], enquanto filter even dá [2,4,6]. dropWhile even dá [1,6]. O 6 já não é testado para terminar o prefixo: a fronteira foi o primeiro 1.

all p xs é verdadeiro se todos os elementos satisfazem p; any p xs basta-se com um. Na lista vazia, all dá True e any dá False. Estas identidades permitem escrever and = foldr (&&) True e or = foldr (||) False.

Uma composição aplica primeiro a função mais à direita. Para sum . map (^2) . filter even em [1,2,3,4], seguimos:

Se precisas de ver a entrada de cada etapa, escreve primeiro a versão com argumento e nomes locais; só depois retira o argumento.

Se a dúvida é como a composição, o map e o fold se combinam, vê este vídeo e prevê cada resultado:

Graham Hutton, FP 10: Higher-Order FunctionsCarregar vídeo do YouTube

Abrir no YouTube

Derivar um fold

Para substituir a recursão de append xs ys, queremos trocar cada (:) de xs por (:) e o [] final por ys. Logo append xs ys = foldr (:) ys xs. Para concat, cada elemento já é uma lista: concat = foldr (++) [].

Inverter com foldl (flip (:)) [] coloca cada novo elemento na cabeça do acumulador. Os estados para [1,2,3] são [], [1], [2,1], [3,2,1]. Inverter com foldr (\x acc -> acc ++ [x]) [] também funciona numa lista finita, mas as concatenações repetidas tornam o tempo quadrático. A primeira versão percorre a lista em tempo linear.

O que a preguiça permite

Haskell só exige um resultado intermédio quando precisa dele. take 3 [1..] pede três células e termina; sum [1..] exige o fim de uma lista que não o tem. False && undefined é False, mas True && undefined falha ao pedir o segundo argumento. A ordem dos argumentos importa para este curto-circuito.

foldr (&&) True (False:repeat True) termina com False, porque && pode ignorar a cauda. foldl (&&) True nessa lista precisa de chegar ao fim e não termina. foldr não é uma promessa geral de terminação em listas infinitas: foldr (+) 0 [1..] também exige a cauda inteira.

foldl pode acumular uma cadeia de expressões por avaliar. foldl' de Data.List força o acumulador a cada passo até à forma normal fraca. É útil para somas grandes, mas não força necessariamente o interior de uma árvore ou de um tuplo. Distingue associatividade da operação, ordem de avaliação e custo em memória.

Contar um intervalo numa lista infinita ordenada

Queremos os primos entre 10 e 30, incluindo as fronteiras. A lista de primos está em ordem crescente. Primeiro retiramos os que são menores que 10; depois conservamos só o prefixo até 30:

intervalo inicio fim = takeWhile (<= fim) . dropWhile (< inicio)

O resultado é [11,13,17,19,23,29], com seis elementos. dropWhile chega ao primeiro primo admissível, 11. takeWhile para ao observar 31; pela ordenação, nenhum dos primos posteriores pode voltar ao intervalo. Assim, length só percorre a lista finita que acabou de ser delimitada.

primo :: Integer -> Bool
primo n = n > 1 && testar 2
  where
    testar d
      | d*d > n = True
      | n `mod` d == 0 = False
      | otherwise = testar (d+1)

primos :: [Integer]
primos = filter primo [2..]

intervalo :: Ord a => a -> a -> [a] -> [a]
intervalo inicio fim = takeWhile (<= fim) . dropWhile (< inicio)

main :: IO ()
main = do
  print (intervalo 10 30 primos)
  print (length (intervalo 10 30 primos))
  print (intervalo 13 23 primos)

length (filter (\p -> 10 <= p && p <= 30) primos) não termina: depois de 29, o filtro continua a procurar para sempre outro elemento que passe. Mesmo produzindo os seis elementos iniciais corretos, não consegue devolver o fim da lista. take 30 também responderia a outra pergunta: conta posições, não valores.

A ordenação é uma hipótese essencial. Numa lista arbitrária, parar no primeiro valor acima de 30 poderia perder um valor menor que aparecesse depois. Numa entrada infinita, precisamos também de alcançar a fronteira de paragem em passos finitos; uma lista infinita de 20 não a tem. Para listas finitas ordenadas, o fim da própria lista também permite terminar.