Haskell – Página 16

La función de Ackermann como prueba de rendimiento

PorJosé A. Alonso 18 agosto 20108 marzo 2013

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
$ A(m,n) = \left\{ \begin{array}{ll} n+1, & \mbox{si\ } m=0, \\ A(m-1,1), & \mbox{si\ } m>0 \mbox{\ y\ } n=0 \\ A(m-1,A(m,n-1)), & \mbox{si\ } m>0 \mbox{\ y\ } n>0 \end{array} \right. $
Read More “La función de Ackermann como prueba de rendimiento”

Números de Lychrel

PorJosé A. Alonso 13 agosto 201030 abril 2015

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”

La función de Takeuchi como banco de prueba para la eficiencia

PorJosé A. Alonso 11 agosto 20109 abril 2014

La función de Takeuchi está definida por
$tak(x,y,z) = \newline \left\{ \begin{array}{ll} y, & si \ x \leq y \\ tak(tak(x-1,y,z), tak(y-1,z,x), tak(z-1,x,y)) & en\ caso\ contrario \end{array} \right.$

En este artículo voy a comparar la la eficiencia de Haskell, Maxima y Lisp escribiendo en los tres la definición recursiva de la función de Takeuchi y calculando $tak(16,6,1)$ .
Read More “La función de Takeuchi como banco de prueba para la eficiencia”

El número de Mersenne 47 en Haskell

PorJosé A. Alonso 9 agosto 20108 marzo 2013

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”

Cruce de listas

PorJosé A. Alonso 5 agosto 20108 marzo 2013

En esta entrada comento las soluciones en Haskell y Maxima de un problema planteado por Adam Majewski en la lista de Maxima en forma de ejercicio para I1M y PD. Además, añadiré soluciones en otros lenguajes conforme las vaya recibiendo.

1. Solución en Haskell

En este ejercico se usarán las siguientes librerías

import Data.List
import Test.QuickCheck

1 2	import Data.List import Test.QuickCheck

Ejercicio 1. Definir la función

cruce :: Eq a => [a] -> [a] -> [[a]]

1	cruce :: Eq a => [a] -> [a] -> [[a]]

tal que (cruce xs ys) es la lista de las listas obtenidas con uniendo las listas de xs sin un elemento con las de ys sin un elemento. Por ejemplo,

*Main> cruce [1,5,3] [2,4]
[[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]
*Main> cruce [1,5,3] [2,4,6]
[[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],
 [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]

*Main> cruce [1,5,3] [2,4]

[[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]

*Main> cruce [1,5,3] [2,4,6]

[[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],

[1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]