Ultima actualización: 14 de abril de 2011.
Paradigmas de Programación
Problemas Generales
Indice General
1.Lista de números suaves
1.1.Imperativa: Solución directa
1.2.Imperativa: Solución eficiente, TAD Lista Ordenada Limitada
1.3.Imperativa: Tratamiento de Excepciones
1.4.Orientación a Objeto: Delphi
1.5.Orientación a Objeto: Java + Herencia
1.6.Orientación a Objeto: Java + Iteradores
1.7.Funcional: Recursividad
1.8.Funcional: Map, Listas infinitas, Evaluación perezosa
2.Triángulo de Pascal
2.1.Imperativa: Análisis
2.2.Orientación a Eventos: callbacks
2.3.Orientación a Eventos: Objetos (Java)
2.4.Orientación a Eventos: Corutinas (Python)

Introducción

La siguiente lista de problemas se han elegido para poner de manifiesto las diferencias de enfoque y las distintas técnicas de programación de varios paradigmas. Las soluciones que se muestran no son en muchos casos las más adecuadas desde el punto de vista del diseño de aplicaciones, ya que se ha dado prioridad a la posibilidad de mostrar distintos aspectos de los paradigmas.

1. Problema de la lista de números suaves

Crear un programa que, dados los valores ini y n, escriba los n números suaves que siguen al ini-ésimo. Un número suave es todo entero positivo cuyos únicos factores primos son 2, 3 y 5, es decir se pueden escribir como 2a˙3b˙5c con a,b,c enteros positivos o nulos. Los primeros números suaves son:

Si se ejecuta el programa con ini = 8 y n = 4 la salida será: 9,10,12,15.

Eficiencia: Los números suaves se hacen cada vez más escasos a medida que aumenta su magnitud. En vez de comprobar para cada número si es o no suave, otro forma de calcularlo es generar directamente la lista de números suaves aplicando la propiedad de que cada número suave es igual al factor 2, 3 o 5 multiplicado por otro número suave que aparece antes en la lista.

1.1. Imperativa: Solución directa

Se recorren los números naturales (v) comprobando si son suaves. Por cada número encontrado incrementamos el índice i, si su valor es mayor o igual que ini se escribe, y el programa se detiene cuando i > fin, donde fin = ini+n-1 es el índice final.

program Suaves1;

  function Suave(x: integer) : boolean; // Comprueba si x es suave
  var y : integer;
  begin
    y := x; // Mientras sea múltiplo de 2,3,5 lo dividimos
    while y mod 2 = 0 do y := y div 2;
    while y mod 3 = 0 do y := y div 3;
    while y mod 5 = 0 do y := y div 5;
    Suave := (y = 1)  // Si es suave el resultado debe ser 1
  end;

var
  ini,fin,n,i,v : integer;
begin
  write('Inicio y longitud: '); readln(ini,n); fin := ini+n-1;
  // Se recorren los naturales con v. La variable i es el indice de suaves.
  v := 1; i := 1;
  repeat
    if Suave(v) then
    begin
      if i >= ini then write(v,' ');
      i := i+1
    end;
    v := v+1
  until i > fin
end.

1.2. Imperativa: Solución eficiente, TAD Lista Ordenada Limitada

La solución anterior es muy poco eficiente debido a que los números suaves aparecen con menor frecuencia a medida que i se va haciendo mayor (el 1693-ésimo número suave es mayor que MaxInt = 231-1 = 2,147,483,647), y cuando i es de ese orden el programa pierde mucho tiempo comprobando números que en su inmensa mayoría no son suaves.

La solución consiste en generar una lista de sólo números suaves aprovechando la propiedad de que si v es suave entonces 2v, 3v y 5v también lo son. Si inicializamos la lista con el valor 1 y la recorremos insertando en ella los valores doble, triple y quintuple del actuaal entonces tenemos garantizado el trabajar únicamente con números suaves y el generar todos (ya que siempre insertamos números mayores que el actual, por lo que no puede suceder que se haya omitido alguno menor que el actual).

El tipo de datos que necesitamos debe tener estas propiedades:

  • Almacena una lista ordenada de enteros. La inserción de valores debe respetar ese orden.
  • Los valores son únicos. Si se pide insertar un valor ya incluido, no se debe insertar.
  • La capacidad de la lista está limitada (para el problema sólo necesitamos almacenar los fin primeros números suaves). Si la lista ya esta llena, la inserción de un nuevo valor debe provocar que se elimine el valor máximo existente. (o que no se inserte el nuevo valor si es mayor que todos los de la lista).

Crearemos un tipo de datos, TLisOrdLim, y sus operaciones asociadas en una unidad, uLisOrdLim.pas, haciendo uso del paradigma modular. El programa principal sería:

program Suaves2;
// Se importa el módulo que define la lista ordenada limitada de enteros
uses uLisOrdLim;

var
  ini,fin,n,i,v : integer;
  // Se declara la variable que representa la lista
  lis : TLisOrdLim;
begin
  write('Inicio y longitud: '); readln(ini,n);
  fin := ini+n-1;
  // Se inicializa la lista: 0 elementos, capacidad para fin numeros suaves.
  uLisOrdLim.Inicializar(lis,fin);
  // Se inserta el 1
  uLisOrdLim.Insertar(lis,1);
  // Se recorren (y generan) los números suaves de índices 1..fin
  for i := 1 to fin do
  begin
    // Se obtiene el i-esimo numero suave
    v := uLisOrdLim.Elemento(lis,i);
    if i >= ini then write(v,' ');
    // Se insertan 2*v, 3*v y 5*v en la lista
    uLisOrdLim.Insertar(lis,2*v);
    uLisOrdLim.Insertar(lis,3*v);
    uLisOrdLim.Insertar(lis,5*v)
  end
end.

Se puede apreciar el uso de espacios de nombres para acceder a las operaciones del tipo de datos, el cuál se define en un módulo separado (de esa forma puede ser reutilizado en otros programas).

Para definir el tipo de datos se utiliza una composición de arrays y registros:

unit uLisOrdLim;

interface // Parte pública

  const
    MAX_DAT = 10000;
  
  type
    TLisOrdLim = record
      Lim : integer;                    // Capacidad de la lista
      N : integer;                      // Número de elementos almacenados
      V : array[1..MAX_DAT] of integer; // Array que almacena los datos
    end;

  procedure Inicializar(var Lista: TLisOrdLim; Limite: integer);
  procedure Insertar(var Lista: TLisOrdLim; Elem: integer);
  function Elemento(const Lista: TLisOrdLim; Pos: integer) : integer;

implementation // Parte privada

  procedure Inicializar(var Lista: TLisOrdLim; Limite: integer);
  begin
    Lista.Lim := Limite;
    Lista.N := 0
  end;

  function Elemento(const Lista: TLisOrdLim; Pos: integer) : integer;
  begin
    Elemento := Lista.V[Pos]
  end;

  // Procedimiento auxiliar: Devuelve en Pos el índice del primer elemento
  // en L.V[1..L.N] que es mayor o igual que X (o L.N+1 si todos son menores
  // que X. En Esta indica si X ya existe en la lista.
  procedure Busqueda(const L: TLisOrdLim; X: integer;
                            var Pos: integer; var Esta: boolean);
  var
    Izda,Dcha,Med : integer;
  begin
    // Algoritmo de búsqueda binaria
    Izda := 1; Dcha := L.N;
    while Izda <= Dcha do
    begin 
      Med := (Izda+Dcha) div 2;
      if L.V[Med] < X then Izda := Med+1 else Dcha := Med-1
    end;
    Pos := Izda;
    Esta := (Pos <= L.N) and (L.V[Pos] = X)
  end;

  procedure Insertar(var Lista: TLisOrdLim; Elem: integer);
  var
    Pos,I : integer;
    Existe : boolean;
  begin
    Busqueda(Lista,Elem,Pos,Existe);
    if (not Existe) and (Pos <= Lista.Lim) then
    begin
      // Desplazar elementos mayores a la derecha
      for I := Lista.N downto Pos do Lista.V[I+1] := Lista.V[I];
      // Insertar el elemento en la posición adecuada
      Lista.V[Pos] := Elem;
      if Lista.N < Lista.Lim then Lista.N := Lista.N+1
    end
  end;  

end.

1.3. Imperativa: Tratamiento de Excepciones

Si probamos el programa anterior con los valores ini = 1360, n = 14 obtenemos lo siguiente:

Inicio y longitud: 1360 14

419904000 421875000 424673280 425152800 429981696 429981696 430467210 430467210
432000000 432000000 437400000 437400000 439453125 439453125 442368000 442368000

Observamos que a partir del valor 429,981,696 aparecen duplicados. Si comprobamos el código observaremos que en realidad en ningún momento existen valores duplicados en la lista, por lo que el error es más sutil.

Si activamos la opción de detección de sobrepasamiento de enteros, veremos que se produce un error tras imprimir el valor 429,981,696, ello es debido a que al insertar 5*429,981,696 = 2,149,908,480, el resultado es mayor que MaxInt y el valor calculado que se inserta en la lista es en realidad -2,145,058,816. Al ser un número negativo, se inserta al principio de la lista y hace que todos los elementos se desplacen una posición a la derecha, por lo que en la siguiente iteración nos volvemos a encontrar el valor 429,981,696.

Para resolver el problema se debe evitar el insertar valores que al calcularles hayan producido un fallo de sobrepasamiento de enteros. Afortunadamente esto es lo que sucede cuando está activada la detección de sobrepasamiento, por lo que lo único que debemos modificar en el programa es añadir un bloque en que podamos recuperarnos de ese fallo:

{$OVERFLOWCHECKS ON}
program Suaves3;

// Se importa el módulo que define la lista ordenada limitada de enteros
uses uLisOrdLim;

var
  ini,fin,n,i,v : integer;
  // Se declara la variable que representa la lista
  lis : TLisOrdLim;
begin
  write('Inicio y longitud: '); readln(ini,n);
  fin := ini+n-1;
  // Se inicializa la lista: 0 elementos, capacidad para fin numeros suaves.
  uLisOrdLim.Inicializar(lis,fin);
  // Se inserta el 1
  uLisOrdLim.Insertar(lis,1);
  // Se recorren (y generan) los números suaves de índices 1..fin
  for i := 1 to fin do
  begin
    // Se obtiene el i-esimo numero suave
    v := uLisOrdLim.Elemento(lis,i);
    if i >= ini then write(v,' ');
    // Se insertan 2*v, 3*v y 5*v en la lista
    try
      uLisOrdLim.Insertar(lis,2*v);
      uLisOrdLim.Insertar(lis,3*v);
      uLisOrdLim.Insertar(lis,5*v)
    except
      on EIntOverflow do begin end // No hay que hacer nada
    end
  end
end.

1.4. Orientación a Objetos: Delphi

Se define una clase que representa la lista ordenada limitada. Nota:Se hace uso de la facilidad sintáctica que ofrece Delphi para definir el acceso a atributos (en este caso el elemento i-esimo de la lista) mediante una sintaxis similar a la del acceso a arrays (palabras reservadas property read. Además se marca como la propiedad por defecto (default), por lo que es posible omitir el nombre de la propiedad (Elem) al acceder al elemento. También se usan arrays dinámicos.

unit uLisOrdLim;

interface

  type
    TLisOrdLim = class
    private
      Lim,N : integer;
      V : array of integer; // Array dinámico
    protected
      procedure Busqueda(X: integer; var Pos: integer; var Esta: boolean);
      // Función que se llamará cuando se use la propiedad Elem
      function Elemento(Pos: integer) : integer;
    public
      constructor Create(Limite: integer);
      procedure Insertar(Elem: integer);
      // El acceso a elementos se define como una propiedad de tipo array
      // que se asocia a la función Elemento.
      property Elem[Pos: integer]: integer read Elemento; default;
    end;

implementation
  
  constructor TLisOrdLim.Create(Limite: integer);
  begin
    Lim := Limite; N := 0;
    // Tamaño dinámico del array (0-based)
    SetLength(V,Lim+1);    
  end;

  function TLisOrdLim.Elemento(Pos: integer) : integer;
  begin
    Elemento := V[Pos-1]
  end;

  procedure TLisOrdLim.Busqueda(X: integer; var Pos: integer; var Esta: boolean);
  var
    Izda,Dcha,Med : integer;
  begin
    Izda := 0; Dcha := N-1;
    while Izda <= Dcha do
    begin
      Med := (Izda+Dcha) div 2;
      if V[Med] < X then Izda := Med+1 else Dcha := Med-1
    end;
    Pos := Izda;
    Esta := (Pos < N) and (V[Pos] = X)
  end;

  procedure TLisOrdLim.Insertar(Elem: integer);
  var
    Pos,I : integer;
    Existe : boolean;
  begin
    Busqueda(Elem,Pos,Existe);
    if (not Existe) and (Pos < Lim) then
    begin
      for I := N-1 downto Pos do V[I+1] := V[I];
      V[Pos] := Elem;
      if N < Lim then N := N+1
    end
  end;

end.

El programa principal se adapta de la siguiente forma: (Nota: Cuando se escribe lis[i] esto se traduce por lis.Elem[i], al ser la propiedad por defecto, y a su vez se traduce por una llamada a la función Elemento: lis.Elemento(i))

{$OVERFLOWCHECKS ON}
program Suaves5;

uses uLisOrdLim;

var
  ini,fin,n,i,v : integer;
  lis : TLisOrdLim;
begin
  write('Inicio y longitud: '); readln(ini,n);
  fin := ini+n-1;
  // Se crea un objeto de la clase TLisOrdLim
  lis := TLisOrdLim.Create(fin);
  lis.Insertar(1);
  for i := 1 to fin do
  begin
    v := lis[i]; // Se hace uso de que elemento es la propiedad por defecto
    if i >= ini then write(v,' ');
    try
      lis.Insertar(2*v);
      lis.Insertar(3*v);
      lis.Insertar(5*v)
    except
      on EIntOverflow do begin end
    end
  end;
  // Se destruye el objeto que representa la lista
  lis.Free;
end.

Al tener Delphi (como C++) un modelo de gestión de memoria manual, es necesario destruir los objetos cuando se finaliza su uso (a diferencia de lo que pasa con Java, C# o Python).

1.5. Orientación a Objetos: Java + Herencia

En la versión de Java se defininen dos clases, LisOrd y LisOrdLim, para ilustrar el uso de la herencia. Nota: La palabra reservada super se usa en Java para acceder a los métodos y atributos de la clase base.

Fichero tads/LisOrd.java:

package tads;

/**
 *  La clase LisOrd representa una lista ordenada 
 *  de enteros distintos. Sólo se inserta un
 *  valor si no existe en la lista.
 */
public class LisOrd {

    int n;          // Número de elementos
    int[] v;        // Array que almacena los elementos

    // Construye una lista vacía capaz de contener
    // capacidad elementos antes de ser ampliada.
    public LisOrd(int capacidad) {
        n = 0;
        v = new int[capacidad];
    }

    // Devuelve el elemento en esa posición (1-based)
    public int elemento(int pos) {
        return(v[pos-1]);
    }

    // Elimina el último elemento (el máyor)
    public void quitaUltimo() {
        if(n > 0) { n--; }
    }

    // Devuelve la posición del primer elemento mayor o
    // igual a val en la lista
    protected int busqueda(int val) {
        int izda = 0;
        int dcha = n-1;
        while(izda <= dcha) {
            int med = (izda+dcha)/2;
            if(v[med] < val) { izda = med+1; } else { dcha = med-1; }
        }
        return(izda);
    }

    // Inserta el elemento si no existe en la lista
    public void insertar(int val) {
        int pos = busqueda(val);
        if(pos == n || v[pos] != val) {
            if(n >= v.length) { 
                // Ampliar array
                int[] w = new int[n+100];
                System.arraycopy(v,0,w,0,n);
                v = w;
            }
            // Desplazar elementos mayores a la derecha
            for(int i = n-1; i >= pos; i--) { v[i+1] = v[i]; }
            // Insertar nuevo
            v[pos] = val;
            // Actualizar número de elementos
            n++;
        }
    }
}

Fichero tads/LisOrdLim.java:

package tads;

/**
 *  La clase LisOrdLim representa una lista ordenada 
 *  con un número limitado de elementos. Si al
 *  insertar un elemento se supera el límite,
 *  se elimina el último (el mayor).
 */
public class LisOrdLim extends LisOrd {
    
    int lim; // Nuevo atributo

    public LisOrdLim(int limite) {
        super(limite+1);
        lim = limite;
    }

    @Override
    public void insertar(int val) {
        super.insertar(val);
        if(n > lim) { quitaUltimo(); }
    }
}

Fichero Programa.java:

import java.util.Scanner;
import tads.LisOrdLim;

/**
 * En Java no existen subrutinas aisladas, por lo que el punto de entrada
 * al programa debe definirse como un método estático dentro
 * de una clase
 */
public class Programa {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        System.out.print("Inicio, longitud = ");
        Scanner scn = new Scanner(System.in);
        int ini = scn.nextInt();
        int lon = scn.nextInt();
        int fin = ini+lon-1;
        // Creacion de la lista
        LisOrdLim lis = new LisOrdLim(fin);
        lis.insertar(1);
        for(int i = 1; i <= fin; i++) {
            int v = lis.elemento(i);
            if(i >= ini) { System.out.print(v+" "); }
            lis.insertar(2*v);
            lis.insertar(3*v);
            lis.insertar(5*v);
        }
    }
}

Java tiene recolección automática de memoria (garbage collector), por lo que no es necesario (ni posible) destruir la lista una vez usada.

1.6. Orientación a Objetos: Java + Iteradores

El programa anterior sufre del mismo problema indicado en el apartado 1.3, agravado por el hecho de que Java no genera excepciones en el sobrepasamiento de enteros. Para solucionarlo, vamos a incluir un método interno para recorrer los elementos de la lista que tenga en cuenta la situación en que, durante un recorrido, se inserten elementos antes del elemento actual.

Desde la versión 1.5, Java dispone de la construcción sintáctica bucles for-each, que permite recorrer los elementos de una estructura con un bucle del tipo for(elem: estructura). Para incorporarla a nuestra lista debemos implementar la interfaz Iterable, cuya definición es:

public interface Iterable<E> {
    public Iterator iterator();
}

Es decir, debemos incluir un método, iterador, que devuelva un objeto que implemente la interfaz Iterator y sea el encargado de recorrer los elementos de la lista. La notación Iterable<E> (genericidad) indica que los valores devueltos por el iterador deben pertenecer a la clase E (donde E se refiere a la clase usada en la definición).

La interfaz Iterador tiene la siguiente definición:

public interface Iterador {
    public boolean hasNext();
    public Object next();
    public void remove();
}

Para recorrer una estructura debemos definir un objeto que implemente los métodos hasNext (indica si existen más elementos por recorrer o se ha alcanzado el final) y next (devuelve el elemento actual y pasa al siguiente). El método remove (eliminar el elemento actual) es opcional y no lo implementaremos.

Para simplificar el problema, no crearemos una nueva clase para recorrer los elementos de la lista, sino que será la propia lista la que lo haga. Esto supone una limitación seria (no pueden realizarse más de un recorrido simultaneo sobre la lista) pero que no afecta a nuestro problema.

Sólo tenemos que modificar la clase LisOrd, la clase derivada LisOrdLim adquiere automaticamente la funcionalidad añadida.

package tads;

import java.util.Iterator;


/**
 *  Implementamos Iterable e Iterator
 */
public class LisOrd implements Iterable<Integer>, Iterator {

    int n;          // Número de elementos
    int[] v;        // Array que almacena los elementos

    // Variable que indica el elemento actual para el iterador
    int iter = 0;

    public LisOrd(int capacidad) {
        n = 0;
        v = new int[capacidad];
    }

    public int elemento(int pos) {
        return(v[pos-1]);
    }

    public void quitaUltimo() {
        if(n > 0) { n--; }
    }

    protected int busqueda(int val) {
        int izda = 0;
        int dcha = n-1;
        while(izda <= dcha) {
            int med = (izda+dcha)/2;
            if(v[med] < val) { izda = med+1; } else { dcha = med-1; }
        }
        return(izda);
    }

    public void insertar(int val) {
        int pos = busqueda(val);
        if(pos == n || v[pos] != val) {
            if(n >= v.length) { 
                int[] w = new int[n+100];
                System.arraycopy(v,0,w,0,n);
                v = w;
            }
            for(int i = n-1; i >= pos; i--) { v[i+1] = v[i]; }
            v[pos] = val;
            n++;
            // Si se ha insertado antes del elemento actual,
            // incrementar el iterador.
            if(pos < iter) { iter++; }
        }
    }

    // Método del interfaz Iterable
    public Iterator iterator() {
        // Devuelve un iterador (la propia lista)
        return this;
    }

    // Métodos del interfaz Iterator
    public boolean hasNext() {
        // Devuelve si quedan elementos por recorrer        
        return(iter < n);
    }

    public Object next() {
        // Devuelve elemento actual y pasa al siguiente
        iter++;
        // Nota: iter es 0-based y elemento es 1-based
        return(elemento(iter));
    }

    public void remove() {
        // No lo implementamos
        throw new UnsupportedOperationException("Not supported yet.");
    }
}

La adaptación del programa consiste en cambiar el bucle for por uno de tipo for-each:

import java.util.Scanner;
import tads.LisOrdLim;

public class Programa {

    public static void main(String[] args) {
        System.out.print("Inicio, longitud = ");
        Scanner scn = new Scanner(System.in);
        int ini = scn.nextInt();
        int lon = scn.nextInt();
        int fin = ini+lon-1;
        LisOrdLim lis = new LisOrdLim(fin);
        lis.insertar(1);
        int i = 1;
        for(int v : lis) {
            if(i >= ini) { System.out.print(v+" "); }
            lis.insertar(2*v);
            lis.insertar(3*v);
            lis.insertar(5*v);
            i++;
        }
    }
}

1.7. Funcional: Recursividad

Deseamos obtener una función que tome dos parámetros enteros, ini y lon, y nos devuelva la lista de números suaves correspondientes. El tipo de la función, y su uso en una sesión de Haskell sería:

prob1 :: Int -> Int -> [Int]
...
*Main> prob1 8 4
[9,10,12,15]
*Main>

Una traducción directa del algoritmo anterior a programación funcional consistiría en usar el tipo lista predefinido en Haskell para almacenar la lista ordenada de numeros suaves que se van generando. En vez de un bucle usaremos recursividad, y para ello necesitamos ampliar el número de parámetros para incluir el límite y la propia lista a la que se van incorporando los múltiplos (*2,*3,*5) de los valores que vamos recorriendo. Definimos para ello una función auxiliar:

prob1 :: Int -> Int -> [Int]
prob1 ini lon = prob1aux ini lon (ini+lon-1) [1]

prob1aux :: Int -> Int -> Int -> [Integer] -> [Integer]
prob1aux ini lon fin lista = ...

Debemos pensar en cómo definir prob1aux en función de llamadas a si misma con parámetros distintos, con valores más cercanos a los casos base. Tenemos dos casos ligeramente distintos:

  • Si todavía no hemos generado los ini primeros valores (que no se incorporan a la lista resultante), entonces el problema se puede establecer como quitar el primer elemento de la lista, incorporar sus múltiplos por 2,3,5 a la lista y resolver el mismo problema con ini-1: La llamada sería prob1aux (ini-1) lon lim lista' donde lista' hace referencia a la lista menos el primer elemento y mas los múltiplos de ese primer elemento.
  • Si ya hemos generado los ini primeros valores (en ese caso ini = 1), entonces el problema se puede establecer como incorporar el primer elemento a la lista resultante y añadir a esa lista el resultado de la llamada en que se quita el primer elemento de la lista, se incorporan los múltiplos de ese primer elemento y la longitud del resultado se decrementa en 1: La llamada sería prob1aux 1 (lon-1) lim lista' donde lista' hace referencia a la lista menos el primer elemento y mas los múltiplos de ese primer elemento.

El caso base se dará cuando el número de elementos que queden por generar sea cero. Escribimos la función con división en casos y, ya que la lista modificada en las llamadas recursivas es la misma, la especificamos una sola vez en una clásula where (se ha dividido en tres lineas, usando variables auxiliares, las inserciones de los múltiplos para que quede más claro el cálculo):

prob1aux :: Int -> Int -> Int -> [Integer] -> [Integer]
prob1aux ini lon lim (x:xs)
  | ini == 1 && lon <= 0  = []
  | ini == 1              = x : prob1aux 1 (lon-1) lim xs235
  | ini > 1               = prob1aux (ini-1) lon lim xs235
  where
     xs235 = insertar xs23 (5*x) lim
     xs23  = insertar xs2  (3*x) lim
     xs2   = insertar xs   (2*x) lim

Queda por definir la función insertar: Esta función recibe una lista ordenada, un valor a insertar y un límite, y devuelve la lista original donde se ha insertado el valor en la posición correcta si no existía en la lista. Si el número de elementos tras la inserción supera el límite, entonces elimina los últimos valores sobrantes. Definimos insertar en base a una función auxiliar, insaux:

insertar :: (Ord a) => [a] -> a -> Int -> [a]
insertar lis x lim = take lim (insaux lis x)

Se ha usado la función predefinida take, la cual devuelve los primeros n valores de una lista. Su definición es la siguiente:

take :: Int -> [a] -> [a]
take 0 lis    = []
take n (x:xs) = x : take (n-1) xs

La función insaux inserta un valor en una lista salvo que ya esté en ella:

insaux :: (Ord a) => [a] -> a -> [a]
insaux [] y = [y]
insaux (x:xs) y
  | x  < y = x : insaux xs y
  | x == y = x : xs
  | x  > y = y : x : xs

El programa completo consistiría en las siguientes definiciones:

insaux :: (Ord a) => [a] -> a -> [a]
insaux [] y = [y]
insaux (x:xs) y
  | x  < y = x : insaux xs y
  | x == y = x : xs
  | x  > y = y : x : xs

insertar :: (Ord a) => [a] -> a -> Int -> [a]
insertar lis x lim = take lim (insaux lis x)

prob1aux :: Int -> Int -> Int -> [Integer] -> [Integer]
prob1aux ini lon lim (x:xs)
  | ini == 1 && lon <= 0  = []
  | ini == 1              = x : prob1aux 1 (lon-1) lim xs235
  | ini > 1               = prob1aux (ini-1) lon lim xs235
  where
     xs235 = insertar xs23 (5*x) lim
     xs23  = insertar xs2  (3*x) lim
     xs2   = insertar xs   (2*x) lim

prob1 :: Int -> Int -> [Int]
prob1 ini lon = prob1aux ini lon (ini+lon-1) [1]

1.8. Funcional: Map, Listas infinitas, Evaluación perezosa

La solución anterior, aunque correcta, no explota todas las posibilidades que ofrece el paradigma funcional respecto a la concisión, eficiencia y elegancia que se pueden obtener.

Si tuviesemos una lista (infinita) que contuviese todos los números suaves, suaves, entonces la función que resuelve el problema consitiría únicamente en descartar los ini-1 primeros valores y quedarse con los lon siguientes:

suaves :: [Int]
suaves = ...

prob1 :: Int -> Int -> [Int]
prob1 ini lon = take lon (drop (ini-1) suaves)

La función predefinida take ya se ha explicado anteriormente. La función predefinida drop recibe un entero, n, y una lista y devuelve la lista resultante de eliminar los n primeros elementos. Una posible definición sería:

drop :: Int -> [a] -> [a]
drop 0 lis = lis
drop n (x:xs) = drop (n-1) xs

La lista de números suaves se puede definir de la siguiente forma: Si tenemos una lista parcial, con los primeros valores, y a partir de ella formamos las listas con los sus duplicados (map (2*) suaves), sus triplicados (map (3*) suaves) y sus quíntuplos (map (5*) suaves), y fusionamos estas tres listas añadiendo el 1 al principio, obtenemos una lista de números suaves ampliada:

La fusión de dos listas ordenadas consiste en obtener otra lista ordenada con los elementos de las listas originales. Nos interesa una versión de la fusión en la que los elementos repetidos sólo aparezcan una vez:

fusion :: (Ord a) => [a] -> [a] -> [a]
fusion [] ys = ys
fusion xs [] = xs
fusion (x:xs) (y:ys)
  | x <  y  = x : fusion xs (y:ys)
  | x == y  = x : fusion xs ys
  | x >  y  = y : fusion (x:xs) ys

El algoritmo es sencillo: Para formar la lista resultante se escoge el menor de los dos primeros elementos de las listas (al estar ordenadas, el primer elemento es el menor de cada lista), y el resto surge de la fusión de los elementos restantes.

Como se deben fusionar tres listas, definimos una función que fusione la primera lista con el resultado de fusionar la segunda con la tercera:

fusion3 :: (Ord a) => [a] -> [a] -> [a] -> [a]
fusion3 xs ys zs = fusion xs (fusion ys zs)

Con esta función ya podemos definir la lista infinita de números suaves:

suaves :: [Int]
suaves = 1 : fusion3 (map (*2) suaves) (map (*3) suaves) (map (*5) suaves)

El hecho de que la lista esté definida en función de si misma no supone un problema en Haskell, ya que las expresiones en Haskell se almacenan sin evaluar, y sólo se evaluan (mediante sustitución de definiciones) en la extensión en que se obtienen los valores necesarios. En &eeacute;ste caso, la evaluación se produce al actuar las funciones take y drop de la definición de prob1, expandiendose el contenido de la lista suaves sólo hasta que se obtienen los valores necesarios de la lista.

El programa completo es el siguiente:

fusion :: (Ord a) => [a] -> [a] -> [a]
fusion (x:xs) (y:ys)
  | x <  y  = x : fusion xs (y:ys)
  | x == y  = x : fusion xs ys
  | x >  y  = y : fusion (x:xs) ys

fusion3 :: (Ord a) => [a] -> [a] -> [a] -> [a]
fusion3 xs ys zs = fusion xs (fusion ys zs)

suaves :: [Int]
suaves = 1 : fusion3 (map (*2) suaves) (map (*3) suaves) (map (*5) suaves)

prob1 :: Int -> Int -> [Int]
prob1 ini lon = take lon (drop (ini-1) suaves)

Nota: Se han omitido los casos base de fusion ya que al trabajar con listas infinitas nunca se van a dar.


2. Problema del Triángulo de Pascal

Un triángulo de Pascal es un conjunto infinito de números enteros dispuestos en forma triangular donde el primer y último valor de cada fila son unos y el resto se calcula como la suma de los dos valores adyacentes de la fila superior. En la imagen izquierda (tomada de Wikipedia) se muestra la forma de construir el triángulo. Como los valores del triángulo crecen muy rápidamente, se establecerá un parámetro, lim, de manera que cada valor se calcula como la suma modulo lim de los dos anteriores (módulo significa que calculamos es resto de la división por lim). De esa forma se garantiza que los valores del triángulo se encuentren siempre entre 0 y lim-1. En la imagen derecha se muestra el triángulo de Pascal módulo 2 (lim = 2)

    

Se desea representar el triángulo de distintas formas, y para ello se exige un diseño de aplicación que cumpla los siguientes criterios:

  • Exista un módulo que defina una representación de una fila del triángulo y una subrutina, GeneraTriangulo, que reciba como parámetros el número de filas a generar y el límite y genere el triángulo fila a fila.
  • El programa principal usará ese módulo y definirá un procedimiento, ProcesaFila, que se encargará de procesar cada linea generada por GeneraTriangulo. Este procedimiento (que reside en el programa principal) recibe como parámetros la fila, su número de fila y el número total de filas a representar.

2.1. Imperativa: Análisis

La definición más sencilla de una fila es un array parcialmente ocupado:

const
  MAX_LIN = 10000;

type
  TFila = record
            N : integer;
            V : array[1..MAX_LIN] of integer;
          end;
    

Para hacer que una linea pase a ser la siguiente añadimos a cada celda el valor de la celda anterior, e incluimos un valor 1 al final:

procedure SigFila(var Fil: TFila; Lim: integer);
var I : integer;
begin
  for I := 2 to Fil.N do
    Fil.V[I] := (Fil.V[I-1]+Fil.V[I]) mod Lim; <-- Erroneo
  Fil.N := Fil.N+1;
  Fil.V[Fil.N] := 1
end;

El código anterior es erroneo debido a que al modificar cada celda estamos perdiendo un valor que se necesita para la siguiente iteración. Este tipo de error es muy común en el paradigma imperativo. El código corregido sería:

procedure SigFila(var Fil: TFila; Lim: integer);
var I,Vant,Vact : integer;
begin
  Vant := Fil.V[1];
  for I := 2 to Fil.N do
  begin
    Vact := Fil.V[I];
    Fil.V[I] := (Vant+Fil.V[I]) mod Lim;
    Vant := Vact
  end;
  Fil.N := Fil.N+1;
  Fil.V[Fil.N] := 1
end;

Añadiendo la subrutina para generar el triángulo de Pascal sería, el módulo para generar triángulos sería:

unit Modulo;

interface

  const
    MAX_LIN = 10000;

  type
    TFila = record
              N : integer;
              V : array[1..MAX_LIN] of integer;
            end;

  procedure GeneraTriangulo(NumFil,Lim: integer);

implementation

  procedure SigFila(var Fil: TFila; Lim: integer);
  var I,Vant,Vact : integer;
  begin
    Vant := Fil.V[1];
    for I := 2 to Fil.N do
    begin
      Vact := Fil.V[I];
      Fil.V[I] := (Vant+Fil.V[I]) mod Lim;
      Vant := Vact
    end;
    Fil.N := Fil.N+1;
    Fil.V[Fil.N] := 1
  end

  procedure GeneraTriangulo(NumFil,Lim: integer);
  var
    I : integer;
    Fil : TFila;
  begin
    // Inicializar primera fila
    Fil.N := 1;
    Fil.V[1] := 1;
    // Procesar primera fila
    ProcesaFila(Fil,1,NumFil);
    // Generar filas restantes
    for I := 2 to NumFil do
    begin
      SigFila(Fil,Lim);
      ProcesaFila(Fil,I,NumFil);
    end
  end;

end.

Y el programa que utiliza al módulo:

program Programa;

uses Modulo;

  procedure ProcesaFila(const fil: TFila; I,N: integer);
  var J : integer;
  begin
    // Espacios iniciales de fila 
    write('':(N-I));
    for J := 1 to Fil.N do write(Fil.V[J]:2);
    writeln;
  end;

var
  N,Lim : integer;
begin
  Write('Lineas, Limite = ');
  ReadLn(N,Lim);
  Modulo.GeneraTriangulo(N,Lim);
end.

Si se intenta compilar éste código, se producirá un error, ya que la subrutina GeneraTriangulo del módulo necesita llamar a la subrutina ProcesaFila, que no está definida en él, sino en el programa principal. Ya que un módulo debe ser independiente de aquellos que lo utilicen, no es posible hacer que conozca datos o procedimientos de los programas que vayan a usarlos, salvo aquellos que se pasen como parámetros.

2.2. Orientación a Eventos: callbacks

Una solución al problema es precisamente permitir pasar por parámetro referencias a subrutinas, de tal forma que puedan ser llamadas desde otro ámbito distinto a aquel en que están definidas. C tiene la posibilidad de definir punteros a funciones, y Pascal la posibilidad de definir lo que se denomina tipos procedurales.

Un tipo procedural en Pascal indica la cabecera de una función o procedimiento (sin indicar su nombre), permitiendo que las variables de ese tipo almacenen referencias a funciones o procedimientos cuya cabecera tenga una definición compatible.

Modificaremos el módulo y el programa anterior para que GeneraTriangulo tenga un parámetro extra que sea el procedimiento que debe invocar cada vez que genere una fila del triángulo:

unit Modulo;

interface

  const
    MAX_LIN = 10000;

  type
    TFila = record
              N : integer;
              V : array[1..MAX_LIN] of integer;
            end;

    // Tipo procedural
    TProcFila = procedure(const Fil: TFila; I,N: integer);

  procedure GeneraTriangulo(NumFil,Lim: integer; Proc: TProcFila);

implementation

  procedure SigFila(var Fil: TFila; Lim: integer);
  var I,Vant,Vact : integer;
  begin
    Vant := Fil.V[1];
    for I := 2 to Fil.N do
    begin
      Vact := Fil.V[I];
      Fil.V[I] := (Vant+Fil.V[I]) mod Lim;
      Vant := Vact
    end;
    Fil.N := Fil.N+1;
    Fil.V[Fil.N] := 1
  end

  procedure GeneraTriangulo(NumFil,Lim: integer; Proc: TProcFila);
  var
    I : integer;
    Fil : TFila;
  begin
    // Inicializar primera fila
    Fil.N := 1;
    Fil.V[1] := 1;
    // Procesar primera fila
    Proc(Fil,1,NumFil);
    // Generar filas restantes
    for I := 2 to NumFil do
    begin
      SigFila(Fil,Lim);
      Proc(Fil,I,NumFil);
    end
  end;

end.

Definimos dos procedimientos de proceso de filas, para clarificar su funcionamiento:

program Programa;

uses Modulo;

  procedure ProcesaFila1(const fil: TFila; I,N: integer);
  var J : integer;
  begin
    // Espacios iniciales de fila 
    write('':(N-I));
    for J := 1 to Fil.N do write(Fil.V[J]:2);
    writeln;
  end;

  procedure ProcesaFila2(const fil: TFila; I,N: integer);
  // Escribe asteriscos en valores impares
  var J : integer;
  begin
    write('':(N-I));
    for J := 1 to Fil.N do
      if Fil.V[J] mod 2 = 0 then write('  ') else write(' *');
    writeln;
  end;

var
  N,Lim : integer;
  P : TProcFila;
begin
  Write('Lineas, Limite = ');
  ReadLn(N,Lim);
  Modulo.GeneraTriangulo(N,Lim,ProcesaFila1);
  // Las referencias a subrutinas se pueden almacenar en variables.
  P := ProcesaFila2; 
  Modulo.GeneraTriangulo(N,Lim,P);
end.

2.3. Orientación a Eventos: Objetos

Otra solución proviene de la Orientación a Objetos: Ya que un objeto tiene código asociado, es posible pasar como parámetro un objeto que contenga la subrutina que se desea invocar en el programa.

Las interfaces de Java permiten organizar el flujo de información de la forma adecuada:

  • El objeto que representa el Programa sabe como mostrar filas, pero no como generar el triángulo.
  • El objeto que representa el Módulo sabe como generar filas, pero no lo que se debe hacer con cada una de ellas.
  • La solución pasa por que el Programa invoque al Módulo pasandose a si mismo como parámetro, para que el módulo pueda llamar al método adecuado del Programa cada vez que genere una fila.
  • No parece razonable, sin embargo, que el Módulo deba conocer los detalles de definición o implementación del Programa, más allá del hecho de que tiene definido el método que debe invocar.
  • Aquí es donde entra en juego el polimorfismo: Si se define una interfaz indicando el nombre y parámetros del método que se debe invocar, y el Programa la implementa, entonces puede enviarse como parámetro al Módulo indicando unicamente que implementa la interfaz, sin indicar que es un objeto de tipo Programa.

Fichero modulo/ProcLin.java:

package modulo;

public interface ProcLin {
    public void procesaLinea(int[] fil, int i, int n);
}

Fichero modulo/GeneradorTriangulos.java:

package modulo;

public class GeneradorTriangulos {

    // Declaramos los métodos como estáticos
    // porque no necesitan acceder a estado interno
    public static void sigFila(int[] fil, int n, int lim) {
        int vant = fil[0];
        for(int i = 1; i < n; i++) {
            int vact = fil[i];
            fil[i] = (vant+fil[i]) % lim;
            vant = vact;
        }
        fil[n] = 1;
    }

    // Se pasa como parámetro un objeto que implemente la
    // interfaz ProcLin
    public static void generar(int numfil, int lim, ProcLin proc) {
        // inicializar primera fila
        int[] fil = new int[numfil];
        fil[0] = 1;
        proc.procesaLinea(fil,1,numfil);
        // Generar resto de filas
        for(int i = 2; i <= numfil; i++) {
            sigFila(fil,i-1,lim);
            proc.procesaLinea(fil,i,numfil);
        }
    }
}

Fichero Programa.java:

import java.util.Scanner;
import modulo.GeneradorTriangulos;
import modulo.ProcLin;

public class Programa implements ProcLin {

    // Método definido en la interfaz
    public void procesaLinea(int[] fil, int i, int n) {
        for(int j = i; j < n; j++ ) { System.out.print(" "); }
        for(int j = 0; j < i; j++) { 
            if(fil[j] % 2 == 0) {
                System.out.print("  ");
            } else {
                System.out.print(" *");
            }
        }
        System.out.println();
    }

    // Constructor de la clase y programa principal
    public Main() {
        System.out.print("Lineas, limite = ");
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int lim = scn.nextInt();
        // Enviamos este objeto (como ProcLin) al generador
        // generar es un método estático
        GeneradorTriangulos.generar(n, lim, this);
    }

    public static void main(String[] args) {
        // Necesitamos instanciar esta clase para
        // tener un objeto que pasar al generador
        new Main();
    }
}

2.4. Orientación a Eventos: Corutinas (Python)

Otra posible solución es el uso de corutinas: Subrutinas que permiten retornar valores de forma que la siguiente llamada a la corutina continue a partir del momento en que se retorno el valor.

Definiendo el generador de filas como una corutina que devuelva cada fila, podemos conseguir el efecto de obtener multiples valores en una sola invocación, si unimos la corutina al concepto de generador/iterador.

Parte del módulo:

def sigfil(fil,lim):
  vant = fil[0]
  for i in range(1,len(fil)):
    vact = fil[i]
    fil[i] += vant
    vant = vact
  fil.append(1)

def generador(numfil,lim):
  fil = [1]
  yield (fil,1,numfil)
  for i in range(2,numfil+1):
    sigfil(fil,lim)
    yield (fil,i,numfil)

Parte del programa:

import modulo

def proclin(fil,i,n):
  print " "*(n-1),
  for v in fil:
    print " *"[v % 2],
  print

def principal(numfil,lim):
  for v in modulo.generador(numfil,lim):
    proclin(*v)

César Vaca Rodríguez

2010 Departamento de Informática, Universidad de Valladolid.