pertenece(X, [X|Xs]).
pertenece(X, [Y|Ys])
:- pertenece(X, Ys).
A continuación, la solución que yo diseñé en Euphoria (no digo que sea la mejor, ni que no hayan otras, pero el caso es que es sencilla y funciona)
constant true = 1, false = 0
function pertenece(object x, sequence y) -- ¿'x' está incluido en 'y'?
for i = 1 tolength(y)
do
if equal(x, y[i]) then
return true
end if
end for
return false
end function
Como se puede ver, la solución dada en Prolog es paradigmática de la forma de trabajar de este lenguaje. Superconciso y potente.
Euphoria no es tan escueto, pero todo aquel que esté acostumbrado a la programación imperativa no debería de tener ningún problema para entender lo que hace esta función.
Ahora, con un código un poquito más complicado, podremos buscar en secuencias anidadas.
function pertenece(object x, object y) -- ¿'x' está incluido en 'y'?
if equal(x, y) then
return true
-- sí pertenece
end if
if sequence(y)
then
-- si es una secuencia ...
for i = 1 to
length(y)
do
-- ... la recorremos ...
if pertenece(x, y[i]) then
-- ... recursivamente
return true
-- sí pertenece
end if
end for
end if
return false -- no pertenece
end function
Lo normal es que el programador avezado en otros lenguajes imperativos, como Pascal, se pregunte ahora sobre cual es la ventaja de Euphoria. ¡La búsqueda recursiva no es nada nuevo! Además, la forma en que se escribe resulta tal vez demasiado familiar para que pueda aportar ninguna novedad.
Y, efectivamente, tiene razón. La diferencia estriba, no en el método, sino en la universalidad del código: sirve tanto para buscar un número entre una secuencia de ellos, como para hallar una secuencia dentro de una serie de secuencias. Es más: átomos (así se llaman los números en Euphoria) y secuencias de cualquier complejidad pueden encontrarse entremezclados, y el código visto arriba serviría igual ¡sin necesidad de variar ni una línea! Aquí es donde aparece cierta similitud con Prolog.
Veamos un ejémplo de uso de la función pertenece.
atom
objeto
objeto = 3.3
sequence
lista
lista = {2,
5, {"hola", 4.56, {"adios",
3.3}, 10000}, "fin"}
printf(SCREEN, "Pertenece? (1 = si, 0 = no): %d\n", pertenece(objeto, lista))
En pantalla aparecería la siguiente salida:
Pertenece? (1 = si, 0 = no): 1
todos_iguales([]).
% la lista está vacia
todos_iguales([X]).
% la lista sólo tiene un elemento
todos_iguales([X, X|Xs])
:- todos:_iguales(X, Xs).
Ahora, veamos la solución que he implementado en Euphoria.
function
todos_iguales(sequence x)
sequence
lista
if
equal({}, x) then
--
la secuencia está vacia
return true
else
lista = repeat(x[1],
length(x))
-- se crea una secuencia repetida de objetos x[1]
return equal(lista, x)
-- se comparan
end if
end function
Esta función no es recursiva, (luego en teoría debería de consumir menos recursos del sistema, ¿no?), y no es mucho más complicada que la solución dada en Prolog. Además, las funciones repeat y equal están optimizadas para una rápida ejecución.
Naturalmente, también está la solución clásica de los lenguajes imperativos.
function todos_iguales(sequence x)
if
equal({}, x) then
--
la secuencia está vacia
return true
else
for i = 1 to length(x)
do
if not equal(x[1], x[i]) then
return false
end if
end for
return true
end
if
end function
Este código también resulta familiar, ¿verdad? Pero, una vez más, tenemos la ventaja de que la secuencia puede estar compuesta tanto de átomos como de otras secuencias. Veamos unos ejemplos:
todos_iguales({3, 3,
3, 3})
todos_iguales({{2, "Hola"},
{2, "Hola"}, {2, "Hola"}})
todos_iguales({})
todos_iguales({}, {})
Empecemos, como siempre, viendo el código escrito en Prolog. Se supone que ya se han determinado una serie de cláusulas explicitando la relación progenitor (lo que se suelen denominar hechos).
antepasado(X, Y)
:- progenitor(X, Y).
antepasado(X,
Y) :- progenitor(Z, Y), antepasado(X, Z).
Una vez más comprobamos la innegable concisión y elegancia de este lenguaje.
Veamos cómo podríamos hacerlo en Euphoria. Comenzamos definiendo una secuencia con los hechos progenitor.
constant PADRE = 1, HIJO = 2
sequence
progenitor
-- 'a' es
progenitor de 'b'
progenitor = {{"Ana",
"Pedro"},
{"Luisa",
"Ana"},
{"Andres",
"Luisa"},
{"Roberto",
"Ana"},
{"Gustavo", "Celeste"},
{"Luisa", "Gines"},
{"Jorge", "Pedro"}}
Y, ahora, la función es_antepasado, que determina si 'a' es antepasado de 's'. Los hechos progenitor se pasan en 'p'.
function
es_antepasado(sequence a, sequence
s,
sequence p) --
retorna 'a' si es el antepasado
sequence
rel
-- de 's'. Si no, retorna "".
rel = {}
for
i = 1 to length(p)
do
-- buscamos por toda la base de hechos
if equal(lower(p[i][HIJO]),
lower(s)) then
-- si 's' es el hijo ...
if equal(lower(p[i][PADRE]),
lower(a)) then
--
... y 'a' es el padre ...
return p[i][PADRE]
-- ... entonces 'a' es el antepasado
else
rel &= es_antepasado(a, p[i][PADRE], p)
--
si no, ¿lo es el padre de 'a'?
end if
end if
end for
return rel
end function
Como puede verse, la sintaxis es más prolija, pero ¿os parece mucho más complicada de entender? Pues a ver qué os parece esta segunda solución.
Primero definimos una función que nos proporcione todos los antepasados de 's'.
function
antepasados(sequence s, sequence
p)
-- todos los antepasados de 's'
sequence
rel
rel = {}
for
i = 1 to length(p)
do
-- recorremos toda la base de hechos
if equal(lower(p[i][HIJO]),
lower(s)) then
--
si 's' figura como hijo de alguien ...
rel = append(rel, p[i][PADRE])
-- ... ese alguien pasa a la lista ...
rel &= antepasados(p[i][PADRE], p)
-- ... y preguntamos por sus padres
end if
end for
return rel -- devolvemos la lista de ancestros de 's' (si los hay; si no, 'rel' será {})
end function
Ahora, usando la función antepasados, resolvemos el anterior problema.
function
es_antepasado_b(sequence a, sequence
s,
sequence p)
integer
i
sequence
rel
rel = {}
rel = antepasados(s,
p) -- obtenemos la lista de ancestros
de 's'
i = find(a, rel)
-- y buscamos a 'a' en dicho árbol
if i then
-- 'i' indica la posición en 'rel'
que 'a' ocupa. Si no está, ...
return rel[i]
-- ... i será 0 ( 0 = falso; no 0 = verdadero)
else
return ""
end if
end function
Lo bueno de esta segunda solución es que resulta mucho más intuitiva y fácil de entender que la primera. Y en eso estoy con la filosofía que mueve a Euphoria: ante todo, sencillez y legibilidad.
¿Y si es_antepasado_b sólo tuviera que responder verdadero o falso? Veámoslo desde el punto de vista de la concisión.
function es_antepasado_b(sequence a, sequence s, sequence p)
return find(a, antepasados(s, p)) -- 0 = falso; no 0 = verdadero
end function
¿Os parece que haya perdido legibilidad?
elimina(X, [X|Xs], Xs).
elimina(X, [Y|Ys], [Y|Zs])
:- elimina(X, Ys, Zs).
El resultado es otra lista a la que le falta el objeto sustraido.
En Euphoria podría hacerse así.
function
elimina(object o, sequence
s)
integer
pos
pos = find(o,
s)
-- busca 'o' en 's'
if pos then
s = s[1..(pos -
1)] & s[(pos +
1)..(length(s))]
--
concatena ambos extremos de s
end if
return s
end function
Prolog hace un uso intensivo de la recursividad, pero esto no siempre es necesario. La solución en Euphoria no es mucho más complicada, ni mucho menos entendible (creo yo).
Pero, haciendo uso de la recursividad, vamos a modificar la anterior función para que elimine el objeto 'o' de 's', aunque esté dentro de secuencias anidadas.
function
elimina(object o, sequence
s)
integer
pos
pos = find(o,
s)
if
pos then
s = s[1..(pos -
1)] & s[(pos +
1)..(length(s))]
return s
end
if
-- Si hemos llegado hasta aquí, es que el objeto no se encuentra a este nivel de anidamiento
for i = 1 tolength(s)
do
--
recorremos la secuencia
if sequence(s[i])
then
--
si el elemento es, a su vez, otra secuencia ...
s[i] = elimina(o, s[i]) -- ... procedemos
con ella de forma recursiva
end if
end for
return s
end function
Reflexionemos un momento sobre esta función. Si el objeto buscado se encuentra repetido dentro del mismo nivel de anidamiento, se eliminará sólo el primero encontrado. Es lo que queremos. Ahora, si desearamos eliminar todas las ocurrencias de dicho objeto, esté donde esté, bastaría con eliminar (o convertir en comentario) el primer return. Mejor aun: dotemos de ambas posibilidades a la misma función, indicándole con un parámetro lo que deseamos que haga.
function
elimina(object o, sequence
s,
integer todos)
integer
pos
pos = find(o,
s)
if
pos then
s = s[1..(pos -
1)] & s[(pos +
1)..(length(s))]
if not todos then
-- si es 0, sólo eliminamos al primero
return s
end if
end if
for i = 1 to length(s)
do
--
recorremos la secuencia
if sequence(s[i])
then
--
si el elemento es, a su vez, otra secuencia ...
s[i] = elimina(o, s[i]) -- ... procedemos
con ella de forma recursiva
end if
end for
return s
end function
Una vez más, al definir 'o' como del tipo object, podemos pasar tanto átomos como secuencias, tal y como se puede ver a continuación.
elimina({3, "Hola"}, {1.102, "Hola", {1, 2, "", {3, "Hola"}}, 3, {3, {"Hola"}}, {3, "Hola"}}, true)
Lo que daría el siguiente resultado:
{1.102, "Hola", {1, 2, ""},
3, {3, {"Hola"}}}
function
adyacentes(object a, object
b,
sequence lista) --
muestra si dos objetos
sequence
pareja
-- son adyacentes en
-- una secuencia
pareja = a & b -- concatenamos
los dos objetos en un orden ...
if match(pareja,
lista) then
return true
end
if
pareja = b & a -- ... y luego en el otro
if match(pareja,
lista) then
return true
else
return false
end
if
end function
Un ejémplo de uso de esta función sería:
adyacentes(3, {7, 4}, {9, 8, 7, 4, 3, 6, 4, 5})
Al concatenar 3, y {7, 4} obtenemos la secuencia resultante {3, 7, 4}. Buscamos esta secuencia en 'lista', sin éxito. Entonces, probamos el otro orden ({7, 4, 3}), que sí es una sub-secuencia de la secuencia 'lista', por lo que el resultado es verdadero.
Sin embargo, ¿cómo haríamos para que la función buscara la adyacencia del átomo 3 y la secuencia {7, 4}, no las sub-secuencias {3, 7, 4} o {7, 4, 3}? Veamoslo.
function
adyacentes(object a, object
b,
sequence lista)
sequence
pareja
pareja = {}
pareja = append(append(pareja,
a), b)
if
match(pareja, lista) then
return true
end
if
pareja = {}
pareja = append(append(pareja,
b), a)
if
match(pareja, lista) then
return true
else
return false
end
if
end function
¿Merece la pena intentar simplificarlo más? Bueno, por probar ...
function adyacencia(object a, object b, sequence lista)
return ((match(append(append({}, a), b), lista)) != 0)
end function
function adyacentes(object a, object b, sequence lista)
if
adyacencia(a, b, lista)
then
return true
else
return adyacencia(b, a, lista)
end
if
end function
Aparte de ser algo más corto, tenemos que, si bien la función adyacentes ha ganado en simplicidad, la función accesoria adyacencia resulta bastante menos "intuitiva".
En todo caso, ambas soluciones funcionan, y se trataría tan sólo
de optar entre concisión y legibilidad..
function
sinDuplicados(sequence origen,
integer
ordenado) --
da como resultado la misma
sequence
resultado
-- secuencia, sin duplicados
resultado = {} -- aquí
se almacena la secuencia resultante
for i = 1 to
length(origen) do
-- recorremos la secuencia origen
if not(find(origen[i],
resultado))
then --
si el elemento no está ya en resultado ...
resultado =
append(resultado, origen[i])
-- ... lo añadimos
end if
end for
if ordenado then
-- si ordenado != 0, entonces se quiere,
además, que esté ordenada
resultado = sort(resultado)
end
if
return resultado
end function
Bastante sencillo, ¿no es cierto?
A ver un ejémplo.
sinDuplicados({3, 5, {1, 7}, 4, 1, 2, 6, 5, {1, 7}, 1}, 1)
El resultado será este:
{1, 2, 3, 4, 5, 6, {1, 7}}
Aquí se ve una característica a tener en cuenta de Euphoria:
los átomos se ubican antes que las secuencias en una secuencia ordenada
con sort.
Además, sort
siempre ordena ascendentemente.
Vamos a ver las dos soluciones habituales: con y sin recursión.
function factorial(integer numero) -- usando la técnica recursiva
if numero = 0 then
return 1
else
return numero * factorial(numero
-
1)
end
if
end function
function
factorial(integer numero)
-- sin recursión
integer
resultado
resultado =
1
if
numero != 0 then
for n = 1 to numero do
resultado *= n
end for
end if
return resultado
end function
¿Hacen falta más explicaciones?
En Prolog (sin predicados predefinidos).
mezcla(Xs, [], Xs).
mezcla([], [Y|Ys], [Y|Ys]).
mezcla([X|Xs], [Y|Ys],
[X|Zs]) :- X < Y, mezcla(Xs, [Y|Ys], Zs).
mezcla([X|Xs], [Y|Ys],
[Y|Zs]) :- X >= Y, mezcla([X|Xs], Ys, Zs).
En SWI Prolog (usando predicados predefinidos)
mezcla(L1, L2, S3) :- msort(L1, S1), msort(L2, S2), merge(S1, S2, S3).
En Euphoria.
function mezcla(sequence s1, sequence s2)
return sort(s1 & s2)
end
function
Nótese que la primera solución Prolog requiere que ambas listas a fusionar estén previamente ordenadas.