Ventajas de la pereza en el problema de los k menores elementos

PorJosé A. Alonso

Una característica singular de Haskell es su carácter perezoso, frente al impaciente de la mayoría de los restantes lenguajes.

Los lenguajes perezosos usan evaluación perezosa; es decir, al evaluar una expresión evalúan sus argumentos sólo cuando los necesita. De manera opuesta, en la evaluación impaciente los argumentos de las expresiones se evalúan antes que las expresiones.

En esta entrada presento un ejercicio para Informática (del Grado de Matemáticas) con objeto de resaltar la ventaja de la evaluación perezosa de Haskell frente a la evaluación impaciente de Maxima. Para ello compararé sus rendimientos al calcular los k primeros elementos de una lista con definiciones semejantes en Haskell y Maxima.
Read More “Ventajas de la pereza en el problema de los k menores elementos”

La función de Ackermann como prueba de rendimiento

PorJosé A. Alonso

En la entrada la función de Takeuchi como banco de prueba para la eficiencia usé la función de Takeuchi para comparar la eficiencia de Haskell (GHC) y Lisp (Clisp y LispWorks). En esta voy a hacer lo mismo con la función de Ackermann.

La función de Ackermann (también llamada función de Ackermann-Péter) es un ejemplo sencillo de función recursiva que no es primitiva recursiva. Definida en 1926 por Wilhelm Ackermann, pero se presenta frecuentemente en la forma propuesta por Rózsa Péter, que es la siguiente
<br /> A(m,n) =<br /> \left\{<br /> \begin{array}{ll}<br /> n+1, & \mbox{si\ } m=0, \\<br /> A(m-1,1), & \mbox{si\ } m>0 \mbox{\ y\ } n=0 \\<br /> A(m-1,A(m,n-1)), & \mbox{si\ } m>0 \mbox{\ y\ } n>0<br /> \end{array}<br /> \right.<br />
Read More “La función de Ackermann como prueba de rendimiento”

Números de Lychrel

PorJosé A. Alonso

Según la Wikipedia, un número de Lychrel es un número natural para el que nunca se obtiene un capicúa mediante el proceso de invertir las cifras y sumar los dos números. Por ejemplo, los siguientes números no son números de Lychrel:

  • 56, ya que en un paso se obtiene un capicúa: 56+65=121.
  • 57, ya que en dos pasos se obtiene un capicúa: 57+75=132, 132+231=363
  • 59, ya que en dos pasos se obtiene un capicúa: 59+95=154, 154+451=605, 605+506=1111
  • 89, ya que en 24 pasos se obtiene un capicúa.

En este ejercicio, pensado para la asignatura de Informática (del Grado de Matemáticas) vamos a buscar con Haskell el primer número de Lychrel.
Read More “Números de Lychrel”

El número de Mersenne 47 en Haskell

PorJosé A. Alonso

En el artículo Cruce de listas abordamos el tema de la simplicidad y eficiencia de las soluciones. En este artículo deseo mostrar la capacidad de Haskell para calcular con grandes números enteros. Para ello, he elegido calcular el último primo de Mersenne descubierto.

Los números primos de Mersenne son los primos de la forma 2^n-1. El último primo de Mersenne descubierto es M_{47}=2^{43112609}-1 que es un número con más de 12 millones de cifras. El descubrimiento lo realizó Edson Smith el 23 de agosto de 2008. Dicho número es el 47 primo de Mersenne conocido.
Read More “El número de Mersenne 47 en Haskell”