Volver arriba
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
Artículos publicados el mismo mes
Permalink:
https://sgcg.es/articulos/2013/08/22/jugando-con-automatas-celulares-5/
Volver arriba
