Questão 3: Escreva uma função recursiva ordena em Haskell que receba um lista
de números inteiros e retorne uma lista
com os elementos de
em ordem ascendente, conforme o exemplo:
> ordena [8, 4, -3, 0, 7, 12]
[-3, 0, 4, 7, 8, 12]
> ordena [8, 4, -3, 0, 7, 12]
[-3, 0, 4, 7, 8, 12]
Passo 1
Resumo do enunciado: precisamos implementar em Haskell uma função recursiva chamada ordena que receba uma lista de inteiros e retorne essa lista em ordem ascendente. O conteúdo envolve recursão, pattern matching e listas.
Passo 2
Definimos o caso base da recursão: se a lista for vazia, a ordenação retorna a lista vazia.
Passo 3
Para o caso recursivo: dividimos a lista em cabeça (x) e cauda (xs). Recursivamente ordenamos a cauda, gerando uma lista ordenada ys.
Passo 4
Precisamos de uma função auxiliar insere para inserir o elemento x na lista ordenada ys no lugar correto. Definimos insere com pattern matching: se a lista é vazia, retorna [y]; caso contrário, comparamos y com o primeiro elemento z para decidir a posição.
Passo 5
Reunimos tudo para escrever a função ordena usando ordena (x:xs) = insere x (ordena xs) e definimos insere conforme descrito.
Resposta
ordena :: [Int] -> [Int]
ordena [] = []
ordena (x:xs) = insere x (ordena xs)
ordena [] = []
ordena (x:xs) = insere x (ordena xs)
insere :: Int -> [Int] -> [Int]
insere y [] = [y]
insere y (z:zs)
| y <= z = y : z : zs
| otherwise = z : insere y zs
insere y [] = [y]
insere y (z:zs)
| y <= z = y : z : zs
| otherwise = z : insere y zs