El que sigue es el ejercicio nro 26 (creo) de la segunda guía de funcional


Se busca un programa que sea capaz de realizar el producto de listas de 
elementos.  Asumiremos que las listas a multiplicar vienen dentro de una lista 
que las contiene.  Por ejemplo, si queremos multiplicar la lista (1 2 3) por la 
lista (4 5), el argumento a nuestra función será ((1 2 3) (4 5)).  El resultado 
esperado en ese caso será: ((1 4) (1 5) (2 4) (2 5) (3 4) (3 5)).


VERSION 1:

Para resolverlo, debemos preguntarnos cómo aprovechar el mecanismo matemático 
de inducción para nuestro propósito.

En el caso del ejemplo propuesto, si el caso k+1 el argumento es ((1 2 3) (4
5)), ¿cuál sería el caso k?  Bueno, puede verse que si la lista primera fuera
(2 3) en lugar de (1 2 3), entonces el resultado parcial sería ((2 4) (2 5) (3
4) (3 5)).

¿Cómo se pasa desde ese resultado parcial al resultado final?

Es claro que hay que agregar ((1 4) (1 5)) al resultado parcial, como primera 
parte del mismo.  ¿Cómo obtengo este "agregado"? Se ve muy bien que debo tomar 
el "1" que había dejado afuera, y multiplicarlo por *toda* la segunda lista.

Hagamos algo de código.  Sea producto el nombre de la función a escribir, 
y sea Lista la lista de entrada no vacía.

Sea Lista -> ((1 2 3) (4 5))

	(car Lista) -> primera lista de números
	(car Lista) -> (1 2 3)
	(cdr Lista) -> ((4 5))

Entonces debo resolver el (producto ((4 5))) ->((4) (5)) 
y luego usaría un (producto-aux (1 2 3) ( (4) (5) )) que pondría cada uno de 
los elementos del primer argumento, como primer elemento de las listas del 
segundo argumento.

(define (producto Lista)
  (cond ((null? Lista) '())
        (else (producto-aux (car Lista) (producto (cdr Lista))))))


Nótese que producto-aux va a colocar los elementos del promer argumento, 
multiplicándolos por el resultado parcial.  El resultado parcial es provisto 
justamente por el programa producto.

Como producto-aux debe iterar por los elementos del primer argumento hasta que 
dicho argumento se vacíe, es cosa ya conocida:

(define (producto-aux cabezas solucion-parcial)
  (cond ((null? cabezas) '())
        ((null? solucion-parcial) (map (lambda (x) (list x)) cabezas))
   ...


O sea, si se ha vaciado cabezas, entonces ya terminó el producto.  Si la 
solucion-parcial es vacía, eso significa que estamos tratando el caso en el 
cual se terminó la lista de listas a multiplicar.

Y ahora falta el caso más complicado, cuando hay que hacer el producto del 
primer elemento de cabezas por todos los de solucion-parcial, y a ese resultado 
concatenarlo con el producto de los otros (resto) elementos de cabezas, hasta 
el final.  Veamos por parte:

Primero veamos el producto del primer (car) elemento de cabezas por los 
elementos de la lista solucion-parcial:

	(map (lambda (x) (cons (car cabezas) x)) solucion-parcial)

El map toma cada elemento de solucion-parcial, lo pone como x para la funcioón 
anónima interna, y ésta concatena el primer elemento de cabezas a ese elemento 
ya citado.  Supongamos que la solucion-parcial ->((4) (5)) y que cabezas sea (1 
2 3).  Entonces la expresión anetrior generará el resultado ((1 4) (1 5))

Ahora nos falta concatenar este resultado con el obtenido de trabajar sobre (2 
3) y (4 5), pero eso es exactamente lo que producto-aux hace.  Entonces lo 
llamamos con los argumentos dados:

	(producto-aux (cdr cabezas) solucion-parcial)

Entonces como (cdr cabezas) da (2 3) y solucion-parcial sigue siendo ((4) 
(5)), la llamada anterior nos responderá: ((2 4) (2 5) (3 4) (3 5)).

Y al concatenarle ((1 4) (1 5)) al principio, tendremos el resultado buscado.  
Eso hace que el código de producto-aux completo quede:

(define (producto-aux cabezas solucion-parcial)
  (cond ((null? cabezas) '())
        ((null? solucion-parcial) (map (lambda (x) (list x)) cabezas))
        (else (append 
               (map (lambda (x) (cons (car cabezas) x)) solucion-parcial)
               (producto-aux (cdr cabezas) solucion-parcial)))))



VERSION 2:

Al releer el programa producto-aux uno se encuentra que se realiza la misma 
operación sobre los elementos de solucion-parcial, repetidamente.  Eso tiene 
olor a un map que ha quedado encerrado.  Analicemos un poco eso.

Cuando tratamos de eliminar la iteración de cola que se realiza sobre cabezas, 
no interferimos con el trabajo sobre solucion-parcial, que como se puede ver en 
el código ogiginal de producto-aux, no se le realiza ninguna modificación.  
Esto nos da la primera parte de nuestro nuevo producto-aux:

(define (producto-aux cabezas solucion-parcial)
  (cond ((null? solucion-parcial) (map (lambda (x) (list x)) cabezas))
   ...

Hemos eliminado el control sobre si está o no vacío cabezas.

¿Cuál es el caso que nos queda ahora?

Recordemos que en el programa anterior, la solución era:

       (append
               (map (lambda (x) (cons (car cabezas) x)) solucion-parcial)
               (producto-aux (cdr cabezas) solucion-parcial))

Ya no tenemos a cabezas para hacerle car, si es que vamos a usar map.  
Sustituyamos (car cabezas) por una variable y que será la variable del map.  
Entonces nos queda:

  (append
         (map (lambda (x) (cons y x)) solucion-parcial)
         (producto-aux (cdr cabezas) solucion-parcial))

La llamada recursiva a producto-aux es exactamente lo que deseamos eliminar 
mediante el mapeo, así que nos queda:

         (map (lambda (x) (cons y x)) solucion-parcial)

Y esta es la función que debo aplicar a cada elemento de cabezas, para 
encontrar las partes de la solución buscada.  La función es:

         (lambda (y) (map (lambda (x) (cons y x)) solucion-parcial))

Y el map queda:

(map (lambda (y) (map (lambda (x) (cons y x)) solucion-parcial)) cabezas)

Por último, estas listas deben concatenarse para dar el resultado final:

(reduce append '()
  (map (lambda (y) (map (lambda (x) (cons y x)) 
                        solucion-parcial))
       cabezas))

Con lo cual el nuevo producto-aux quedará:

(define (producto-aux cabezas solucion-parcial)
  (cond ((null? solucion-parcial) (map (lambda (x) (list x)) cabezas))
        (else (reduce append '()
                      (map (lambda (y) (map (lambda (x) (cons y x)) 
                                            solucion-parcial))
                           cabezas)))))


VERSION 3:

Veamos ahora con más detalle al programa producto:

(define (producto Lista)
  (cond ((null? Lista) '())
        (else (producto-aux (car Lista) (producto (cdr Lista))))))

Puede apreciarse que no ayuda demasiado en conseguir los resultados.  ¿Podremos 
eliminarlo?

Veamos el cuerpo de producto-aux:

  (cond ((null? solucion-parcial) (map (lambda (x) (list x)) cabezas))
        (else (reduce append '()
                      (map (lambda (y) (map (lambda (x) (cons y x))
                                            solucion-parcial))
                           cabezas))))

Al revisar el cuerpo de producto, vemos que en realidad cabezas es simplemente 
(car Lista) y que solucion-parcial es (cdr Lista).  Entonces podemos 
"transplantar" el cuerpo de producto-aux a producto (suponiendo que el caso de 
argumento Lista vacía se resuelva en el nuevo cuerpo); para ello realizamos 
las sustituciones ya mencionadas:

(define (producto Lista)
  (cond ((null? (cdr Lista)) (map (lambda (x) (list x)) (car Lista)))
        (else (reduce append '()
                      (map (lambda (y) (map (lambda (x) (cons y x))
                                            (producto (cdr Lista))))
                           (car Lista))))))

Lo cual nos deja con una versión más compacta.

EOF