Cruce de listas

En esta entrada comento las soluciones en Haskell y Maxima de un problema planteado por Adam Majewski en la lista de Maxima en forma de ejercicio para I1M y PD. Además, añadiré soluciones en otros lenguajes conforme las vaya recibiendo.

1. Solución en Haskell

En este ejercico se usarán las siguientes librerías

import Data.List
import Test.QuickCheck

1 2	import Data.List import Test.QuickCheck

Ejercicio 1. Definir la función

cruce :: Eq a => [a] -> [a] -> [[a]]

1	cruce :: Eq a => [a] -> [a] -> [[a]]

tal que (cruce xs ys) es la lista de las listas obtenidas con uniendo las listas de xs sin un elemento con las de ys sin un elemento. Por ejemplo,

*Main> cruce [1,5,3] [2,4]
[[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]
*Main> cruce [1,5,3] [2,4,6]
[[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],
 [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]

*Main> cruce [1,5,3] [2,4]

[[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]

*Main> cruce [1,5,3] [2,4,6]

[[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],

[1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]

Solución:

cruce :: Eq a => [a] -> [a] -> [[a]]
cruce xs ys = [(delete x xs) ++ (delete y ys) | x <- xs, y <- ys]

1 2	cruce :: Eq a => [a] -> [a] -> [[a]] cruce xs ys = [(delete x xs) ++ (delete y ys) \| x <- xs, y <- ys]

Ejercicio 2. Comprobar con QuickCheck que el número de elementos de (cruce xs ys) es el producto de los números de elementos de xs y de ys.

Solución:
La propiedad es

prop_cruce :: Eq a => [a] -> [a] -> Bool
prop_cruce xs ys =
    length (cruce xs ys) == (length xs) * (length ys)

prop_cruce :: Eq a => [a] -> [a] -> Bool

prop_cruce xs ys =

length (cruce xs ys) == (length xs) * (length ys)

La comprobación es

*Main> quickCheck prop_cruce
+++ OK, passed 100 tests.

1 2	*Main> quickCheck prop_cruce +++ OK, passed 100 tests.

2. Solución en Maxima

Ejercicio 1. Definir la función cruce tal que cruce(xs,ys) es la lista de las listas obtenidas con uniendo las listas de xs sin un elemento con las de ys sin un elemento. Por ejemplo,

(%i2) cruce([1,5,3],[2,4]);
(%o2) [[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]
(%i3) cruce([1,5,3],[2,4,6]);
(%o3) [[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],
       [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]
(%i4) cruce([1,5,3],[2,4,2]);
(%o4) [[5,3,4,2],[5,3,2,2],[5,3,4,2],[1,3,4,2],[1,3,2,2],
       [1,3,4,2],[1,5,4,2],[1,5,2,2],[1,5,4, 2]]

(%i2) cruce([1,5,3],[2,4]);

(%o2) [[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]

(%i3) cruce([1,5,3],[2,4,6]);

(%o3) [[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],

[1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]

(%i4) cruce([1,5,3],[2,4,2]);

(%o4) [[5,3,4,2],[5,3,2,2],[5,3,4,2],[1,3,4,2],[1,3,2,2],

[1,3,4,2],[1,5,4,2],[1,5,2,2],[1,5,4, 2]]

Solución:

cruce(xs,ys) :=
   create_list(append(delete(x,xs,1),delete(y,ys,1)),x,xs,y,ys)$

1 2	cruce(xs,ys) := create_list(append(delete(x,xs,1),delete(y,ys,1)),x,xs,y,ys)$

3. Solución en Lisp

Una definición en Lisp-puro, aportada por Julio Rubio, es la siguiente

(defun cruce (lista1 lista2)
  (flet ((menos-uno (lista)
                    (do ((postlista lista (rest postlista))
                         (prelista (list) (cons (first postlista)  
                                                prelista))
                         (listares (list) (cons (revappend
                                                 prelista
                                                 (rest postlista))
                                                listares)))
                        ((endp postlista) listares))))
    (mapcan #'(lambda (l1) (mapcar #'(lambda (l2) (append l1 l2))
                                   (menos-uno lista2)))
            (menos-uno lista1))))

(defun cruce (lista1 lista2)

(flet ((menos-uno (lista)

(do ((postlista lista (rest postlista))

(prelista (list) (cons (first postlista)

prelista))

(listares (list) (cons (revappend

prelista

(rest postlista))

listares)))

((endp postlista) listares))))

(mapcan #'(lambda (l1) (mapcar #'(lambda (l2) (append l1 l2))

(menos-uno lista2)))

(menos-uno lista1))))

La evaluación de los ejemplos es

> (cruce '(1 5 3) '(2 4))
((1 5 2) (1 5 4) (1 3 2) (1 3 4) (5 3 2) (5 3 4))
> (cruce '(1 5 3) '(2 4 6))
((1 5 2 4) (1 5 2 6) (1 5 4 6) (1 3 2 4) (1 3 2 6) (1 3 4 6) (5 3 2 4)
 (5 3 2 6) (5 3 4 6))
> (cruce '(1 5 3) '(2 4 2))
((1 5 2 4) (1 5 2 2) (1 5 4 2) (1 3 2 4) (1 3 2 2) (1 3 4 2) (5 3 2 4)
 (5 3 2 2) (5 3 4 2))

> (cruce '(1 5 3) '(2 4))

((1 5 2) (1 5 4) (1 3 2) (1 3 4) (5 3 2) (5 3 4))

> (cruce '(1 5 3) '(2 4 6))

((1 5 2 4) (1 5 2 6) (1 5 4 6) (1 3 2 4) (1 3 2 6) (1 3 4 6) (5 3 2 4)

(5 3 2 6) (5 3 4 6))

> (cruce '(1 5 3) '(2 4 2))

((1 5 2 4) (1 5 2 2) (1 5 4 2) (1 3 2 4) (1 3 2 2) (1 3 4 2) (5 3 2 4)

(5 3 2 2) (5 3 4 2))

4. Solución en Prolog

Una definición del cruce en Prolog es

cruce(Xs,Ys,L) :-
   findall(Zs,(select(_,Xs,As),select(_,Ys,Bs),append(As,Bs,Zs)),L).

1 2	cruce(Xs,Ys,L) :- findall(Zs,(select(_,Xs,As),select(_,Ys,Bs),append(As,Bs,Zs)),L).

La evaluación de los ejemplos es

?- cruce([1,5,3],[2,4],L).
L = [[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]].
?- cruce([1,5,3],[2,4,6],L).
L = [[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],
     [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]].
?- cruce([1,5,3],[2,4,2],L).
L = [[5,3,4,2],[5,3,2,2],[5,3,2,4],[1,3,4,2],[1,3,2,2],
     [1,3,2,4],[1,5,4,2],[1,5,2,2],[1,5,2,4]].

?- cruce([1,5,3],[2,4],L).

L = [[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]].

?- cruce([1,5,3],[2,4,6],L).

L = [[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],

[1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]].

?- cruce([1,5,3],[2,4,2],L).

L = [[5,3,4,2],[5,3,2,2],[5,3,2,4],[1,3,4,2],[1,3,2,2],

[1,3,2,4],[1,5,4,2],[1,5,2,2],[1,5,2,4]].

5. Simplicidad

Un parámetro para comparar la simplicidad de las definiciones es el número de palabras usadas en su definición, incluyendo las usadas en las definiciones auxiliares. Por lo que respecta a la función cruce, ls simplicidad de las distintas definiciones es

Haskell	25 palabras
Maxima	39 palabras
Prolog	44 palabras
Lisp	104 palabras

6. Eficiencia

Siguiendo la sugerencia de Gonzalo Aranda, he comparado la eficiencia de las implementaciones de las distintas definiciones en sus correspondientes lenguajes. Para ello, he medido el tiempo empleado en calcular el cruce de la lista formada por los N primeros números con ella misma para N igual a 100, 200, 300, 400 y 500.

Los experimentos han sido los siguientes:

Experimentos en Haskell con GHC 6.12.1

-- Definición
lista n = [1..n]

-- Resultados
--    *Main> :set +s
--    *Main> length (cruce (lista 100) (lista 100))
--    10000
--    (0.03 secs, 0 bytes)
--    *Main> length (cruce (lista 200) (lista 200))
--    40000
--    (0.06 secs, 2861084 bytes)
--    *Main> length (cruce (lista 300) (lista 300))
--    90000
--    (0.12 secs, 5752844 bytes)
--    *Main> length (cruce (lista 400) (lista 400))
--    160000
--    (0.20 secs, 12440928 bytes)
--    *Main> length (cruce (lista 500) (lista 500))
--    250000
--    (0.29 secs, 18962144 bytes)

-- Definición

lista n = [1..n]

-- Resultados

-- *Main> :set +s

-- *Main> length (cruce (lista 100) (lista 100))

-- 10000

-- (0.03 secs, 0 bytes)

-- *Main> length (cruce (lista 200) (lista 200))

-- 40000

-- (0.06 secs, 2861084 bytes)

-- *Main> length (cruce (lista 300) (lista 300))

-- 90000

-- (0.12 secs, 5752844 bytes)

-- *Main> length (cruce (lista 400) (lista 400))

-- 160000

-- (0.20 secs, 12440928 bytes)

-- *Main> length (cruce (lista 500) (lista 500))

-- 250000

-- (0.29 secs, 18962144 bytes)

Experimentos con Maxima 5.20.1

/* Definición */
lista(n) := makelist(i,i,1,n)$

/* Resultados:
     (%i3) showtime:true$
     Evaluation took 0.0000 seconds (0.0000 elapsed)
     (%i4) length(cruce(lista(100),lista(100)));
     Evaluation took 1.0400 seconds (1.4900 elapsed)
     (%o4)                                10000
     (%i5) length(cruce(lista(200),lista(200)));
     Evaluation took 8.8200 seconds (10.0500 elapsed)
     (%o5)                                40000
     (%i6) length(cruce(lista(300),lista(300)));
     No lo calcula.  */

/* Definición */

lista(n) := makelist(i,i,1,n)$

/* Resultados:

(%i3) showtime:true$

Evaluation took 0.0000 seconds (0.0000 elapsed)

(%i4) length(cruce(lista(100),lista(100)));

Evaluation took 1.0400 seconds (1.4900 elapsed)

(%o4) 10000

(%i5) length(cruce(lista(200),lista(200)));

Evaluation took 8.8200 seconds (10.0500 elapsed)

(%o5) 40000

(%i6) length(cruce(lista(300),lista(300)));

No lo calcula. */

Experimentos en Lisp con GNU CLISP 2.44.1

;;; Definición
(defun lista (n)
  (cond ((= n 1) '(1))
        (t (cons n (lista (1- n))))))

;;; Resultados
;;;    [4]> (time (length (cruce (lista 100) (lista 100))))
;;;    Real time: 0.710281 sec.
;;;    Run time: 0.676042 sec.
;;;    Space: 12188088 Bytes
;;;    GC: 8, GC time: 0.48803 sec.
;;;    10000
;;;    [5]> (time (length (cruce (lista 200) (lista 200))))
;;;    Real time: 5.876731 sec.
;;;    Run time: 5.732358 sec.
;;;    Space: 96695688 Bytes
;;;    GC: 18, GC time: 4.31227 sec.
;;;    40000
;;;    [6]> (time (length (cruce (lista 300) (lista 300))))
;;;    Real time: 18.732824 sec.
;;;    Run time: 18.457155 sec.
;;;    Space: 325523288 Bytes
;;;    GC: 18, GC time: 14.376899 sec.
;;;    90000
;;;    [7]> (time (length (cruce (lista 400) (lista 400))))
;;;    Real time: 91.2772 sec.
;;;    Run time: 40.66254 sec.
;;;    Space: 770670888 Bytes
;;;    GC: 15, GC time: 30.221888 sec.
;;;    160000
;;;    [8]> (time (length (cruce (lista 500) (lista 500))))
;;;    *** - No queda espacio para almacenar más objetos LISP

;;; Definición

(defun lista (n)

(cond ((= n 1) '(1))

(t (cons n (lista (1- n))))))

;;; Resultados

;;; [4]> (time (length (cruce (lista 100) (lista 100))))

;;; Real time: 0.710281 sec.

;;; Run time: 0.676042 sec.

;;; Space: 12188088 Bytes

;;; GC: 8, GC time: 0.48803 sec.

;;; 10000

;;; [5]> (time (length (cruce (lista 200) (lista 200))))

;;; Real time: 5.876731 sec.

;;; Run time: 5.732358 sec.

;;; Space: 96695688 Bytes

;;; GC: 18, GC time: 4.31227 sec.

;;; 40000

;;; [6]> (time (length (cruce (lista 300) (lista 300))))

;;; Real time: 18.732824 sec.

;;; Run time: 18.457155 sec.

;;; Space: 325523288 Bytes

;;; GC: 18, GC time: 14.376899 sec.

;;; 90000

;;; [7]> (time (length (cruce (lista 400) (lista 400))))

;;; Real time: 91.2772 sec.

;;; Run time: 40.66254 sec.

;;; Space: 770670888 Bytes

;;; GC: 15, GC time: 30.221888 sec.

;;; 160000

;;; [8]> (time (length (cruce (lista 500) (lista 500))))

;;; *** - No queda espacio para almacenar más objetos LISP

En Clisp puede compilarse obtenindo los siguientes resultados

[2]> (compile-file "CruceDeListas.lsp")
;; Compiling file CruceDeListas.lsp ...
;; Wrote file CruceDeListas.fas
0 errores, 0 advertencias
#P"CruceDeListas.fas" ;
NIL ;
NIL
[3]> (load "CruceDeListas")
;; Loading file CruceDeListas.fas ...
0 errores, 0 advertencias
;; Loaded file CruceDeListas.fas
T
[4]> (time (length (cruce (lista 100) (lista 100))))
Real time: 0.445768 sec.
Run time: 0.444027 sec.
Space: 12162784 Bytes
GC: 8, GC time: 0.352023 sec.
10000
[5]> (time (length (cruce (lista 200) (lista 200))))
Real time: 4.412166 sec.
Run time: 4.404275 sec.
Space: 96645584 Bytes
GC: 19, GC time: 3.704231 sec.
40000
[6]> (time (length (cruce (lista 300) (lista 300))))
Real time: 11.520125 sec.
Run time: 11.468717 sec.
Space: 325448384 Bytes
GC: 11, GC time: 9.104567 sec.
90000
[7]> (time (length (cruce (lista 400) (lista 400))))
Real time: 32.548817 sec.
Run time: 32.538033 sec.
Space: 770571184 Bytes
GC: 16, GC time: 26.909681 sec.
160000
[8]> (time (length (cruce (lista 500) (lista 500))))
*** - No queda espacio para almacenar más objetos LISP

[2]> (compile-file "CruceDeListas.lsp")

;; Compiling file CruceDeListas.lsp ...

;; Wrote file CruceDeListas.fas

0 errores, 0 advertencias

#P"CruceDeListas.fas" ;

NIL ;

NIL

[3]> (load "CruceDeListas")

;; Loading file CruceDeListas.fas ...

0 errores, 0 advertencias

;; Loaded file CruceDeListas.fas

[4]> (time (length (cruce (lista 100) (lista 100))))

Real time: 0.445768 sec.

Run time: 0.444027 sec.

Space: 12162784 Bytes

GC: 8, GC time: 0.352023 sec.

10000

[5]> (time (length (cruce (lista 200) (lista 200))))

Real time: 4.412166 sec.

Run time: 4.404275 sec.

Space: 96645584 Bytes

GC: 19, GC time: 3.704231 sec.

40000

[6]> (time (length (cruce (lista 300) (lista 300))))

Real time: 11.520125 sec.

Run time: 11.468717 sec.

Space: 325448384 Bytes

GC: 11, GC time: 9.104567 sec.

90000

[7]> (time (length (cruce (lista 400) (lista 400))))

Real time: 32.548817 sec.

Run time: 32.538033 sec.

Space: 770571184 Bytes

GC: 16, GC time: 26.909681 sec.

160000

[8]> (time (length (cruce (lista 500) (lista 500))))

*** - No queda espacio para almacenar más objetos LISP

Experimentos en Prolog con SWI Prolog, Version 5.8.0:

% Definición
lista(N,L) :- findall(X,between(1,N,X),L).

% Resultados:
%    ?- time((lista(100,_L1), cruce(_L1,_L1,_L2), length(_L2,N))).
%    % 1,020,324 inferences, 1.580 CPU in 1.645 seconds (96% CPU, 645775 Lips)
%    N = 10000.
%    
%    ?- time((lista(200,_L1), cruce(_L1,_L1,_L2), length(_L2,N))).
%    % 1,416,109 inferences, 1.200 CPU in 1.244 seconds (96% CPU, 1180091 Lips)
%    ERROR: Out of global stack

% Definición

lista(N,L) :- findall(X,between(1,N,X),L).

% Resultados:

% ?- time((lista(100,_L1), cruce(_L1,_L1,_L2), length(_L2,N))).

% % 1,020,324 inferences, 1.580 CPU in 1.645 seconds (96% CPU, 645775 Lips)

% N = 10000.

% ?- time((lista(200,_L1), cruce(_L1,_L1,_L2), length(_L2,N))).

% % 1,416,109 inferences, 1.200 CPU in 1.244 seconds (96% CPU, 1180091 Lips)

% ERROR: Out of global stack

En la siguiente tabla se resumen de tiempos (en segundos) de los experimentos es
$ \begin{array}{|l|r|r|r|r|r|} \hline Lenguaje & N=100 & N=200 & N=300 & N=400 & N=500 \\ \hline Haskell & 0.03 & 0.06 & 0.12 & 0.20 & 0.29 \\ \hline Lisp & 0.67 & 5.73 & 18.46 & 40.66 & \\ \hline Lisp\ compilado & 0.44 & 4.40 & 11.47 & 32.55 & \\ \hline Maxima & 1.04 & 8.82 & & & \\ \hline Prolog & 1,58 & & & & \\ \hline \end{array} $

Estos tiempos dependen evidentemente del ordenador y de la versión del lenguaje que se utilice.

7. Comentarios

Este ejercicio se añadirá a los libros Ejercicios de programación en Haskell e Introducción al Cálculo simbólico con Maxima.

Es el primer ejercicio del libro de Maxima que usa la función create_list. El uso de dicha función hace que las definiciones en Haskell y Maxima sean semejantes.