Questão 3: Escreva uma função recursiva ordena em Haskell que receba um lista p de números inteiros e retorne uma lista q com os elementos de p em ordem ascendente, conforme o exemplo:
> 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)
insere :: Int -> [Int] -> [Int]
insere y [] = [y]
insere y (z:zs)
| y <= z = y : z : zs
| otherwise = z : insere y zs

Exercícios relacionados