Pertenencia

Empezaré con algo muy elemental y sencillo: el predicado Prolog para indicar la pertenencia de un objeto a una lista:

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

Este predicado pregunta si todos los elementos de una lista son iguales.

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({}, {})
 

Antepasados

Vamos ahora a un clásico de los manuales de Prolog: la forma de determinar los antepasados de una persona. Se usa para demostrar la potencia de la programación recursiva.

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

El predicado elimina sustrae un objeto de una lista.

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"}}}
 

Adyacentes

Este es otro ejémplo de programación sencilla y legible en Euphoria.

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..
 

Eliminar duplicados

La finalidad de la siguiente función es eliminar los elementos duplicados de una secuencia.

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.
 

Factorial

¡Cómo no! Este es, seguramente, el ejemplo más asiduamente utilizado para explicar la recursividad.

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?
 

Mezcla

Prolog no siempre puede ofrecer una respuesta que gane claramente en concisión a su alternativa en Euphoria. El código siguiente puede ser un buen ejémplo. Objetivo del mismo: devolver una secuencia ordenada producto de la fusión de otras dos.

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.



(volver)         (siguiente)