Cesar Systems

Es natural expresar muchas operaciones con listas por medio de métodos recursivos. El siguiente ejemplo es un algoritmo recursivo para imprimir una lista hacia atrás:

1. Separar la lista en dos partes: el primer nodo (llamado cabeza) y el resto (llamado cola).
2. Imprimir la cola hacia atrás.
3. Imprimir la cabeza.

Por supuesto, el paso 2, la llamada recursiva, supone que tenemos una manera de imprimir una lista del revés. Pero si suponemos que la llamada recursiva funciona |el acto de fe| entonces podemos estar convencidos de que este
algoritmo funciona.

Todo lo que necesitamos es un caso básico y una forma de demostrar que para cualquier lista podemos obtener el caso básico. Dada la definición recursiva de una lista, un caso básico natural es la lista vacía, representada por None:

   1: def imprimeAlReves(lista):

   2:     if lista == None: return

   3:     cabeza = lista

   4:     cola = lista.siguiente

   5:     imprimeAlReves(cola)

   6:     print cabeza,

La primera línea maneja el caso inicial no haciendo nada. Las dos siguientes líneas dividen la lista en cabeza y cola. Las dos ultimas líneas imprimen la lista. La coma que hay al final de la ultima l³nea evita que Python salte de línea después de imprimir un nodo.

Llamamos este metodo tal como antes invocamos a imprimeLista:

   1: >>> imprimeAlReves(nodo1)

   2: 3 2 1

El resultado es una lista invertida.
Es posible que se pregunte por que imprimeLista e imprimeAlReves son funciones y no métodos de la clase Nodo. La razón es que queremos usar None para representar la lista vacía y no es legal llamar un metodo sobre None. Esta limitación resulta algo incomoda a la hora de escribir código para manipular listas con un estilo orientado a objetos puro.

¿Podemos demostrar que imprimeAlReves siempre acabara? En otras palabras,
¿siempre alcanzaremos el caso básico? De hecho, la respuesta es no. Algunas listas harán que el metodo no funcione.

No hay nada que impida a un nodo hacer referencia a un nodo anterior de la lista, incluido el mismo. Por ejemplo, esta figura muestra una lista con dos nodos, uno de los cuales apunta a si mismo:

Si llamamos a imprimeLista sobre esta lista, entrara en un bucle infinito. Si llamamos a imprimeAlReves, lo hará de forma infinitamente recursiva. Este tipo de comportamiento da lugar a que sea muy difícil trabajar con listas infinitas.

Sin embargo, en ocasiones resultan útiles. Por ejemplo, podríamos representar un numero como una lista de dígitos y usar una lista infinita para representar una fracción repetida.

A pesar de todo, es un problema que no podamos probar que imprimeLista e imprimeAlReves puedan terminar correctamente. Lo mejor que podemos hacer es armar que si la lista no contiene bucles, estos métodos podrán terminar”.

Este tipo de afirmaciones se conocen como condiciones previas. Imponen una restricción sobre uno de los parámetros y describen el comportamiento del metodo si la restricción se satisface. Veremos mas ejemplos mas adelante.

Una parte de imprimeAlReves podría habernos sorprendido:

   1: cabeza = lista

   2: cola = lista.siguiente

Después de la primera asignación, la cabeza y la cola tienen el mismo tipo y el mismo valor. Así que, ¿para que hemos creado un nueva variable?

La razón es que las dos variables desempeñan papeles diferentes. Pensamos en la cabeza como una referencia al primer nodo de la lista. Estos “papeles” no forman parte del programa, sino que están en la mente del programador.

En general no podemos decir con solo mirar un programa que papel desempeñara un variable. Esta ambigÄuedad puede ser útil, pero también puede dificultar la lectura del programa. A menudo usaremos nombres para las variables como nodo y lista para explicar como queremos usar una variable y a veces creamos variables adicionales para eliminar ambigüedades.

Podríamos haber escrito imprimeAlReves sin cabeza ni cola, que lo haría mas conciso, pero posiblemente menos claro:

   1: def imprimeAlReves(lista) :

   2:     if lista == None : return

   3:     imprimeAlReves(lista.siguiente)

   4:     print lista,

Mirando esas dos llamadas, hemos de recordar que imprimeAlReves trata sus argumentos como una colección y print los trata como a un solo objeto.

El teorema fundamental de la ambigüedad indica que la ambigüedad que es inherente a una referencia a un nodo:

Una variable que hace apunta a nodo puede tratar a este nodo como un objeto o como el primero de una lista de nodos.

Hay dos formas de modificar una lista enlazada. Obviamente, podemos cambiar la carga de uno de los nodos, pero las operaciones mas interesantes son las que añaden, quitan o reordenan los nodos.

Como ejemplo, escribamos un metodo que quite el segundo nodo de la lista y devuelva una referencia al nodo quitado:

   1: def eliminaSegundo(lista):

   2:     if lista == None: return

   3:     primero = lista

   4:     segundo = lista.siguiente

   5:     # hacer que el primer noda apunte al tercero

   6:     primero.siguiente = segundo.siguiente

   7:     # separar el segundo nodo del resto de la lista

   8:     segundo.siguiente = None

   9:     return segundo

De nuevo, estamos usando variables temporales para hacer mas legible el código.

Así es como usamos este método:

   1: >>> imprimeLista(nodo1)

   2: 1 2 3

   3: >>> eliminado = elimnaSegundo(nodo1)

   4: >>> imprimeLista(eliminado)

   5: 2

   6: >>> imprimeLista(nodo1)

   7: 1 3

¿Que ocurriría si llamáramos a este metodo y pasáramos una lista de un único elemento (un singleton)?

¿Que sucederá si pasáramos una lista vacía como argumento?

¿Hay una condición previa para este metodo? Si es así, será algo razonable establecer un metodo para manejar una violación de la condición previa.

A menudo es útil dividir una operación de listas en dos métodos.

Por ejemplo, para imprimir una lista invertida en el formato convencional [3, 2, 1] podemos usar el metodo imprimeAlReves para imprimir 3, 2, pero necesitaremos un metodo aparte para imprimir los corchetes y el primer nodo. Llamémoslo imprimeAlRevesBonito:

   1: def imprimeAlRevesBonito(lista) :

   2:         print "[",

   3:             if lista != None :

   4:             cabeza = lista

   5:             cola = lista.siguiente

   6:             imprimeAlReves(cola)

   7:         print cabeza,

   8:     print "]",

De nuevo, vemos que es buena idea comprobar métodos como este para ver si funcionan con casos especiales como una lista vacía o un singleton.

Cuando usamos este metodo en algún otro lugar del programa, llamamos directamente a imprimeAlRevesBonito, y este llama a imprimeAlReves en nuestro lugar. En cierto modo, imprimeAlRevesBonito actúa como un envoltorio, y utiliza a imprimeAlReves como su ayudante.

Existen ciertos problemas delicados con la forma en que se implementaron las listas. Invirtiendo el orden de causa y efecto, propondremos primero una implementación alternativa y explicaremos luego los problemas que esta resuelve.

En primer lugar crearemos un nueva clase llamada ListaEnlazada. Sus atributos son un entero que contiene la longitud de la lista y una referencia al primer nodo. Los objetos ListaEnlazada sirven de asas para la manipulación de las
listas de los objetos de tipo Nodo:

   1: class ListaEnlazada :

   2: def __init__(self) :

   3: self.longitud = 0

   4: self.cabeza = None

Una ventaja de la clase ListaEnlazada es que suministra un marco natural para poner funciones-envoltorio como imprimeAlRevesBonito, que podemos convertir en un metodo de la clase ListaEnlazada:

   1: class ListaEnlazada:

   2: ...

   3:     def imprimeAlReves(self):

   4:         print "[",

   5:             if self.cabeza != None:

   6:                 self.cabeza.imprimeAlReves()

   7:             print "]",

   8: class Nodo:

   9: ...

  10:     def imprimeAlReves(self):

  11:         if self.siguiente != None:

  12:             cola = self.siguiente

  13:             cola.imprimeAlReves()

  14:         print self.carga,

Para complicar un poco mas las cosas, renombramos imprimeAlRevesBonito.

Ahora hay dos métodos llamados imprimeAlReves: uno en la clase Nodo (el ayudante), y otro en la clase ListaEnlazada (el envoltorio). Cuando el envoltorio llama a self.cabeza.imprimeAlReves, esta llamando al ayudante, ya que
self.cabeza es un objeto de tipo Nodo.

Otra ventaja de la clase ListaEnlazada es que facilita la forma de añadir o quitar el primer elemento de una lista. Por ejemplo, agregaPrimero es un metodo para ListaEnlazada; toma un elemento de la carga como argumento y lo coloca en el principio de la lista:

   1: class ListaEnlazada:

   2: ...

   3:     def agregaPrimero(self, carga):

   4:         nodo = Nodo(carga)

   5:         nodo.siguiente = self.cabeza

   6:         self.cabeza = nodo

   7:         self.longitud = self.longitud + 1

Como suele ser usual, deberíamos comprobar este código para ver si maneja casos especiales.

Por ejemplo, que ocurriría si la lista esta inicialmente vacía?

Algunas listas están “bien construidas”; otras no. Por ejemplo, si una lista contiene un bucle, provocara que nuestros métodos se cuelguen, así que podríamos exigir que las listas no contengan bucles. Otro requisito es que el valor de el valor de longitud en el objeto de tipo Lista Enlazada deber³a ser igual al numero verdadero de nodos de la lista.

A este tipo de requisitos los llamaremos invariantes porque, idealmente deberían cumplirse en todos los objetos en todo momento. Especificar invariantes para objetos es una practica útil de la programación porque hace mas fácil demostrar la idoneidad del código, comprobar la integridad de las estructuras de datos y la detección de errores.

Una cosa que a veces confunde respecto a los invariantes es que en ocasiones son violados. Por ejemplo, en medio de agregaPrimero, después de añadir el nodo paro antes de incrementar la longitud, se viola el invariante. Se acepta este tipo de violación; de hecho, a menudo es imposible modificar un objeto sin violar un invariante durante al menos un corto espacio de tiempo. Normalmente, se exige que todo metodo que viole un invariante debe restablecerlo.

Si hay algún tramo significativo de código en el que el invariante se ve violado, es importante que los comentarios lo dejen

referencia incrustada: Es una referencia almacenada en un atributo de un objeto.

lista enlazada: Estructura de datos que implementa una colección por medio de una secuencia de nodos enlazados.

nodo: Elemento de una lista, normalmente implementado como un objeto que contiene una referencia a otro objeto del mismo tipo.

carga: Datos contenidos en un nodo. enlace: Referencia incrustada usada para enlazar un objeto con otro.

condición previa: Afirmación que debe ser cierta para que un metodo funcione correctamente.

teorema fundamental de la ambiguedad: Una referencia a un nodo de una lista puede tratarse como un objeto individual o como el primero de una lista de nodos.
singleton: Lista enlazada con un solo nodo.

envoltorio: Metodo que actúa como mediador entre un metodo invocador y metodo ayudante, haciendo a menudo su invocación mas fácil o menos proclive a errores.

ayudante: Metodo al que no se invoca directamente por un metodo llamante sino por otro metodo para formar parte de una operación.

invariante: Afirmación que debería ser cierta para un objeto en todo momento (excepto tal vez cuando se esta modificando el objeto).