Haskell Hero

Hasta ahora hemos definido listas escribiendo elementos individuales. Es decir, cuando necesitabamos una lista de números enteros desde uno hasta cinco, lo escribimos de esta manera: [1,2,3,4,5]. Escribir tal lista no es un problema. Sin embargo, esta solución es inadecuada cuando necesitamos por ejemplo una lista de números desde uno hasta ciento. O por ejemplo desde uno hasta un millón. O incluso una lista infinita desde uno hasta el infinito. En este momento nos ayudan rangos.

La lista de números desde uno hasta cinco escribimos como [1..5]. Entonces no hay problema con la lista desde uno hasta un millón: [1..1000000]. La lista desde uno hasta el infinito la definimos de manera similar, sin especificar el límite superior [1..]. Si dejamos Hugs evaluar la expresión [1..], Hugs empezará imprimir indefinidamente números desde uno hasta el infinito. Podemos interrumpir lo pulsando Ctrl+C.

Ejemplos

[1..10]        ~>*  [1,2,3,4,5,6,7,8,9,10]
[10..]          =   [10,11,12,13,14,15, ... ]
take 3 [10..]  ~>*  [10,11,12]
[20..10]       ~>*  []
['a'..'f']     ~>*  "abcdef"

Después nos gustaría tener una lista de todos números impares desde uno hasta diez. Esta podemos escribir de manera siguiente: [1,3..10], en general [m,s..n]. El valor m indica el primer elemento de la lista, s indica el segundo elemento, la resta de s y m nos indica la diferencia entre elementos vecinos de la lista y n indica el límite superior (si se trata de una lista creciente) o inferior (si se trata de una lista descendiente).

Si s es superior a m, la lista resultante será creciente. Si s es inferior a m, la lista resultante será descendiente. Si s == m, la lista resultante será constante. En este caso podemos también usar la variante infinita sin un límite superior/inferior.

Ejemplos

[1,3..10]       ~>*  [1,3,5,7,9]
[10,20..]        =   [10,20,30,40,50 ... ]
[1,2..0]        ~>*  []
[10,9..1]       ~>*  [10,9,8,7,6,5,4,3,2,1]
[10,9..20]      ~>*  []
['f','d'..'a']  ~>*  "fdb"
['&','&'..]      =   "&&&&&&&&&&&& ... "

Ejemplo

Definid una lista creciente de todos los números desde uno hasta un millón que son o pares o divisibles por cinco.

Ya sabemos de clases de matemática como escribir un conjunto de números que cumplan estas condiciones:

{ x | x es del conjunto {1,..., 1000000},
      x es par o es divisible por 5}

[ x | x <- [1..1000000], even x || x `mod` 5 == 0]

even x || x `mod` 5 == 0

La construcción x <- s, donde s es una lista, se llama un generador.

¿Qué pasa cuando hay más generadores en la notación? Pongamos un ejemplo corto:

[ (x,y) | x <- [1..3], y <- [1..x] ]

• La variable x se sustituye por 1.
  • La variable y se sustituye por 1.
  • Se añade la dupla (1,1) a la lista final.
• La variable x se sustituye por 2.
  • La variable y se sustituye por 1.
  • Se añade la dupla (2,1) a la lista final.
  • La variable y se sustituye por 2.
  • Se añade la dupla (2,2) a la lista final.
• La variable x se sustituye por 3.
  • La variable y se sustituye por 1.
  • Se añade la dupla (3,1) a la lista final..
  • La variable y se sustituye por 2.
  • Se añade la dupla (3,2) a la lista final.
  • La variable y se sustituye por 3.
  • Se añade la dupla (3+3) a la lista final.

La lista final será entonces la siguiente:

[ (1,1), (2,1), (2,2), (3,1), (3,2), (3,3) ]

Otros ejemplos

[ 2*x | x <- [1..5] ]  ~>*  [2,4,6,8,10]

map    f s  =  [ f x | x <- s ]
filter p s  =  [  x  | x <- s, p x ]