\n
Ejercicio 1.<\/em> Definir la funci\u00f3n<\/p>\n tal que (cruce xs ys)<\/em> es la lista de las listas obtenidas con uniendo las listas de xs<\/em> sin un elemento con las de ys<\/em> sin un elemento. Por ejemplo,<\/p>\n Ejercicio 2.<\/em> Comprobar con QuickCheck que el n\u00famero de elementos de (cruce xs ys)<\/em> es el producto de los n\u00fameros de elementos de xs<\/em> y de ys<\/em>.<\/p>\n Soluci\u00f3n:<\/em> La comprobaci\u00f3n es<\/p>\n Ejercicio 1.<\/em> Definir la funci\u00f3n cruce<\/em> tal que cruce(xs,ys)<\/em> es la lista de las listas obtenidas con uniendo las listas de xs<\/em> sin un elemento con las de ys<\/em> sin un elemento. Por ejemplo,<\/p>\n Soluci\u00f3n:<\/em><\/p>\n Una definici\u00f3n en Lisp-puro, aportada por Julio Rubio, es la siguiente<\/p>\n La evaluaci\u00f3n de los ejemplos es<\/p>\n Una definici\u00f3n del cruce<\/em> en Prolog es<\/p>\n La evaluaci\u00f3n de los ejemplos es<\/p>\n Un par\u00e1metro para comparar la simplicidad de las definiciones es el n\u00famero de palabras usadas en su definici\u00f3n, incluyendo las usadas en las definiciones auxiliares. Por lo que respecta a la funci\u00f3n cruce<\/em>, ls simplicidad de las distintas definiciones es<\/p>\n 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\u00fameros con ella misma para N igual a 100, 200, 300, 400 y 500.<\/p>\n Los experimentos han sido los siguientes:<\/p>\n Experimentos en Haskell con GHC 6.12.1<\/p>\n Experimentos con Maxima 5.20.1<\/p>\n Experimentos en Lisp con GNU CLISP 2.44.1<\/p>\n En Clisp puede compilarse obtenindo los siguientes resultados<\/p>\n Experimentos en Prolog con SWI Prolog, Version 5.8.0:<\/p>\n En la siguiente tabla se resumen de tiempos (en segundos) de los experimentos es Estos tiempos dependen evidentemente del ordenador y de la versi\u00f3n del lenguaje que se utilice.<\/p>\n Este ejercicio se a\u00f1adir\u00e1 a los libros Ejercicios de programaci\u00f3n en Haskell<\/a> e Introducci\u00f3n al C\u00e1lculo simb\u00f3lico con Maxima<\/a>.<\/p>\n Es el primer ejercicio del libro de Maxima que usa la funci\u00f3n create_list<\/em>. El uso de dicha funci\u00f3n hace que las definiciones en Haskell y Maxima sean semejantes.<\/p>\n","protected":false},"excerpt":{"rendered":" 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\u00e1s, a\u00f1adir\u00e9 soluciones en otros lenguajes conforme las vaya recibiendo. 1. Soluci\u00f3n en Haskell En este ejercico se usar\u00e1n las siguientes librer\u00edas import Data.List import…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5,74],"tags":[84,270,281],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/321"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=321"}],"version-history":[{"count":43,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/321\/revisions"}],"predecessor-version":[{"id":3047,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/321\/revisions\/3047"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\r\ncruce :: Eq a => [a] -> [a] -> [[a]]\r\n<\/pre>\n
\r\n*Main> cruce [1,5,3] [2,4]\r\n[[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]\r\n*Main> cruce [1,5,3] [2,4,6]\r\n[[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],\r\n [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]<\/pre>\n
\n
\nSoluci\u00f3n:<\/em><\/p>\n\r\ncruce :: Eq a => [a] -> [a] -> [[a]]\r\ncruce xs ys = [(delete x xs) ++ (delete y ys) | x <- xs, y <- ys]\r\n<\/pre>\n
\n
\n
\nLa propiedad es<\/p>\n\r\nprop_cruce :: Eq a => [a] -> [a] -> Bool\r\nprop_cruce xs ys =\r\n length (cruce xs ys) == (length xs) * (length ys)\r\n<\/pre>\n
\r\n*Main> quickCheck prop_cruce\r\n+++ OK, passed 100 tests.<\/pre>\n
2. Soluci\u00f3n en Maxima<\/h3>\n
\n\r\n(%i2) cruce([1,5,3],[2,4]);\r\n(%o2) [[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]\r\n(%i3) cruce([1,5,3],[2,4,6]);\r\n(%o3) [[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],\r\n [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]\r\n(%i4) cruce([1,5,3],[2,4,2]);\r\n(%o4) [[5,3,4,2],[5,3,2,2],[5,3,4,2],[1,3,4,2],[1,3,2,2],\r\n [1,3,4,2],[1,5,4,2],[1,5,2,2],[1,5,4, 2]]\r\n<\/pre>\n
\n\r\ncruce(xs,ys) :=\r\n create_list(append(delete(x,xs,1),delete(y,ys,1)),x,xs,y,ys)$\r\n<\/pre>\n
3. Soluci\u00f3n en Lisp<\/h3>\n
\r\n(defun cruce (lista1 lista2)\r\n (flet ((menos-uno (lista)\r\n (do ((postlista lista (rest postlista))\r\n (prelista (list) (cons (first postlista) \r\n prelista))\r\n (listares (list) (cons (revappend\r\n prelista\r\n (rest postlista))\r\n listares)))\r\n ((endp postlista) listares))))\r\n (mapcan #'(lambda (l1) (mapcar #'(lambda (l2) (append l1 l2))\r\n (menos-uno lista2)))\r\n (menos-uno lista1))))\r\n<\/pre>\n
\r\n> (cruce '(1 5 3) '(2 4))\r\n((1 5 2) (1 5 4) (1 3 2) (1 3 4) (5 3 2) (5 3 4))\r\n> (cruce '(1 5 3) '(2 4 6))\r\n((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)\r\n (5 3 2 6) (5 3 4 6))\r\n> (cruce '(1 5 3) '(2 4 2))\r\n((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)\r\n (5 3 2 2) (5 3 4 2))\r\n<\/pre>\n
4. Soluci\u00f3n en Prolog<\/h3>\n
\r\ncruce(Xs,Ys,L) :-\r\n findall(Zs,(select(_,Xs,As),select(_,Ys,Bs),append(As,Bs,Zs)),L).\r\n<\/pre>\n
\r\n?- cruce([1,5,3],[2,4],L).\r\nL = [[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]].\r\n?- cruce([1,5,3],[2,4,6],L).\r\nL = [[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],\r\n [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]].\r\n?- cruce([1,5,3],[2,4,2],L).\r\nL = [[5,3,4,2],[5,3,2,2],[5,3,2,4],[1,3,4,2],[1,3,2,2],\r\n [1,3,2,4],[1,5,4,2],[1,5,2,2],[1,5,2,4]].\r\n<\/pre>\n
5. Simplicidad<\/h3>\n
\n\n
\n Haskell<\/td>\n 25 palabras<\/td>\n<\/tr>\n \n Maxima<\/td>\n 39 palabras<\/td>\n<\/tr>\n \n Prolog<\/td>\n 44 palabras<\/td>\n<\/tr>\n \n Lisp<\/td>\n 104 palabras<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n 6. Eficiencia<\/h3>\n
\r\n-- Definici\u00f3n\r\nlista n = [1..n]\r\n\r\n-- Resultados\r\n-- *Main> :set +s\r\n-- *Main> length (cruce (lista 100) (lista 100))\r\n-- 10000\r\n-- (0.03 secs, 0 bytes)\r\n-- *Main> length (cruce (lista 200) (lista 200))\r\n-- 40000\r\n-- (0.06 secs, 2861084 bytes)\r\n-- *Main> length (cruce (lista 300) (lista 300))\r\n-- 90000\r\n-- (0.12 secs, 5752844 bytes)\r\n-- *Main> length (cruce (lista 400) (lista 400))\r\n-- 160000\r\n-- (0.20 secs, 12440928 bytes)\r\n-- *Main> length (cruce (lista 500) (lista 500))\r\n-- 250000\r\n-- (0.29 secs, 18962144 bytes)\r\n<\/pre>\n
\r\n\/* Definici\u00f3n *\/\r\nlista(n) := makelist(i,i,1,n)$\r\n\r\n\/* Resultados:\r\n (%i3) showtime:true$\r\n Evaluation took 0.0000 seconds (0.0000 elapsed)\r\n (%i4) length(cruce(lista(100),lista(100)));\r\n Evaluation took 1.0400 seconds (1.4900 elapsed)\r\n (%o4) 10000\r\n (%i5) length(cruce(lista(200),lista(200)));\r\n Evaluation took 8.8200 seconds (10.0500 elapsed)\r\n (%o5) 40000\r\n (%i6) length(cruce(lista(300),lista(300)));\r\n No lo calcula. *\/\r\n<\/pre>\n
\r\n;;; Definici\u00f3n\r\n(defun lista (n)\r\n (cond ((= n 1) '(1))\r\n (t (cons n (lista (1- n))))))\r\n\r\n;;; Resultados\r\n;;; [4]> (time (length (cruce (lista 100) (lista 100))))\r\n;;; Real time: 0.710281 sec.\r\n;;; Run time: 0.676042 sec.\r\n;;; Space: 12188088 Bytes\r\n;;; GC: 8, GC time: 0.48803 sec.\r\n;;; 10000\r\n;;; [5]> (time (length (cruce (lista 200) (lista 200))))\r\n;;; Real time: 5.876731 sec.\r\n;;; Run time: 5.732358 sec.\r\n;;; Space: 96695688 Bytes\r\n;;; GC: 18, GC time: 4.31227 sec.\r\n;;; 40000\r\n;;; [6]> (time (length (cruce (lista 300) (lista 300))))\r\n;;; Real time: 18.732824 sec.\r\n;;; Run time: 18.457155 sec.\r\n;;; Space: 325523288 Bytes\r\n;;; GC: 18, GC time: 14.376899 sec.\r\n;;; 90000\r\n;;; [7]> (time (length (cruce (lista 400) (lista 400))))\r\n;;; Real time: 91.2772 sec.\r\n;;; Run time: 40.66254 sec.\r\n;;; Space: 770670888 Bytes\r\n;;; GC: 15, GC time: 30.221888 sec.\r\n;;; 160000\r\n;;; [8]> (time (length (cruce (lista 500) (lista 500))))\r\n;;; *** - No queda espacio para almacenar m\u00e1s objetos LISP\r\n<\/pre>\n
\r\n[2]> (compile-file \"CruceDeListas.lsp\")\r\n;; Compiling file CruceDeListas.lsp ...\r\n;; Wrote file CruceDeListas.fas\r\n0 errores, 0 advertencias\r\n#P\"CruceDeListas.fas\" ;\r\nNIL ;\r\nNIL\r\n[3]> (load \"CruceDeListas\")\r\n;; Loading file CruceDeListas.fas ...\r\n0 errores, 0 advertencias\r\n;; Loaded file CruceDeListas.fas\r\nT\r\n[4]> (time (length (cruce (lista 100) (lista 100))))\r\nReal time: 0.445768 sec.\r\nRun time: 0.444027 sec.\r\nSpace: 12162784 Bytes\r\nGC: 8, GC time: 0.352023 sec.\r\n10000\r\n[5]> (time (length (cruce (lista 200) (lista 200))))\r\nReal time: 4.412166 sec.\r\nRun time: 4.404275 sec.\r\nSpace: 96645584 Bytes\r\nGC: 19, GC time: 3.704231 sec.\r\n40000\r\n[6]> (time (length (cruce (lista 300) (lista 300))))\r\nReal time: 11.520125 sec.\r\nRun time: 11.468717 sec.\r\nSpace: 325448384 Bytes\r\nGC: 11, GC time: 9.104567 sec.\r\n90000\r\n[7]> (time (length (cruce (lista 400) (lista 400))))\r\nReal time: 32.548817 sec.\r\nRun time: 32.538033 sec.\r\nSpace: 770571184 Bytes\r\nGC: 16, GC time: 26.909681 sec.\r\n160000\r\n[8]> (time (length (cruce (lista 500) (lista 500))))\r\n*** - No queda espacio para almacenar m\u00e1s objetos LISP\r\n<\/pre>\n
\r\n% Definici\u00f3n\r\nlista(N,L) :- findall(X,between(1,N,X),L).\r\n\r\n% Resultados:\r\n% ?- time((lista(100,_L1), cruce(_L1,_L1,_L2), length(_L2,N))).\r\n% % 1,020,324 inferences, 1.580 CPU in 1.645 seconds (96% CPU, 645775 Lips)\r\n% N = 10000.\r\n% \r\n% ?- time((lista(200,_L1), cruce(_L1,_L1,_L2), length(_L2,N))).\r\n% % 1,416,109 inferences, 1.200 CPU in 1.244 seconds (96% CPU, 1180091 Lips)\r\n% ERROR: Out of global stack\r\n<\/pre>\n
\n![\"<br](\"https:\/\/s0.wp.com\/latex.php?latex=%3Cbr+%2F%3E+++%5Cbegin%7Barray%7D%7B%7Cl%7Cr%7Cr%7Cr%7Cr%7Cr%7C%7D+%5Chline%3Cbr+%2F%3E++++Lenguaje+++++++%26+N%3D100+%26+N%3D200+%26+N%3D300+%26+N%3D400+%26+N%3D500+%5C%5C+%5Chline%3Cbr+%2F%3E++++Haskell++++++++++%26+++0.03+%26++++0.06+%26++0.12+%26++0.20+%26++0.29+%5C%5C+%5Chline%3Cbr+%2F%3E++++Lisp+++++++++++%26++0.67+%26++5.73+%26+18.46+%26+40.66+%26+++++%5C%5C+%5Chline%3Cbr+%2F%3E++++Lisp%5C+compilado+%26++0.44+%26++4.40+%26+11.47+%26+32.55+%26+++++%5C%5C+%5Chline%3Cbr+%2F%3E++++Maxima++++%09+++%26++1.04+%26++8.82+%26+++++%26+++++%26+++++%5C%5C+%5Chline%3Cbr+%2F%3E++++Prolog+++%09+++%26++1%2C58+%26+++++%26+++++%26+++++%26++++%5C%5C+%5Chline%3Cbr+%2F%3E+++%5Cend%7Barray%7D%3Cbr+%2F%3E+&bg=ffffff&fg=000&s=0&c=20201002\")
7. Comentarios<\/h3>\n