Sucesiones auto descriptivas en Haskell

En las Olimpiadas de Matemáticas del 2001 se propuso el siguiente problema

Buscar todas las sucesiones finitas (x(0), x(1),…,x(n)) tales que para todo j, 0 ≤ j ≤ n, x(j) es igual al número de veces que aparece j en la sucesión.

Las sucesiones que cumplen la anterior condición se llaman auto descriptivas. Un ejemplo de sucesión auto descriptiva es [5,2,1,0,0,1,0,0,0] ya que

  • el 0 aparece 5 veces,
  • el 1 aparece 2 veces,
  • el 2 aparece 1 vez,
  • el 3 aparece 0 veces,
  • el 4 aparece 0 veces,
  • el 5 aparece 1 vez,
  • el 6 aparece 0 veces,
  • el 7 aparece 0 veces y
  • el 8 aparece 0 veces.

En la siguiente relación de ejercicios, elaborada para la asignatura de Informática (de 1º del Grado en Matemáticas) y para la siguiente versión del libro Piensa en Haskell, se resuelve el problema con Haskell.

En el último ejercicio sólo se ha hecho una comprobación, para completar el problema queda pendiente demostrar formalmente la propiedad.