Ordenação de Dados - II

O que resultaria da tentativa de usar a definição apresentada em "Ordenação de Dados - I" para uma lista com repetição?

> ordena [3,5, 4,2,6,5]
[2,3,4,5,
Program error: pattern match failure: head []

como o valor 5 se repete, e sua segunda ocorrência é desconsiderada, o elemento de índice 4 da lista ordenada não existe e assim, a lista de elementos para i igual a 4 é vazia e portanto a apliação de head [ ] falha.

Há como contornar a situação? A definição anterior pode ser estendida para contemplar a repetição?

Podemos voltar à definição apresentada na postagem anterior e verificar que na se deixarmos de usar a a operação head xs, na definição de "elempos i xs", teriamos como resultado uma lista de listas.

menores y xs = [x | x<-xs, x <>
qmen y xs = length (menores y xs)
elempos i xs = [ x | x <-xs, qmen x xs == i]
ordena xs = [ elempos i xs | i <- [0..length xs -1]]

> ordena [8, 7, 5 , 9, 20, 4, 2]
[[2],[4],[5],[7],[8],[9],[20]]

e agora, aplicando a definição para uma lista com repetição, obtemos:

> ordena [3,5, 3, 4,2,6,5, 3]
[[2],[3,3,3],[],[],[4],[5,5],[],[6]]

podemos observar que no caso de repetição, surgem n-1 listas vazias, correspondendo ao elementos que por serem repetidos se associam no índice anterior.

Estamos a um passo da solução. Podemos concatenar todas as listas e assim obtermos o resultado desejado.

ordena xs = concat [ elempos i xs | i <- [0..length xs -1]]

> ordena [3,5, 3, 4,2,6,5, 3]
[2,3,3,3,4,5,5,6]
> ordena [8, 7, 5 , 9, 20, 4, 2]
[2,4,5,7,8,9,20]

Como podemos agora refrasear a nossa descrição informal da solução?