El problema de la igualdad de los bordes de los árboles binarios (sameFringe)
Dos árboles binarios tienen iguales los bordes si tienen exactamente
las mismas hojas leídas de izquierda a derecha, independientemente de
nodos interiores. Por ejemplo,
|
1 2 3 4 5 6 |
árbol1 árbol2 árbol3 árbol4 o o o o / \ / \ / \ / \ 1 o o 3 o 3 o 1 / \ / \ / \ / \ 2 3 1 2 1 4 2 3 |
Los bordes de los árboles 1 y 2 son iguales, aunque tiene distintas
estructuras internas. El árbol 3 no tiene el mismo borde que el 1 o
el 2, debido al nodo 4. El árbol 4 tampoco tiene el mismo borde que
el 1 debido al orden en que se leen las hojas.
El problema de la igualdad de los bordes de los árboles binarios
(samefringe, en inglés) consiste en decidir si dos árboles tienen los bordes iguales.
Según Richard Gabriel en su artículo The Design of Parallel Programming Languages, en 1977 hubo un debate en el ACM SIGART Newsletter sobre si samefringe es el problema más simple que necesita multiproceso o corrutinas para resolverse fácil y eficientemente. En el debate intervinieron muchas personas, entre ellas John McCarthy cuya primera solución fue la siguiente:
|
1 2 3 4 5 6 7 |
(defun leaves (tree) (cond ((atom tree) (list tree)) (t (append (leaves (car tree)) (leaves (cdr tree)))))) (defun samefringe (tree1 tree2) (equal (leaves tree1) (leaves tree2))) |
En Same Fringe Problem se presentan soluciones del problema en distintos lenguajes de programación.
Recientemente se propuso samefringe como tarea de Programming Praxis.
A continuación voy a mostrar soluciones al problema samefringe en lenguajes funcionales perezosos (Haskell) e impacientes (Maxima y Lisp.
Las soluciones se presentan como ejercicios para el curso de Informática (del Grado de Matemáticas) y para los libros de Introducción al cálculo simbólico con Maxima y Ejercicios de programación en Haskell.
Como se observa en la tabla del final del artículo, el perezoso Haskell agota a los impacientes Maxima y Lisp.
Solución en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
-- --------------------------------------------------------------------- -- Ejercicio 1. Definir el tipo de dato de los árboles binarios, según -- las siguientes reglas: -- * si t1 y t2 son árboles binarios con hojas de tipo a, entonces -- (Nodo t1 t2) también lo es. -- * si x es un del tipo a, entonces (Hoja x) es un árbol binario de -- tipo a. -- --------------------------------------------------------------------- data Arbol a = Nodo (Arbol a) (Arbol a) | Hoja a deriving Show -- --------------------------------------------------------------------- -- Ejercicio 2. Definir las constantes -- arbol1, arbol2, arbol3, arbol4 :: Arbol Int -- para representar los siguientes árboles binarios -- árbol1 árbol2 árbol3 árbol4 -- o o o o -- / \ / \ / \ / \ -- 1 o o 3 o 3 o 1 -- / \ / \ / \ / \ -- 2 3 1 2 1 4 2 3 -- --------------------------------------------------------------------- arbol1, arbol2, arbol3, arbol4 :: Arbol Int arbol1 = Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3)) arbol2 = Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3) arbol3 = Nodo (Nodo (Hoja 1) (Hoja 4)) (Hoja 3) arbol4 = Nodo (Nodo (Hoja 2) (Hoja 3)) (Hoja 1) -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- borde :: Arbol a -> [a] -- tal que (borde t) es el borde del árbol t; es decir, la lista de las -- hojas del árbol t leídas de izquierda a derecha. Por ejemplo, -- borde arbol4 == [2,3,1] -- --------------------------------------------------------------------- borde :: Arbol a -> [a] borde (Nodo i d) = borde i ++ borde d borde (Hoja x) = [x] -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- igualBorde :: Eq a => Arbol a -> Arbol a -> Bool -- tal que (igualBorde t1 t2) se verifica si los bordes de los árboles -- t1 y t2 son iguales. Por ejemplo, -- igualBorde arbol1 arbol2 == True -- igualBorde arbol1 arbol3 == False -- igualBorde arbol1 arbol4 == False -- --------------------------------------------------------------------- igualBorde :: Eq a => Arbol a -> Arbol a -> Bool igualBorde t1 t2 = borde t1 == borde t2 -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- arbolProf :: Int -> a -> Arbol a -- tal que (arbolProf n x) es el árbol completo de profundidad n cuyas -- hojas son el elemento x. Por ejemplo, -- *Main> arbolProf 1 5 -- Hoja 5 -- *Main> arbolProf 2 5 -- Nodo (Hoja 5) (Hoja 5) -- *Main> arbolProf 3 5 -- Nodo (Nodo (Hoja 5) (Hoja 5)) (Nodo (Hoja 5) (Hoja 5)) -- --------------------------------------------------------------------- arbolProf :: Int -> a -> Arbol a arbolProf 1 x = Hoja x arbolProf (n+1) t = Nodo t' t' where t' = arbolProf n t -- --------------------------------------------------------------------- -- Ejercicio 6. Se define la función -- problema :: Int -> Bool -- problema n = igualBorde (arbolProf n 5) (arbolProf n 7) -- Calcular los tiempos necesarios para calcular las siguientes -- expresiones -- (problema 20) -- (problema 21) -- (problema 22) -- (problema 23) -- (problema 24) -- (problema 25) -- (problema 30) -- --------------------------------------------------------------------- problema :: Int -> Bool problema n = igualBorde (arbolProf n 5) (arbolProf n 7) -- La sesión es -- *Main> :set -fobject-code -- *Main> :load "IgualBorde.hs" -- [1 of 1] Compiling Main ( IgualBorde.hs, IgualBorde.o ) -- Ok, modules loaded: Main. -- *Main> :set +s -- *Main> problema 10 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 15 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 20 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 21 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 22 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 23 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 24 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 25 -- False -- (0.00 secs, 0 bytes) -- *Main> problema 30 -- False -- (0.00 secs, 0 bytes) |
Este ejercicio se basa en el artículo Carl Hewitt’s Same-Fringe Problem de Remco Niemeijer publicada en Bonsai Code.
Solución en Maxima
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
/* --------------------------------------------------------------------- * Ejercicio 1. Definir las constantes arbol1, arbol2, arbol3 y arbol4 * para representar los siguientes árboles binarios * árbol1 árbol2 árbol3 árbol4 * o o o o * / \ / \ / \ / \ * 1 o o 3 o 3 o 1 * / \ / \ / \ / \ * 2 3 1 2 1 4 2 3 * ------------------------------------------------------------------ */ arbol1 : [1,[2,3]]$ arbol2 : [[1,2],3]$ arbol3 : [[1,4],3]$ arbol4 : [[2,3],1]$ /* --------------------------------------------------------------------- * Ejercicio 2. Definir la función borde tal que borde(t) es el borde * del árbol t; es decir, la lista de las hojas del árbol t leídas de * izquierda a derecha. Por ejemplo, * borde(arbol4) = [2,3,1] * ------------------------------------------------------------------ */ borde (a) := if a=[] then a else if atom(a) then [a] else append(borde(first(a)),borde(rest(a)))$ /* --------------------------------------------------------------------- * Ejercicio 3. Definir la función igualBorde tal que (igualBorde t1 t2) * se verifica si los bordes de los árboles t1 y t2 son iguales. Por * ejemplo, * (%i50) igualBorde(arbol1,arbol2); * (%o50) true * (%i51) igualBorde(arbol1,arbol3); * (%o51) false * (%i52) igualBorde(arbol1,arbol4); * (%o52) false * ------------------------------------------------------------------ */ igualBorde(t1,t2) := is(borde(t1) = borde(t2))$ /* --------------------------------------------------------------------- * Ejercicio 4. Definir la función arbolProf tal que (arbolProf n x) es * el árbol completo de profundidad n cuyas hojas son el elemento x. Por * ejemplo, * (%i67) arbolProf(1,5); * (%o67) [5] * (%i68) arbolProf(2,5); * (%o68) [[5], [5]] * (%i69) arbolProf(3,5); * (%o69) [[[5], [5]], [[5], [5]]] * ------------------------------------------------------------------ */ arbolProf(n,x) := if n=1 then [x] else [arbolProf(n-1,x),arbolProf(n-1,x)]$ /* --------------------------------------------------------------------- * Ejercicio 5. Se define el siguiente problema * problema(n) := igualBorde(arbolProf(n,5),arbolProf(n,7))$ * Calcular los tiempos necesarios para calcular las siguientes * expresiones * problema(20) * problema(21) * problema(22) * problema(23) * problema(24) * problema(25) * problema(30) * ------------------------------------------------------------------ */ problema(n) := igualBorde(arbolProf(n,5),arbolProf(n,7))$ /* La sesión es * (%i9) compile(all)$ * (%i10) showtime : true$ * Evaluation took 0.0000 seconds (0.0000 elapsed) * (%i11) problema1(20); * Evaluation took 30.7100 seconds (31.3700 elapsed) * (%o11) false * (%i12) problema1(21); * Evaluation took 55.9600 seconds (57.4400 elapsed) * (%o12) false * (%i13) problema1(22); */ |
Solución en Lisp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
;;; --------------------------------------------------------------------- ;;; Ejercicio 1. Definir las constantes arbol1, arbol2, arbol3 y arbol4 ;;; para representar los siguientes árboles binarios ;;; árbol1 árbol2 árbol3 árbol4 ;;; o o o o ;;; / \ / \ / \ / \ ;;; 1 o o 3 o 3 o 1 ;;; / \ / \ / \ / \ ;;; 2 3 1 2 1 4 2 3 ;;; --------------------------------------------------------------------- (setq arbol1 '(1 (2 3)) arbol2 '((1 2) 3) arbol3 '((1 4) 3) arbol4 '((2 3) 1)) ;;; --------------------------------------------------------------------- ;;; Ejercicio 2. Definir la función borde tal que (borde t) es el borde ;;; del árbol t; es decir, la lista de las hojas del árbol t leídas de ;;; izquierda a derecha. Por ejemplo, ;;; (borde arbol4) = (2 3 1) ;;; --------------------------------------------------------------------- (defun borde (a) (cond ((null a) a) ((atom a) (list a)) (t (append (borde (car a)) (borde (cdr a)))))) ;;; --------------------------------------------------------------------- ;;; Ejercicio 3. Definir la función igualBorde tal que (igualBorde t1 t2) ;;; se verifica si los bordes de los árboles t1 y t2 son iguales. Por ;;; ejemplo, ;;; (igualBorde arbol1 arbol2) = T ;;; (igualBorde arbol1 arbol3) = NIL ;;; (igualBorde arbol1 arbol4) = NIL ;;; --------------------------------------------------------------------- (defun igualBorde (t1 t2) (equal (borde t1) (borde t2))) ;;; --------------------------------------------------------------------- ;;; Ejercicio 4. Definir la función arbolProf tal que (arbolProf n x) es ;;; el árbol completo de profundidad n cuyas hojas son el elemento x. Por ;;; ejemplo, ;;; (arbolProf 1 5) = (5) ;;; (arbolProf 2 5) = ((5) (5)) ;;; (arbolProf 3 5) = (((5) (5)) ((5) (5))) ;;; --------------------------------------------------------------------- (defun arbolProf (n x) (cond ((= n 1) (list x)) (t (list (arbolProf (1- n) x) (arbolProf (1- n) x))))) ;;; --------------------------------------------------------------------- ;;; Ejercicio 5. Se define el siguiente problema ;;; (defun problema (n) ;;; (igualBorde (arbolProf n 5) (arbolProf n 7))) ;;; Calcular los tiempos necesarios para calcular las siguientes ;;; expresiones ;;; (problema 20) ;;; (problema 21) ;;; (problema 22) ;;; (problema 23) ;;; (problema 24) ;;; (problema 25) ;;; (problema 30) ;;; --------------------------------------------------------------------- (defun problema (n) (igualBorde (arbolProf n 5) (arbolProf n 7))) ;;; La sesión es ;;; [4]> (compile-file "IgualBorde.lsp") ;;; [5]> (load "IgualBorde.fas") ;;; T ;;; [6]> (time (problema 20)) ;;; Real time: 9.307735 sec. ;;; Run time: 9.308582 sec. ;;; Space: 201326560 Bytes ;;; GC: 36, GC time: 5.032318 sec. ;;; NIL ;;; [7]> (time (problema 21)) ;;; Real time: 19.11963 sec. ;;; Run time: 19.093193 sec. ;;; Space: 419430368 Bytes ;;; GC: 33, GC time: 10.436651 sec. ;;; NIL ;;; [8]> (time (problema 22)) ;;; Real time: 39.09912 sec. ;;; Run time: 37.92237 sec. ;;; Space: 872415200 Bytes ;;; GC: 35, GC time: 20.329266 sec. ;;; NIL ;;; [9]> (time (problema 23)) ;;; Real time: 76.02747 sec. ;;; Run time: 74.488655 sec. ;;; Space: 1811939296 Bytes ;;; GC: 37, GC time: 38.970432 sec. ;;; NIL ;;; [10]> (time (problema 24)) ;;; Real time: 152.46944 sec. ;;; Run time: 150.76143 sec. ;;; Space: 3758096352 Bytes ;;; GC: 39, GC time: 78.11288 sec. ;;; NIL ;;; [11]> (time (problema 25)) ;;; Real time: 267.91818 sec. ;;; Run time: 265.7806 sec. ;;; Space: 7784628192 Bytes ;;; GC: 45, GC time: 140.9208 sec. ;;; NIL ;;; [12]> (time (problema 30)) ;;; *** - No queda espacio para almacenar más objetos LISP ;;; El resumen es ;;; +----+----------+---------------+ ;;; | n | segundos | bytes | ;;; +----+----------+---------------+ ;;; | 20 | 9.30 | 201.326.560 | ;;; | 21 | 19.09 | 419.430.368 | ;;; | 22 | 37.92 | 872.415.200 | ;;; | 23 | 74.48 | 1.811.939.296 | ;;; | 24 | 150.76 | 3.758.096.352 | ;;; | 25 | 265.78 | 7.784.628.192 | ;;; | 30 | Agotado | Agotado | ;;; +----+----------+---------------+ |
Comparaciones
Respecto de la simplicidad, las soluciones en los 3 lenguajes son análogas a la de J. McCarthy.
Respecto de la eficiencia, hay grandes diferencias en los tiempos empleados como se resume en la siguiente tabla
Las versiones utilizadas son GHC 6.12.1 para Haskell, la 5.20.1 de Maxima y CLISP 2.44.1 para Lisp.
Se observa que el perezoso Haskell agota a los impacientes Maxima y Lisp.