SGCG

…esto no es un subtítulo…

Ir a: contenido categorías calendario archivo suscripción

Volver arriba

Jugando con autómatas celulares (5)

2013-08-22

Hace varios artículos, planteamos un interesante proyecto: una pequeña biblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.

Hace unos días creamos un sencillo autómata de ejemplo. El código era específico de este autómata, pero podemos ir creando funciones más generales con las que trabajar. Hoy hacemos un pequeño desvío para construir unas pocas funciones auxiliares que serán muy útiles más adelante. Casi todas estas funciones son para Scheme R5RS, cuya biblioteca estándar es deliberadamente pequeña y minimalista. Algunas de estas funciones aparecen en los «casi estándares» SRFI.

Función para agrupar listas de elementos correspondientes

A menudo, tenemos varias listas y queremos construir una que agrupa los elementos de forma que tenemos el grupo de los primeros elementos de las listas de entrada, el grupo de los segundos elementos de las listas de entrada, el grupo de los terceros elementos de las listas de entrada… Esta operación suele llamarse zip. Existe en Python 2 y en Scheme R5RS es así de sencilla:
(define (zip . lists) (apply map (cons list lists)))
Usamos map para recorrer las listas de entrada. El número de listas de entrada es variable y lo indicamos así con el puntito delante del argumento lists. Esto de poner un puntito es azúcar sintáctico en Scheme para indicar que lo que sigue es una lista de argumentos de tamaño variable, lo que se conoce muchas veces como varargs: aunque nosotros ponemos escribimos los argumentos uno tras otro al llamar a nuestra función, los argumentos llegan empaquetados en una lista. Luego usamos esta lista de argumentos con apply para llamar a map, pero empaquetamos algún argumento adicional con cons. ¡No es tan difícil! Esta llamada
(zip a b c)
hace esto por debajo
(apply map (cons list (list a b c)))
que a su vez es equivalente a
(map list a b c)

Función de reducción o acumulación

Esto es lo que suele llamarse fold, reduce, accumulate… Es un consumidor de listas. En Python2 hay un equivalente llamado reduce que es algo incómodo porque trabaja con solamente una lista; nosotros queremos usar varias. ¿Qué hace fold? Lo que hace es ir aplicando un operador (una función) a los elementos de una lista (o un conjunto de listas) y un acumulador que va actualizando con el resultado de la última aplicación de la función. Esta operación tan abstracta es tan rematadamente útil que ni siquiera Guido van Rossum, dictador benévolo de Python, pudo librarse de ella por completo en Python 3.

Hay varias maneras de hacer fold. Nosotros vamos a usar una variante que recorre la lista linealmente de izquierda a derecha (de elemento en elemento desde el primero hasta el último) y aplica el operador con el siguiente valor de la lista (o el siguiente elemento de cada lista si pasamos varias) en primer lugar y el resultado de la anterior aplicación del operador en último lugar.

Nuestra fold acepta un número arbitrario de listas para trabajar. Para hacer esto, tenemos que hacer de nuevo una función variádica, es decir, que acepta varargs. Nuestra función acepta como primer argumento el operador operator que vamos a aplicar, como segundo argumento el valor inicial initial-value del acumulador, como tercer argumento la primera lista list1 sobre la que trabajar y (si hay más argumentos) las demás listas en listn. El código de Scheme es así:
(define (fold operator initial-value list1 . listn) (if (null? listn) (if (null? list1) initial-value (fold operator (operator (car list1) initial-value) (cdr list1))) (fold (lambda (lists accumulator) (apply operator (append lists (list accumulator)))) initial-value (apply zip (cons list1 listn)))))
No es muy complicado. Empezamos con una comprobación: si no hemos pasado más que una lista (en cuyo caso listn tiene valor nulo), hacemos nuestro trabajo directamente; si no, volvemos a llamar a fold, pero esta vez con los argumentos modificados para trabajar con los elementos del conjunto de listas de entrada apareados con zip. El trabajo principal se hace de forma recursiva. También podemos hacer lo mismo con iteración:
(define (fold operator initial-value list1 . listn) (if (null? listn) (do ((accumulator initial-value (operator (car lis) accumulator)) (lis list1 (cdr lis))) ((null? lis) accumulator)) (fold (lambda (lists accumulator) (apply operator (append lists (list accumulator)))) initial-value (apply zip (cons list1 listn)))))
Es un poco más compacto, pero más críptico.

Python tiene algo que es casi equivalente a fold: la función reduce. El problema de reduce es que solamente admite una lista. Queremos trabajar con varias, así que nos inventamos una función fold que hace lo mismo que la de Scheme, pero sin necesidad de reescribir la función reduce. A cambio, la función reduce de Python usa operadores cuyo primer argumento es el acumulador y cuyo segundo argumento es el siguiente valor de la lista; esto es el orden inverso al que se usa en el fold de Scheme, así que vamos a darle la vuelta. La función es así:
def fold(operator, initial_value, list1, *listn): if len(listn) == 0: def operator_for_reduce(accumulator, new_value): return operator(new_value, accumulator) return reduce(operator_for_reduce, list1, initial_value) else: def apply_operator(lists, accumulator): arguments = list(lists) + [accumulator] return operator(*arguments) return fold(apply_operator, initial_value, zip(*([list1] + list(listn))))
En Python 2 hay un equivalente a apply que, de hecho, se llama igual, pero cuyo uso está desaconsejado a favor de la llamada con un asterisco que hemos hecho. A veces, parece que Python trata de recordar a Perl.

Función de generación de listas

Esto es más o menos lo opuesto a fold: unfold. A partir de unas funciones que indican cómo operar y un valor semilla, esta función crea una lista. La función unfold acepta como argumentos un predicado stop? que indica si hay que parar, una función generate que genera el siguiente elemento de la lista a partir de la semilla, una función update que actualiza el valor de la semilla para la siguiente operación, un valor semilla seed que sirve para dar comienzo al trabajo y una función opcional tail que sirve para crear la cola de la lista si queremos.
(define (unfold stop? generate update seed . tail) (if (stop? seed) (if (null? tail) '() ((car tail) seed)) (cons (generate seed) (if (null? tail) (unfold stop? generate update (update seed)) (unfold stop? generate update (update seed) (car tail))))))
Esta función está bien y es muy compacta, pero podría dejarnos sin pila si la lista generada creciera mucho. La siguiente versión es más larga, pero más rápida y sin posibilidad de desbordamiento de pila:
(define (unfold stop? generate update seed . tail) (define (accumulate current-seed current-list) (if (stop? current-seed) (reverse (if (null? tail) current-list (cons ((car tail) current-seed) current-list))) (accumulate (update current-seed) (cons (generate current-seed) current-list)))) (accumulate seed '()))
Esta versión es un poquito más complicada que como podría ser. Estamos haciendo recursión terminal o de cola (tail recursion) con un acumulador porque Scheme da la garantía de que así nunca nos quedaremos sin pila por muy profunda que sea la recursión. Aparte de esto, también es interesante que volvemos a tener la técnica de separar con un punto la lista de argumentos opcionales; como se trata de una lista, para acceder a la propia función guardada en tail hay que acceder al primer elemento (car) de la lista. También podemos hacer una versión iterativa:
(define (unfold stop? generate update seed . tail) (do ((current-seed seed (update current-seed)) (current-list '() (cons (generate current-seed) current-list))) ((stop? current-seed) (reverse (if (null? tail) current-list (cons ((car tail) current-seed) current-list))))))

El equivalente en Python es así:
def unfold(stop_p, generate, update, seed, tail=None): current_list = [] while not stop_p(seed): current_list = current_list + [generate(seed)] seed = update(seed) if tail is not None: current_list = current_list + [tail(seed)] return current_list
Esta versión es así de imperativa porque Python no favorece, en principio, la recursión. La ventaja es que el código es un poquito más corto que el de recursión explícita, pero es más largo que el iterativo. La función predicado stop_p se llama de esta manera como guiño a Lisp. Todo el enfoque que estamos haciendo es quizá poco Pythónico, con mucha definición de funciones de orden superior y muy poca definición de interminables árboles de clases.

Función para generar rangos de números

En Python 2, tenemos la función range para generar un rango de números entre dos extremos (el primero incluido y el último excluido) con un incremento que se pasa como argumento opcional y cuyo valor por defecto es la unidad. De hecho, el primer argumento, que es el comienzo del rango, también es opcional y toma por defecto el valor 0. Vamos a hacer algo similar en Scheme:
(define (range start end step) (let ((comparator (if (> end start) >= <=))) (unfold (lambda (n) (comparator n end)) (lambda (n) n) (lambda (n) (+ n step)) start)))
Este código funciona parecido a como el range de Python 2, pero no comprueba si el paso step conduce a bucles infinitos (si es nulo o apunta en sentido opuesto al que acercaría del comienzo start al final end). Tampoco tiene parámetros opcionales, sino que todos son obligatorios. Otra diferencia está en que esta función no obliga a usar argumentos enteros; podemos usar números racionales y números inexactos (de coma flotante) sin problemas. El uso de unfold abstrae toda la lógica iterativa o recursiva; sin duda, podríamos haber hecho el mismo trabajo con bucles:
(define (range start end step) (let ((comparator (if (> end start) >= <=))) (do ((n start (+ n step)) (accumulator '() (cons n accumulator))) ((comparator n end) (reverse accumulator)))))
La sintaxis es algo críptica, pero el código queda más compacto, sin duda. También podríamos haber usado una función recursiva:
(define (range start end step) (let ((comparator (if (> end start) >= <=))) (if (comparator start end) '() (cons start (range (+ start step) end step)))))
Igual que pasaba con la primera versión recursiva de unfold, este código puede dejarnos sin pila. También podríamos hacer una versión con recursión terminal:
(define (range start end step) (define comparator (if (> end start) >= <=)) (define (accumulate position accumulator) (if (comparator position end) (reverse accumulator) (accumulate (+ position step) (cons position accumulator)))) (accumulate start '()))

Otros artículos de la serie


Categorías: Informática

Permalink: http://sgcg.es/articulos/2013/08/22/jugando-con-automatas-celulares-5/