Secuencias
Para poder manipular colecciones de elementos de una forma simple, el lenguaje incorpora la noción de secuencia. Las secuencias se definen de manera inductiva, con el valor [] de secuencia vacía y el operador : que a partir de un elemento y una secuencia de elementos (todos pertenecientes al mismo conjunto), retorna la secuencia resultante de agregar el elemento al principio de la secuencia dada.
suma :: R* -> R
suma(l) = 0 si l == []
{ primero(l) + suma(resto(l))
largo :: R* -> R
largo(l) = 0 si l == []
{ 1 + largo(resto(l))
conj RSeqNV = { l en R* | largo(l) /= 0 }
maximo :: RSeqNV -> R
maximo(l) = primero(l) si resto(l) == []
{ max(primero(l), maximo(resto(l)))
Por ejemplo, utilizando secuencias podemos definir la función "tienen", que dado un número de días, retorna todos los meses que tienen en total ese número de días (y la secuencia vacía si ningún mes los tiene):
tienen :: N -> Mes*
tienen(d) = [Abril, Junio, Setiembre, Noviembre] si d == 30
{ [Enero, Marzo, Mayo, Julio, Agosto, Octubre, Diciembre] si d == 31
{ [Febrero] si (d == 28, d == 29)
{ []
Además de esa forma de construcción de secuencias, la función rango permite construir secuencias de racionales a partir de un valor inicial, un valor final y un valor de paso. Por ejemplo rango(0,100,10) retorna la secuencia [0,10,20,30,40,50,60,70,80,90,100].
Para poder obtener los elementos de una secuencia existen las funciones destructoras primero y resto, que respectivamente retornan el primer elemento de una secuencia y la secuencia resultante de quitar el primer elemento. Por ejemplo la expresión primero(rango(0,100,10)) retorna el valor real 0 y resto(rango(0,100,10)) retorna la secuencia 10:20:30:40:50:60:70:80:90:100 :[]. Notar que en estos ejemplos hemos realizado composición de funciones, dado que a primero y resto les hemos pasado el resultado de aplicar la función rango. Es decir, hemos usado la expresión derecha de la definición de composición de funciones, que es: f . g (x) = f(g(x)), donde los dominios y codominios de f y g cumplen determinadas condiciones. También podemos usar la expresión izquierda y escribir por ejemplo, primero . rango(0,100,10).
Dado que el conjunto de secuencias de elementos de un comjunto A cualquiera se define inductivamente a partir de la secuencia vacía y la función "cons", es natural definir funciones sobre secuencias usando recursión. En la Figura 6 se muestran algunos ejemplos básicos: la función suma que toma una secuencia de reales y devuelve la suma de sus elementos. Si la secuencia es vacía el resultado es 0 (caso base) y si no, se suma el primer real al resultado de hacer la suma de las elementos del resto de la secuencia (caso inductivo). De forma similar se puede calcular la cantidad de elementos de una secuencia con la función largo. Para la función maximo, que calcula el máximo de una secuencia de reales no vacía, definimos un nuevo conjunto RSeqNV de secuencias no vacías como dominio de la función, para que la función sea total. Notar que dentro de las condiciones de los conjuntos se pueden utilizar funciones definidas en el mismo programa, como largo en RSeqNV.
Ejemplos de funciones que devuelven secuencias.
En los ejemplos de la Figura 6 el resultado es un real, veremos un par de ejemplos de funciones que devuelven secuencias.
La funcion inicial toma una secuencia de enteros y devuelve la secuencia sin el último elemento (el segmento inicial). La función tomar toma una seceuncia de enteros y un natural n, devuelve una secuencia con los primeros n elementos de la secuencia dada. Si n es mayor que el largo de la secuencia, ésta queda incambiada.
inicial :: Z* -> Z*
inicial (sec) = [] si resto(sec) == []
{ primero(sec) : inicial (resto(sec))
tomar :: N X Z* -> Z*
tomar (n, l) = [] si n == 0
o [] si l == []
o primero(l) : tomar (n-1, resto(l))