Haskell/Soluções: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
→‎Listas e n-uplas: Adição de mais um capítulo e rebaixando o nível de todas as seções
Linha 1:
= Básico =
 
== [[Haskell/Variáveis e funções|Variáveis e funções]] ==
 
Linha 205 ⟶ 207:
# <source lang=haskell>
h :: Int -> a -> b -> Char -- y e z não são usados, portanto, seus tipos não importam e nem precisam ser iguais
</source>
 
 
= Introdutório =
 
== [[Haskell/Recursividade|Recursividade]] ==
 
=== Recursividade numérica ===
 
{{Exercício|1=
# O que acontece se calcularmos <code>fatorial (-1)</code>?
# Como já vimos antes, a ordem dos padrões é importante quando definimos uma função. Se fizéssemos <source lang="haskell">
fatorial n = n * fatorial (n - 1)
fatorial 0 = 1
</source> e tentássemos calcular <code>fatorial 6</code>, o que aconteceria?
# O ''fatorial duplo'' de um número é a multiplicação dos sucessores intercalados, partindo de 1 (ou 2) até o argumento. Por exemplo: o fatorial duplo de 8 é 8 × 6 × 4 × 2 = 384; o fatorial duplo de 7 é 7 × 5 × 3 × 1 = 105. Defina uma função <code>fatorialDuplo</code> em Haskell que faça esta conta.
}}
 
# O compilador começaria a avaliar<br /><code>(-1) * fatorial (-2)</code><br /><code>(-1) * (-2) * fatorial (-3)</code><br /><code>(-1) * (-2) * (-3) * fatorial (-4)</code><br />e assim por diante. Como a definição de <code>fatorial</code> não possui nenhum caso que impeça essa expansão, o compilador começaria o processo mas nunca consegueria terminá-lo corretamente.
# O compilador avaliaria corretamente até <code>6 * 5 * 4 * 3 * 2 * 1 * fatorial 0</code>. Neste ponto, ele deveria encerrar a recursividade, mas como um argumento <code>0</code> satisfaz a condição do primeiro caso, o caso base nunca seria avaliado e a expansão do fatorial continuaria pelos números negativos. O resultado seria o mesmo que o do exercício anterior.
# <source lang="haskell">
fatorialDuplo 1 = 1
fatorialDuplo 2 = 2
fatorialDuplo n = n * fatorialDuplo (n - 2)
</source>
 
{{Exercício|1=
# Defina uma função recursiva chamada <code>potencia</code> tal que o resultado de <code>potencia x y</code> seja <code>x</code> elevado à potência <code>y</code>.
# Lhe é dada a função <code>maisUm x = x + 1</code>. Sem usar <code>(+)</code> novamente, e usando apenas <code>maisUm</code> e <code>(-)</code>, defina a função recursiva <code>adicao</code> tal que <code>adicao x y</code> resulte na soma de <code>x</code> e <code>y</code>. Considere apenas números inteiros não-negativos.
# Escreva a função <code>log2</code> que calcula o logaritmo de seu argumento na base 2. Por exemplo: <code>log2 1024 = 10</code>, <code>log2 1 = 0</code>, <code>log2 11 = 3</code>. Dica: use números inteiros, e use <code>div x y</code> (uma função nativa de Haskell) para calcular o quociente da divisão de <code>x</code> por <code>y</code>.
}}
 
# <source lang=haskell>
potencia _ 0 = 1
potencia x y = x * potencia x (y - 1)
</source>
# <source lang=haskell>
adicao x 0 = x
adicao x y = adicao (maisUm x) (y - 1)
</source>
# <source lang=haskell>
log2 1 = 0
log2 x = 1 + log2 (div x 2)
</source>
 
=== Recrusividade usando listas ===
 
{{Exercício|1=
Escrevas as seguintes funções de forma recursiva. Note que todas elas já possuem uma versão nativa no Prelude. Você pode usar dois casos base, caso ache necessário, apesar de que todos podem ser resolvidos com apenas um.
# <code>replicar :: Int -> a -> [a]</code>, que recebe um contador ''n'' e um elemento, e retorna uma lista contendo ''n'' elementos iguais aos da entrada. Ex.: <code> replicar 3 2 = [2,2,2]</code>. A versão do Prelude chama-se <code>replicate</code>.
# <code>(!!!) :: [a] -> Int -> a</code>, que recebe uma lista e um índice de posição, e retorna o elemento contido em tal posição dentro da lista. O primeiro elemento da lista está na posição 0. Ex.: <code>"abcde" !!! 2 = 'c'</code>. A versão do Prelude chama-se <code>(!!)</code>.
# <code>ziper :: [a] -> [b] -> [(a,b)]</code>, que age como um ziper entre duas listas, isto é, pega um elemento de cada lista, forma uma dupla, e retorna uma lista de duplas. Ex.: <code>ziper [1,2,3,4] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]</code>. Perceba que a ação é interrompida quando o limite da lista mais curta é atingido. A versão do Prelude chama-se <code>zip</code>.
# Redefina <code>length</code> usando uma função interna auxiliar e um parâmetro acumulador.}}
 
# <source lang=haskell>
replicar :: Int -> a -> [a]
replicar 0 _ = []
replicar n x = x : replicar (n - 1) x
</source>
# <source lang=haskell>
(!!!) :: [a] -> Int -> a
(x:xs) !!! 0 = x
(x:xs) !!! n = xs !!! (n - 1)
</source>
# <source lang=haskell>
ziper :: [a] -> [b] -> [(a,b)]
ziper [] _ = []
ziper _ [] = []
ziper (x:xs) (y:ys) = (x,y) : ziper xs ys
</source>
# <source lang=haskell>
minhaLength :: [t] -> Int
minhaLength l = go l 0
where go [] n = n
go (x:xs) n = go xs (n+1)
</source>