Para principiantes, esta é uma atividade que traz bastante dificuldades. Há uma forte inclinação em descrever como ordenar uma lista, em detrimento da preocupação com a descrição do que é uma lista ordenada.
Vamos primeiro restringir nosso problema de ordenação: comecemos pela ordenação crescente de uma lista de números inteiros distintos.
No primeiro passo, a descrição informal, devemos encontrar uma propriedade de lista ordenada crescente de números inteiros distintos, que seja aderente ao mecanismo List Comprehension.
Descrevendo Informalmente:
- em uma lista ordenada crescente de números distintos, o índice de um elemento é igual à quantidade de elementos menores que ele na referida lista;
- que pode ser reescrita como: para cada índice i, de uma lista ordenada, o i-ésimo elemento é aquele que possui exatamente i elementos menores que ele na lista.
Formalizando:
--
-- a ordenação de xs é uma lista formada por elempos i xs, tal que i pertence ao intervalo de
-- indexação de xs
--
ordena xs = [ elempos i xs | i <- [0..length xs - 1]]
--
-- o elemento de xs que tem posição i é o cabeça da lista dos elementos x pertencentes xs tal
-- que a quantidade de menores que x em xs é igual a i
--
elempos i xs = head [ x | x <-xs, qmen x xs == i]
--
-- a quantidade de menores que x em xs é o tamanho da lista de menores
--
qmen y xs = length (menores y xs)
--
-- a lista de elementos de xs menores que y é formada pelos elementos de xs que satisfazem a
-- propriedade: y <>
--
menores y xs = [x | x<-xs, x <>
vejamos alguns exemplos de uso, rodando em HUGS para windows:
Testando a Solução
> ordena [7, 3, 5, 2, 9, 4, 6, 1, 10, 0]
[0,1,2,3,4,5,6,7,9,10]
> ordena [100]
[100]
> ordena []
[]
> ordena [10,9..0]
[0,1,2,3,4,5,6,7,8,9,10]
Alguns possíveis prosseguimentos:
- e se a a lista possui elementos repetidos?
- e se a ordem desejada for decrescente?
- e se a lista for formada por elementos de outro tipo?
Nenhum comentário:
Postar um comentário