Funções recursivas

No Haskell não temos loops como for e while, em vez disso usamos funções recursivas, que são funções que no final de sua execução chamam elas mesmas de volta. Na verdade elas são muito parecidas com os loops de repetição.

Vamos fazer uma função que receba como parâmetro um inteiro n e retorne a soma dos números pares entre 0 e n.

Em uma linguagem imperativa como o C, a função ficaria mais ou menos assim:

int soma_pares(n) {
    int sum = 0;
    for (int i=0; i < n; i++){
        if (n % 2 == 0){
            sum += n;
        }
    }
    return sum;
}

Já em Haskell ela fica assim:

somaPares 0 = 0
somaPares n =
    if mod n 2 == 0 then n + somaPares (n - 1)
    else somaPares (n - 1)

Perceba que se a condição mod n 2 == 0 for atendida, o resultado da função será o valor n somado ao valor da próxima chamada da função que será somaPares (n - 1), o resultado vai acumulando até que o n seja igual a zero, que é o caso de parada.

Listas

Tipos

• [1, 1, 2, 3, 5, 8, 13] == (Num a) => [a]
• [True, False, False, True] == [Bool]
• [‘H’, ‘a’, ‘s’, ‘k’, ‘e’, ‘l’, ‘l’] == [Char] ou String

Estrutura

• [] faz uma lista vazia
• x:xs faz uma lista com cabeça x e cauda xs
• [1, 2, 3, 4] == 1: (2: (3: (4: [])))
• [1, 2, 3, 4] == 1:2:3:4:[]
• toda lista termina com a lista vazia: []

Operadores de lista

• x:xs junta um elemento x a uma lista xs
• [x] ++ xs junta uma lista [x] a uma lista xs

Funções com listas

tamanho :: [a] -> Int --declaração de tipo
tamanho [ ] = 0 --caso de parada
tamanho (x:xs) = 1 + tamanho xs

• a cada iteração, a função tira o primeiro termo da lista e soma 1, retornando no final o numero de elementos
• essa função esta implementada na biblioteca prelude com o nome de length, onde length :: [a] -> Int

somatorio :: (Num a) -> [a] -> a
somatorio [ ] = 0
somatorio (x:xs) = x + somatorio xs

• a cada iteração, a função tira o primeiro termo da lista e o adiciona ao somatório, retornando no final a soma dos termos
• essa função esta implementada na biblioteca prelude com o nome de sum, onde sum :: [a] -> Int

nprimeiros :: Int -> [a] -> [a]
nprimeiros 0 _ = [ ]
nprimeiros _ [ ] = [ ]
nprimeiros n (x:xs) = x : nprimeiros (n - 1) xs

• essa função exibe os n primeiros elementos de uma lista
• essa função esta implementada na biblioteca prelude com o nome de take

Tuplas

• As tuplas são muito parecidas com as listas, mas são feitas neste formato:(a, b)
• As tuplas também possuem cauda e cabeça, então o (x:xs) ainda funciona
• Quando temos listas de tuplas é possível fazer ((x,y):xys) para referenciar os elementos (x, y) de uma tupla dentro de uma lista

primeiro (a, b) -> a
primeiro (x, y) = x
-- como não precisamos no valor de y podemos substituí-lo por um _
primeiro (x, _) = x

--funcionamento desejado
> zip' [1, 2, 3] "abcd"
[(1, 'a'), (2, 'b'), (3, 'c')]
--implementação
zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = [] --se um dos elementos for vazio retorne lista vazia
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

unzip' :: [(a,b)] -> ([a], [b])
unzip' [] = ([], [])
unzip' ((x,y):xys) = x:fst (unzip' xys), y:snd (unzip' xys)

Um pouco (bem pouco) de cálculo λ

O cálculo lambda é composto de 3 elementos:

• Váriaveis
• Definição de funções (abstração)
• Aplicação de funções Vamos ver um exemplo:

e ::= x
    | \x -> e --uma função que recebe x e devolve e
    | e1 e2

Nesse caso temos:

• Variável = x
• Abstração = \x -> e
• Aplicação = e1 e2 (aplique o argumento e2 na função e1) e1(e1(e2))

Alguns exemplos de funções:

\x -> (\y -> y) -- recebe 2 args e retorna o segundo
\x -> (\y -> x) -- recebe 2 args e retorna o primeiro
-- simplificando...
\x y -> y
\x y -> x

dica: sempre que ver um \ lembre-se do λ

Fold

A função fold tem duas variações: foldr e foldl, o que muda de uma para outra é o sentido em que a função é aplicada(e a ordem dos argumentos). Meu entendimento dessa função ainda é muito limitado, mas consegui fazer um contador com ela:

Essa função conta as palavras de um frase (na verdade ela conta os espaços em branco e subtrai 1 para assim chegar no valor correto). Perceba que eu utilizei a opação acc no foldr e apliquei uma condição para incrementar o contador.

contaPalavras :: (Num a) => [Char] -> a
count e (x:xs)= foldr (\x acc -> if e==x then acc+1 else acc ) 1 (x:xs)
contaPalavras (x:xs) = count ' ' (x:xs)

Funções High Order

em breve

Escrito por Vinícius Hansen

• Github: https://github.com/ViniciusHansen
• Discord: Vinicius Hansen#2665