Menu Close

Categoría: Haskell

PeH: El triángulo de Pascal en Haskell

El triángulo de Pascal es un triángulo de números

         1
        1 1
       1 2 1
     1  3 3  1
    1 4  6  4 1
   1 5 10 10 5 1
  ...............

construido de la siguiente forma

  • la primera fila está formada por el número 1;
  • las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La construcción del triángulo de Pascal sirve para ilustrar cómo se puede trabajar con listas infinitas en Haskell usando la evaluación perezosa como se muestra en los siguientes ejercicios.

PeH: La conjetura de Gilbreath en Haskell

Se considera el siguiente proceso: (1) escribir los 5 primeros números primos, (2) restar cada dos números consecutivos, escribiendo los resultados en valor absoluto, hasta quedarse con un único número se obtiene la siguiente tabla:

2, 3, 5, 7, 11
1, 2, 2, 4 
1, 0, 2
1, 2 
1

Se observa que todas las filas comienza con el número 1.

Repitiendo el proceso empezando con los 8 primeros números primos se obtiene la siguiente tabla:

2, 3, 5, 7, 11, 13, 17, 19 
1, 2, 2, 4,  2,  4,  2  
1, 0, 2, 2,  2,  2 
1, 2, 0, 0,  0 
1, 2, 0, 0 
1, 2, 0 
1, 2 
1

Se observa que, de nuevo, todas las filas comienza con el número 1.

La conjetura de Gilbreath afirma que si escribimos la sucesión de números primos completa y después construimos las correspondientes sucesiones formadas por el valor absoluto de la resta de cada pareja de números consecutivos, entonces todas esas filas que obtenemos comienzan siempre por 1.

En los siguiente ejercicios comprobaremos experimentalmente con Haskell dicha conjetura. Para la representación, usaremos la simétrica de la que
hemos comentado anteriormente; es decir,

 2
 3, 1
 5, 2, 1
 7, 2, 0, 1
11, 4, 2, 2, 1
13, 2, 2, 0, 2, 1
17, 4, 2, 0, 0, 2, 1
19, 2, 2, 0, 0, 0, 2, 1

en la que la primera columna son los números primos y el elemento de la fila i y columna j (con i, j > 1) es el valor absoluto de la diferencia de los elementos (i,j-1) e (i-1,j-1).

La relación de ejercicios (elaboradad para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) es

PeH: La sucesión de Kolakoski

Dada una sucesión, su contadora es la sucesión de las longitudes de de sus bloque de elementos consecutivos iguales. Por ejemplo, la sucesión contadora de abbaaabbba es 12331; es decir; 1 vez la a, 2 la b, 3 la a, 3 la b y 1 la a.

La sucesión de Kolakoski es una sucesión infinita de los símbolos 1 y 2 que es su propia contadora. Los primeros términos de la sucesión de Kolakoski son 1221121221221… que coincide con su contadora (es decir, 1 vez el 1, 2 veces el 2, 2 veces el 1, …).

En la siguiente relación (para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) se define la sucesión de Kolakoski.

El problema del granjero, la oveja y la col en Haskell

Recientemente, Justin Le ha publicado el artículo Wolf, goat, cabbage: The list MonadPlus & logic problems en el que explica cómo se pueden usar las mónadas para resolver el problema del granjero, el lobo, la oveja y la col. El enunciado de dicho problema es el siguiente

Un granjero fue al mercado y compró un lobo, una oveja y una col. Para volver a su casa tenía que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras. Además, si el lobo se queda solo con la cabra se la come y si la cabra se queda sola con la col se la come.

El reto del granjero era cruzar él mismo y dejar sus compras a la otra orilla del río, dejando cada compra intacta. ¿Cómo lo hizo?

A partir del artículo, he elaborado la siguiente relación de ejercicios (para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell). En ella se incluyen soluciones sin usar mónadas y con mónadas (concretamente, los ejercicios 12, 15 y 17).

La relación de ejercicios y sus soluciones es la siguiente

El desafío matemático “Un número curioso” en Haskell

En El País del día 16 se presentó el desafío matemático Un número curios cuyo enunciado es el siguiente:

El equipo que preparamos los desafíos matemáticos hemos decidido abonarnos durante todo el año a un número de la Lotería. Para elegir ese número, que debe estar comprendido entre el 0 y el 99.999, pusimos como condición que tuviese las cinco cifras distintas y que, además, cumpliese alguna otra propiedad interesante. Finalmente hemos conseguido un número que tiene la siguiente propiedad: si numeramos los meses del año del 1 al 12, en cualquier mes del año ocurre que al restar a nuestro número de lotería el número del mes anterior, el resultado es divisible por el número del mes en el que estemos. Y esto sucede para cada uno de los meses del año.

Es decir, si llamamos L a nuestro número, tenemos por ejemplo que en marzo L-2 es divisible entre 3 y en diciembre L-11 es divisible entre 12.

El reto que os planteamos es que nos digáis a qué número de Lotería estamos abonados.

He elaborado una relación de ejercicios (para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) en la que se generaliza el problema y se resuelve con Haskell de cuatro maneras distintas. La relación de ejercicios es la siguiente

Evaluación en Haskell con tiempo acotado

A veces es interesante evaluar expresiones en Haskell durante un tiempo limitado. Se puede conseguir usando la función timeout de la librería System.Timeout y la evaluate de la Control.Exception.

Vamos a mostrar su uso el siguiente ejemplo. En primer lugar, importamos las funciones

import System.Timeout (timeout)
import Control.Exception (evaluate)

A continuación, definimos la función de Fibonacci

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

y la función acotada tal que (acotada t f x) calcula (f x) durante t microsegundos (1/10^6 segundos) y devuelve (Just (f x)) si encuentra su valor o Nothing en caso contrario.

acotada :: Int -> (a -> b) -> a -> IO (Maybe b)
acotada t f x = timeout t (return $! f x)

Con acotada podemos realizar evaluaciones con tiempo limitado. Por ejemplo,

ghci> acotada 100 fib 5
Just 8
ghci> acotada 100 fib 20
Nothing
ghci> acotada (10^5) fib 20
Just 10946

También se puede acotar con evaluate. Por ejemplo,

ghci> timeout 100 $ evaluate (fib 5)
Just 8
ghci> timeout 100 $ evaluate (fib 20)
Nothing
ghci> timeout (10^5) $ evaluate (fib 20)
Just 10946

Esta entrada se basa en la consulta Haskell time limit on evaluation de StackOverflow.

El problema de Josefo en Haskell

El problema de Josefo hace referencia a Flavio Josefo, un historiador judío que vivió en el siglo I. Según lo que cuenta Josefo, él y cuarenta soldados camaradas fueron capturados por los romanos. Antes que rendirse, decidieron acabar ellos mismos con sus vidas. Para hacerlo, se dispusieron en un círculo y acordaron que irían contando de tres en tres, de forma que cada tercer soldado sería ejecutado por la persona de su izquierda. El último hombre que quedara con vida tendría que suicidarse. Según cuenta la leyenda, Josefo calculó rápidamente cuál sería la posición del último hombre en morir para colocarse allí, y una vez hubieron muerto sus compatriotas, se entregó a los romanos.

El enunciado del problema de Josefo de orden (n,m) es el siguiente: Se tienen n personas entorno a un círculo, ordenadas y numeradas desde la primera a la n-ésima. Empezando por la persona número 1, se saltan m-1 personas y se mata a la m-ésima. A continuación se saltan otras m-1 personas y se ejecuta a la siguiente. El proceso continúa hasta que sólo quede una. El objetivo es, dados n y m, encontrar el lugar inicial en el círculo para sobrevivir.

A continuación muestro una relación de ejercicios (elaborada para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) en la que se presentan distintas soluciones y se compara su eficiencia.

Exámenes de programación funcional con Haskell (2)

He publicado una actualización del libro Exámenes de programación funcional con Haskell (2009-2014) en el que recopilo los exámenes de la asignatura de Informática (de primero del Grado en Matemáticas) desde el curso 2009-10 hasta el actual. El libro contiene 81 exámenes y 539 ejercicios.

Este libro es el complemento de los anteriores:

Sucesiones auto descriptivas en Haskell

En las Olimpiadas de Matemáticas del 2001 se propuso el siguiente problema

Buscar todas las sucesiones finitas (x(0), x(1),…,x(n)) tales que para todo j, 0 ≤ j ≤ n, x(j) es igual al número de veces que aparece j en la sucesión.

Las sucesiones que cumplen la anterior condición se llaman auto descriptivas. Un ejemplo de sucesión auto descriptiva es [5,2,1,0,0,1,0,0,0] ya que

  • el 0 aparece 5 veces,
  • el 1 aparece 2 veces,
  • el 2 aparece 1 vez,
  • el 3 aparece 0 veces,
  • el 4 aparece 0 veces,
  • el 5 aparece 1 vez,
  • el 6 aparece 0 veces,
  • el 7 aparece 0 veces y
  • el 8 aparece 0 veces.

En la siguiente relación de ejercicios, elaborada para la asignatura de Informática (de 1º del Grado en Matemáticas) y para la siguiente versión del libro Piensa en Haskell, se resuelve el problema con Haskell.