Realizando cálculos con listas

Ahora que ya sabemos qué son las listas y cómo se representan, podemos pasar al tema de cómo trabajar con ellas, en específico, cómo realizar cálculos con ellas. Pero antes de ir a ello, repasemos cómo construir una lista, pero esta vez desde una perspectiva «más programática», pues si vamos a trabajar con listas esto es lo primero que debemos saber, cómo construirlas pieza por pieza.

Bueno, una lista es un valor como cualquier otro (de tipo «lista», por supuesto), de modo que podemos sin ningún problema asociarlas a una variable. Entendido esto, podemos empezar, por lo tanto, declarando un identificador X1 para que represente a nuestra lista, y luego asignar a este identificador una representación textual de la lista que queremos que represente. Aunque, espera!, si basamos nuestra representación según la definición formal (pues la idea es construir la lista pieza por pieza), le podemos asignar una lista vacía (cosa que no queremos ahora), o un elemento seguido de otra lista. Con el elemento no hay problema, pero ¿Y la otra lista?. Cierto, vamos a tener que declarar otro identificador adicional para que represente a esa «otra lista». Con eso, ya podemos definir nuestra primera pieza tal como se muestra a continuación:

declarar X1, X2
X1 = 10 | X2

Ya con este primer paso, lo que sigue no es difícil. Ahora para extender esa lista debemos asignar una nueva lista a X2. Para ello, declaramos una nueva variable X3, y la utilizamos para representar la lista asociada a la definición de lista de X2.

declarar X3
X2 = 11 | X3

Nota que sólo declaramos X3, si volvemos a declarar a X2, entonces ya no hará referencia a la misma variable que declaramos antes. Nota también, que considerando que aún estamos en paradigma funcional, las variables siguen siendo de asignación única. Puedo declarar una variable, y luego asignarle un valor mucho después, pero sólo una vez. Bien, a continuación, dependiendo la cantidad de elementos que queramos incluir en la lista el paso anterior se repite una y otra vez. Se declara un identificador para que represente a una nueva lista a incluir en la siguiente definición, y luego se asigna esa definición a la variable anterior que quedaba sin asignar. Cuando ya estemos listos con nuestra lista, para finalizar simplemente asignamos una lista vacía a la última variable sin asignar.

X3 = nil

Con esto, ya tenemos nuestra lista construida paso por paso.

Nota: Por supuesto, hubiera sido más rápido haberla definido como 10|11|nil, pero la idea era entender la construcción pieza por pieza según la definición. Adicionalmente, también se podría haber definido alguna otra sintaxis que ofreciera el lenguaje (algun azúcar sintáctico para las listas) como podría ser [10, 11].

Nota2: En esta construcción con pseudocódigo hemos asumido la existencia de un operador | que significa «un elemento seguido de otro (o de una lista)», para así seguir su definición teórica. Sin embargo, no todos los lenguajes incluyen necesariamente una sintaxis para representar esta idea, y muchas veces se limitan (si es que soportan las listas) a algún azúcar sintáctico como [1, 2, 3] para representarlas, que deja oculta su definición teórica. O también se puede dar el caso que lo que en ese lenguaje llamen listas sea algo completamente distinto a la idea aquí expresada, en el sentido que su implementación siga una lógica completamente distinta (ejemplo, las listas en Python).

Nota3: En muchos lenguajes que soportan esta sintaxis, a la parte izquierda de la definición (al elemento) se le llama la «cabeza de la lista» (o en LISP, usualmente como car), y a la parte derecha (a la otra lista) como la «cola de la lista» (En LISP, usualmente como cdr).

Sumando los elementos de una lista numérica

Bien, es momento de revisar cómo recorrer una lista, y por consiguiente, cómo definir funciones recursivas con el fin de realizar cálculos con listas. Para lo que sigue, añadiremos a nuestro pseudocódigo dos nuevas funcionalidades más, .head y .tail, para obtener el encabezado y la cola de una lista, respectivamente. Estas funcionalidades, en realidad, vienen incluidas en la mayoría (por no decir todos) los lenguajes que incluyen soporte preconstruido para listas basadas en la definición que hemos dado. De no incluirlas, sólo podríamos construir listas, pero no contaríamos con ningún medio de acceso para las listas ya construidas. No podríamos recorrerlas. Bien, como primer ejemplo consideremos una función que sume todos los números incluidos en una lista. ¿Cómo lo hacemos?. Bueno, debemos pasar la lista como argumento por supuesto. Pero ¿Cómo calculamos la suma?. En realidad, hay una forma que no es complicada de deducir. Si nos dirigimos a la definición de lista podemos vemos que una, siempre que no esté vacía, no es más que «un elemento seguido de otra lista». Es decir, basándonos en esa definición, podríamos decir que la suma de los elementos de una lista no es más que «la suma de un elemento más la suma de los elementos de la otra lista»!. Y sabiendo que podemos acceder al elemento con L.head, y a la otra lista con L.tail, y considerando que la «otra lista» se irá reduciendo cada vez más hasta llegar a una lista vacía, podemos implementar lo anterior de forma prácticamente literal haciendo uso de una recursión! El siguiente código da muestra de ello:

fun Suma(Lista):
  if(Lista == nil) return 0
  else
    return Lista.head + Suma(Lista.tail)
  end
end

Vale la pena resaltar como llegamos a nuestra solución simplemente siguiendo la estructura recursiva de las listas dada por su definición. Esta es una visión muy importante. Es muestra de cómo los tipos de datos recursivos y las funciones recursivas se ajustan entre ellos muy bien. Ahora, sin embargo, aún tenemos un problema. Hemos encontrado una solución, pero no la mejor. No utiliza la recusividad por cola a la que tanta atención y énfasis le dimos en la sección anterior. Arreglemos eso. Definamos una invariante para esta situación. En este caso, dado que el acumulador debe ir recolectando la suma de cada uno de los encabezados, uno por uno, la otra parte debe ser lo que aún queda sin sumar. Así que bueno, ahí tenemos a nuestra invariante. No fue muy complicado de encontrar la verdad. En este caso, también podríamos decir que fue siguiendo la definición. Bien, entonces tendríamos que:

suma(Lista) =(h1+h2+…+hi)+ suma(Listai.tail) \text{suma(Lista) } = (h_1 + h_2 + \ldots + h_i) + \text{ suma(Lista}_i\text{.tail)}

Es decir, que la suma de los elementos de una lista es igual a la suma de una serie de encabezados más la suma de la cola que le corresponde al último encabezado, donde por cierto, la suma de los encabezados es nuestro acumulador. Así que, en definitiva, vamos llamando recursivamente colas de listas, al mismo tiempo que vamos sumando el encabezado al acumulador, hasta que la cola de una lista sea una lista vacía. El código implementando esta idea se puede ver a continuación:

fun Suma(Lista):
  fun SumaInvariante(Lista, A):
      if Lista == nil then return A
      else
        return SumaInvariante(Lista.tail, A + Lista.head)
      end
  end

  return SumaInvariante(Lista, 0)
end

Con eso ya tenemos una solución eficiente que sigue los principios que aprendimos la sección anterior.

Obteniendo el n-ésimo elemento de una lista

Resolvamos ahora otro problema de un tipo completamente distinto. Escribamos una función que nos retorne el n-ésimo elemento de una lista. Nota que una lista se define como un elemento seguido de una lista, y así en adelante. No contamos con un acceso directo a cada uno de los elementos. El único modo que podemos hacerlo es recorriendo la lista de forma recursiva hasta encontrar al n-ésimo elemento en cuestión, y por lo tanto, esta funcionalidad es bastante útil en realidad. Bien, Escribamos la función. Para ello, podemos releer la descripción que dimos del problema («recorrer de forma recursiva hasta encontrar el n-ésimo elemento») haciendo uso de la definición de lista. Una lista, como ya sabemos, esta compuesta de dos partes (si no está vacía): un encabezado y una cola. En otras palabras, el resultado que buscamos no es otro que el encabezado de la cola de la cola de la cola ... de nuestra lista original. Con esta perspectiva en mente, ya podemos escribir la función que buscamos. Simplemente debemos ir reduciendo el valor de nn, al mismo tiempo que en cada llamada recursiva accedemos a una cola tras otra, hasta que nn sea igual a 1, y entonces el encabezado de esa lista en particular corresponda al elemento que buscamos. En el siguiente código se puede ver una implementación de lo anterior:

fun ObtenerElemento(Lista, n):
  if n == 1 then return Lista.head
  else
    return ObtenerElemento(Lista.tail, n - 1)
  end
end

Nota que en este caso la solución a la que hemos llegado ya utiliza recursividad por cola. Nota además que a diferencia de los problemas anteriores, en este no hay necesidad de un acumulador, pues resulta que no estamos realizando ningun cálculo que signifique ir acumulando un resultado a partir de una colección de elementos. En su lugar, aquí simplemente realizamos tantas iteraciones como sean necesarias hasta dar con una situación en particular (n==1n == 1 en este caso). Podríamos, por lo tanto, preguntarnos ¿Cuál es la invariante en este caso?. Pues resulta, que a diferencia de las fórmulas anteriores, para este tipo de casos podemos definir una invariante con una simple proposición como esta:

El elemento n-ésimo de una lista es igual al encabezado de la (n-1)-ésima cola

Para tomar en cuenta:
¿Qué sucede si se pasa a la función un valor mayor a la cantidad de elementos en la lista como argumento nn?

Ejercicio
Escribe una función (empleando programación invariante) que tome como argumento un entero nn y retorne una lista con todos los factoriales de 1 a nn. (Ej 5 => [1!, 2!, 3!, 4!, 5!])

Ejercicio
La concatenación es una tarea frecuente a la hora de trabajar con varias listas. Esta consiste en construir una nueva lista a partir de la unión de todos los elementos de dos listas distintas. Por ejemplo, al concatenar [1, 2, 3] y [4, 5, 7] se genera la lista [1, 2, 3, 4, 5, 7] (Nota que el orden de los elementos en la lista resultante depende del orden en que se realiza la operación. Si la concatenación fuera entre [4, 5, 7] y [1, 2, 3] el resultado sería [4, 5, 7, 1, 2, 3]). Escribe una función que tome como argumento dos listas, y retorne la concatenación de las dos (considerando la lista del primer argumento, como la primera lista de la operación).

Coincidencia de patrones

Cuando estamos ante una lista, al mismo tiempo estamos ante un patrón. Por supuesto, aunque una lista es una estructura de dato que vive en la memoria, el patrón no existe en la memoria, sino que en nuestra definición abstracta y en nuestra representación visual. En este caso, el patrón es que una lista está compuesta de un encabezado y una cola (a menos que esté vacía). Y es basándose en esta propiedad que muchos lenguajes de programación simbólica incluyen soporte a algo que se conoce como «coincidencia de patrones» (o búsqueda de patrones). Una operación especial con la cual se puede descomponer una estructura de dato en distintas partes según un patrón establecido. Por ejemplo, una lista L, se podría descomponer en su encabezado y cola si indicamos el patrón E|C (el nombre de las variables puede ser arbitrario). O si fuera una lista de tres o más elementos, se podría descomponer en sus dos primeros elementos, y la cola que corresponde al último de ellos, indicando el patrón E1|E2|C. Nota que si la lista estuviera vacía, no coincidiría con ninguno de los patrones dados anteriormente. Bien, esta operación es bastante poderosa la verdad, ya que nos permite pensar en la descomposición de una estructura en las sucesivas llamadas recursivas de una forma mucho más visual. Incluyamósla por tanto a nuestro pseudocódigo. Cada lenguaje puede ofrecer una sintaxis muy diferente para esta operación (aún cuando la lógica es la misma). Para nuestro caso definiremos la siguiente sintaxis para representar esta operación:

case L:
  if Patron1
      //[Instrucciones]
  elseif Patron2
      //[Instrucciones]
  ...
  else
     //[Instrucciones]
end

Donde L representa a la variable vinculada a la estructura, que luego «de alguna manera»(pues hay que recordar que el patrón no existe en la memoria) se va comparando con la forma de distintos patrones hasta encontrar uno (si lo hay) con el que coincida, para proceder a descomponerla en distintas variables locales según lo indicado en el patrón. Nota que la estructura será dividida según el primer patrón con el que coincida (en este sentido, opera igual que un condicional if), y que por lo tanto, hay que tener cuidado al definir nuestros patrones, pues si un patrón cubre todos los casos de un patrón que va en un elseif posterior, este último patrón nunca se ejecutará. En lo ideal, los patrones deberían ser independientes unos de otros, de ese modo aún cuando se cambien de ubicación los patrones, el programa seguirá funcionando correctamente.

Una vez que contamos con una sintaxis para representar la descomposición de una estructura de acuerdo a un patrón, podemos reescribir todas las funciones que iban descomponiendo a las listas dentro de las llamadas recursivas usando esta nueva sintaxis, como se muestra a continuación con la función para sumar todos los elementos de una lista.

fun SumaInvariante(Lista, A):
  case L:
    if E|C
      return sumaInvariante(C, A+E)
    elseif nil:
      return A
  end
end

Nota: Este constructo aunque se incluye en la mayoría de lenguajes simbólicos diseñados en base al paradigma funcional, no forma parte de la definición del estilo funcional.

Nota2: Nota además que este constructo no entrega nada nuevo desde el punto de vista de los problemas que se pueden resolver(pues podemos resolverlos usando recursiones y las propiedades head y tail de la estructura). Sin embargo, entrega una sintaxis con la que podemos pensar la descomposición de estructuras de forma más visual, que puede ser de gran ayuda al momento de reflexionar sobre la solución a un problema. En ese sentido, es una ayuda adicional al programador.

Funciones que crean listas

Hasta ahora ya sabemos cómo escribir funciones que tomen como argumento una lista y luego de una serie de cálculos retorne algún valor de tipo simple como salida. Ahora vayamos más allá. Revisemos la construcción de funciones que retornen un tipo de dato compuesto, en específico, que nos retornen listas. En realidad, no es algo complicado. Sólo hace falta utilizar la recursividad al igual que antes (ó también como ayuda adicional la operación para descomponer la lista según un patrón). Y de hecho, la misma recursividad por cola. Se aclara esto, pues podrías pensar ingenuamente que es imposible, pues la lista se va construyendo después de cada llamada recursiva. Pero, en realidad, como ya demostraremos, la construcción de la lista se realiza antes de cada llamada recursiva, y no después. De modo que la recursividad por cola también es posible. Bien, resolvamos un problema para ejemplificar el procedimiento. Considera el problema de concatenar dos listas. Escribamos una función que realice eso (en muchos lenguajes a esta funcionalidad se la conoce como append()). Esta es la especificación de lo que buscamos conseguir:

l1=[a1,a2,…,an] l_1 = [a_1, a_2, \ldots, a_n]

l2=[b1,b2,…,bk] l_2 = [b_1, b_2, \ldots, b_k]

concatenar(l1,l2)=[a1,a2,…,an,b1,b2,…,bk] \text{concatenar}(l_1, l_2) = [a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_k]

Es decir, una función que cree una nueva lista a partir de la unión de todos los elementos de otras dos listas. Por supuesto, si la primera lista (l1l_1) está vacía, entonces el resultado consta simplemente de los elementos presentes en l2l_2, o dicho de otro modo, el resultado es derechamente una copia de la lista l2l_2. Pero si la primera lista contiene al menos un elemento, entonces lo que se necesita hacer es asignar a la cola del ultimo elemento de la primera lista, la segunda lista en cuestión. ¿Cómo hacemos esto? Bueno, si la primera lista consistiera exactamente de un elemento podriamos escribir simplemente que l1.tail = l2, o usando la sintaxis para la coincidencia de patrones, también podríamos escribir que:

case l1:
  of E|C
    C = l2

¿Pero qué sucedería si la primera lista tuviera dos o más elementos? Bueno, en ese caso, lo que buscamos se podría ver desde la siguiente perspectiva: necesitamos definir una lista cuyo encabezado sea el encabezado de la primera lista y cuya cola sea la concatenación entre la cola de la primera lista y la segunda lista!. De hecho, en esa afirmación tenemos una invariante, pues lo anterior siempre será cierto! La concatenación entre dos listas será una lista formada por el encabezado de la primera como su elemento y la concatencación entre la cola de la primera lista y la segunda. Y esta forma de ver el problema es clave, pues nos muestra como podemos implementar una solución recursiva directamente desde su misma definición tal como lo hemos hecho con muchos otros problemas anteriores. Finalmente, a continuación se muestra una implementación de esa solución:

fun concatenar(l1, l2):
  case l1:
    of nil
      return l2
    elseif E|C
      return E|concatenar(C, l2)
  end
end

Bien, como puedes ver, no era algo complicado. Podríamos decir, que de cierto modo, se pueden implementar funciones que retornen listas prácticamente del mismo modo que implementamos funciones que retornen otros tipos simples. Y esta solución es un gran ejemplo de ello. Aunque aún nos queda un detalle. Esta función parece no emplear recursividad por cola. A simple vista, uno podría decir que necesitamos que primero se resuelva una llamada recursiva determinada para poder realizar una operación E|C. Sin embargo, cuando empezamos a abordar el tema de construir funciones que retornen listas, dijimos que nuestras soluciones podrían ser recursivas por colas, aún cuando no lo parezcan. Y efectivamente es así. Para demostrarlo, eso sí, haremos uso del lenguaje kernel. Traduciremos la función a lenguaje kernel y desde allí verificaremos que efectivamente la recursividad aquí presente es por cola, y que las operaciones se realizan antes de las llamadas recursivas y no después. Bien, aunque para ir a esa demostración, antes necesitamos definir formalmente el lenguaje kernel para el paradigma funcional, así que vamos a ello.

Lenguaje Kernel del paradigma funcional

Como mencionamos al inicio del curso, el lenguaje kernel es el lenguaje nuclear más simple de un paradigma de programación. Y ahora que ya contamos con los conceptos suficientes, es momento de definir al lenguaje kernel del paradigma funcional. Una vez que contemos con esta definición, podremos traducir cualquier programa escrito en paradigma funcional al lenguaje kernel, cosa que nos será de utilidad para analizar al programa desde esa traducción con el objetivo de demostrar y descubrir sus propiedades. De momento, adicionalmente podemos añadir que el lenguaje kernel es, en realidad, la primera parte (de dos) de la semántica formal de un lenguaje de programación. Es decir, que en cierto sentido, compone la mitad de la definición de su semántica!. La segunda parte es la máquina abstracta que introduciremos en lecciones posteriores, pero que en modo resumido es un mecanismo matemático que nos permite mostrar la ejecución de un programa de forma abstracta. Con la primera parte (el lenguaje kernel), en cambio, tenemos una representación significativa de cada una de las piezas con las que se puede programar (pero no - en un sentido formal - que sucede cuando se ejecuta un programa escrito con esas piezas). Dicho esto, ya podemos presentar esta primera parte y obtener algunas ventajas y comprensiones extras a partir de este. He aquí la definición formal de nuestro lenguaje kernel para el paradigma funcional:

<s> :: = skip
        | <s>1 <s>2
        | declare <x>
        | <x>1 = <x>2
        | <x> = <v>
        | if <x> then <s>1 else <s>2 end
        | proc<x> (<x>1 ... <x>n) <s> end
        | <x>(<y>1 ... <y>n)
        | case <x> of <pattern> then <s>1 else <s>2 end


<v> :: = <number> | <list> | ...

<number> ::= <int> | <float>

<list>, <pattern> ::= nil | <x> | <x> '|' <list>

En realidad esta definición no está completa, está casi completa, pero no completa del todo. Faltan incluir ciertas cosas que se verán en la siguiente sección. De cualquier modo, aún incompleta puede parecer bastante confusa, aunque en cierto sentido se parece bastante a la definición gramatical que antes dimos para las listas. La primera parte (dedicada a la definición ), definen las intrucciones posibles en este lenguaje. Así, puedes ver como una instrucción «se define como» un término skip incluido para finalizar un programa, «o» (puedes ver el uso de la barra vertical nuevamente como el operador lógico de disyunción) como una instrucción junto a otra instrucción, o como la declaración de una variable, o como la asignación de una variable a otra variable, o como la asignación de un valor a una variable, o como una instrucción if, o como un procedimiento, o como ... espera!, eso de procedimiento no suena familiar. Bueno, un procedimiento no es más que una función, que toma como argumentos n variables, y retorna (automáticamente) a la última variable de la lista de argumentos cuando finaliza la instrucción asociada a su definición. Aclarado este punto, una instrucción también puede verse como una llamada a un procedimiento, y finalmente como instrucción case (nuestra instrucción para descomponer estructuras). Como conclusión, podríamos decir que una instrucción no es más que todas esas cosas que hemos estado usando para escribir nuestros programas (con la salvedad de la diferencia entre función y procedimiento, claro), pero definidas de manera formal usando nuestra afamada notación EBNF.

Más abajo, como por supuesto nuestro lenguaje no consta sólo de instrucciones, también se entregan definiciones para los valores, los números, las listas, y los patrones. En el caso de los valores «se definen como» un numero o una lista o otros valores que nos faltan por introducir en las lecciones siguientes. En el caso de los numeros estos pueden ser enteros o flotantes, y finalmente, se da una definición para las listas y los patrones similar a la definición que dimos anteriormente, con la diferencia que esta vez la definición da espacio para que un patrón y una lista puedan estar compuestos únicamente de una variable.

Y bueno, esa sería la definición formal de nuestro lenguaje kernel. Una vez que se lee lo anterior, entonces se pierde gran parte, por no decir toda, esa complejidad que sugiere a primera vista. Aun nos quedan cosas que añadir, en especifico, otros valores como estructuras de árbol y grafos. Pero ya con esta definición podemos hacer bastante. Ahora mismo vale la pena notar como en el lenguaje kernel todas las instrucciones se representan a través de un identificador único, y que por lo tanto, es posible visualizar todos los resultados intermedios de un programa, pues cada paso, cada instrucción en el lenguaje kernel se puede separar en torno a estos identificadores. Esto último se considera un principio fundamental que subyace a todas las traducciones a lenguaje kernel que se realizan a partir del código de algún programa funcional. Otra cosa que vale la pena notar es como en el lenguaje kernel todas las funciones se transforman en procedimientos con un argumento extra (el argumento dirigido a representar el valor de retorno), y que todas las expresiones que anidadas (como los bloques al interior de intrucciones if o dentro de una función) se vuelven no anidadas (se pueden definir por fuera mediante su identificador único).

Nota: Es necesario resaltar la diferencia entre la definición de programación funcional y la definición de un lenguaje kernel para programar en estilo funcional. El lenguaje kernel, como el que hemos definido, puede incluir constructos adicionales como case, dirigidos a facilitar la programación. Adicionalmente, qué tipos de valores se soportan en el lenguaje tampoco tiene que ver con la definición de programación funcional en sí, pero sin embargo, en un lenguaje como el kernel, es vital especificar con que valores podemos trabajar y como se definen las estructuras.

Nota2: Nota que la sintaxis especifica para nuestro lenguaje (las palabras claves, que signos usar) es una cuestión aparte. Se podría definir un lenguaje kernel prácticamente igual pero que en lugar de paréntesis para representar la lista de argumentos de un procedimiento, se utilice corchetes, o que en lugar de if la palabra clave sea cuando.

Demostrando la recursividad por cola de la concatenación

Bien, ahora que ya tenemos nuestro lenguaje kernel podemos realizar la demostración que comentábamos. Primero, realicemos la traducción de nuestra función a lenguaje kernel. Esta era nuestra función:

fun concatenar(l1, l2):
  case l1:
    of nil
      return l2
    elseif E|C
      return E|concatenar(C, l2)
  end
end

En primer lugar concatenar() se vuelve un procedimiento con un argumento extra.

proc concatenar(l1, l2, l3)
  ...

Luego, para nuestra instrucción case cada caso tiene un sólo patrón, estando dedicado el primer caso a comprobar si l1 es una lista vacía:

proc concatenar(l1, l2, l3)
  case l1 of nil then ...

Luego, como en nuestro lenguaje kernel no hay un return, sino que un procedimiento retorna automáticamente el valor de l3 una vez que finaliza su instrucción asociada. En este caso, debemos asignar el valor que queremos retornar a l3.

proc concatenar(l1, l2, l3)
  case l1 of nil then l3 = l2

Luego, para incluir el siguiente caso, como no hay un elseif incluido en la definición del lenguaje kernel, debemos incluir otra instrucción case luego de un else del anterior. De hecho, siempre que queramos evaluar múltiples patrones para un caso, siempre tendremos que hacer uso de instrucciones case tras otro else en el lenguaje kernel. Finalmente, escribimos

proc concatenar(l1, l2, l3)
  case l1 of nil then l3 = l2
  else case l1 of E|C then ...

Ahora necesitamos traducir la instrucción return E|concatenar(C, l2). En este caso, hay un resultado intermedio (concatenar(C, l2)) que se puede expresar de forma separada ya que es una instrucción válida en nuestro lenguaje kernel(considerando el argumento adicional). Aparte de eso, dado que l3 es el valor que se retornará automáticamente, debemos asignar a l3 lo que será el valor de retorno, pero claro, no le podemos asignar directamente E|concatenar(C, 12), debemos separar esas instrucciónes de algún modo. Lo que podemos hacer, es definir una lista con una cola indefinida de momento(una lista cuya cola es una variable sin un valor asignado aún), y luego asignar esa lista a l3. Luego de esto, podemos asignar una lista concreta a esa cola indefinida usando una llamada recursiva!. Antes de todo esto, por supuesto, vamos a necesitar declarar una variable que haga el papel de cola. Pero en cuanto a lo que viene después, es tal cual como construimos listas paso por paso al inicio de esta sección. Finalmente, nuestra traducción resultante quedaría así:

proc concatenar(l1, l2, l3)
  case l1 of nil then l3 = l2
  else case l1 of E|C then
          declare t3
          l3 = E|t3
          concatenar(C, l2, t3)
      end
   end
end

Nota que tal como anticipamos, el hecho de que al traducir al lenguaje kernel estemos obligados a separar las instrucciones lo más posible, hace que los pasos intermedios se vuelvan visibles de una forma mucho más clara. Lo mismo sucede con la obligación de representar al retorno como una variable adicional. Al seguir esta norma debemos mostrar en forma clara cuál es la asignación que recibe. Bien, ya con esta versión más limpia de nuestra función para concatenar listas, podemos sin lugar a dudas afirmar que emplea la recursividad por cola. La llamada recursiva es la última acción que realiza la función y la asignación del valor de retorno se realiza antes, como se puede observar. De hecho, además se puede notar como la técnica clave para conseguir esto es la distinción entre la declaración de una variable y la asignación de un valor a la misma (la cual se realiza con la llamada recursiva posterior). Es la posibilidad de contar con variables no enlazadas la que nos permite no tener que regresar a una llamada anterior. Adicionalmente, en ninguno de los casos se contradice la asignación única que define a la programación funcional, pues de hecho, las asignaciones se realizan una sola vez para cada variable, en los distintos momentos que el primer argumento es una lista vacía. Bien, dicho todo lo anterior, finalmente podemos dar por demostrada nuestra afirmación inicial: nuestra función era eficiente pues usa la recursividad por cola. En adición, nos muestra cómo visualizar nuestros programas desde la mirada del lenguaje kernel nos ayuda a ver sus detalles, a notar con mayor claridad sus propiedades. Más allá del formalismo complicado que puede parecer en un inicio, una definición formal siempre puede ser de bastante utilidad.

Ejercicio:
Todos tenemos que tratar con el procesamiento de textos en algun momento y la función "Reemplazar todo" es una aplicación común en muchos de los casos. Con esta función puedes encontrar todas las ocurrencias de una cadena S1, y reemplazarlas con otra cadena S2.

En este ejericio se te pide encontrar una cadena(bajo la forma de una lista) en otra lista. La función debe tomar dos listas L1 y L2 como argumentos, y retornar true si L1 se encuentra en L2. Por ejemplo, encontrarCadena([b, c], [a, b, c, d]) debería retornar true, pues [b, c] está en [a, b, c, d]. Nota además que si los dos argumentos son listas vacías, también debe retornar true.

Adicionalmente, se te pide diseñar otra función de antemano. Una función que verifique si una lista L1 es un «prefijo» de otra lista L2. L1 es prefijo de L2 si L2 comienza con L1. Por ejemplo, si L1 = [a, b, c] y L2 = [a, b, c, d, e, f] entonces efectivamente L1 es prefijo de L2.

Nota: la función prefijo se debe definir fuera de la función para encontrar una cadena en una lista.