Menu Close

Categoría: Haskell

Libro de ejercicios resueltos de programación en Haskell (versión del 19 de Diciembre de 2011)

A lo largo del curso iré actualizando un libro de ejercicios resueltos de programación con Haskell con las relaciones de ejercicios del curso de Informática (de 1º del Grado en Matemáticas)

En la versión actual contiene las soluciones de las 9 primeras relaciones y los 2 primeros exámenes:

  1. Definiciones elementales de funciones (1).
  2. Definiciones elementales de funciones (2).
  3. Definiciones por comprensión (1).
  4. Definiciones por comprensión (2).
  5. Definiciones por comprensión (3): El cifrado César.
  6. Definiciones por recursión.
  7. Definiciones por recursión y por comprensión (1).
  8. Definiciones por recursión y por comprensión (2).
  9. Definiciones sobre cadenas, orden superior y plegado.
  10. Exámenes:
    • Examen 1 (26 de Octubre de 2011).
    • Examen 2 (30 de Noviembre de 2011).

El libro se ha ampliado en la versión del 8 de Febrero de 2012.

A un primo de un múltiplo del inverso en Haskell

La semana pasada en el blog Números y algo más se planteó el problema Igual a un múltiplo del “inverso” mas/ menos un primo cuyo enunciado es el siguiente:

El número 21 es el menor número que es igual a un múltiplo de sí mismo dado vuelta (2 x12) más/menos (-3) un primo menor que él:
      21 = 12 x 2 – 3
El siguiente es:
      31 = 13 x 2 + 5
En este caso vemos que el número original también es primo.

La solución 13 = 31 x 6 – 173 no es válida ya que 173 a pesar de ser primo es mayor que 13.

Buscando sólo primos que tengan esta propiedad el siguiente que cumple es el 41 y para el cual tenemos dos soluciones:
      41 = 14 x 2 + 13
      41 = 14 x 5 – 29

El primer primo que tiene cuatro soluciones es el 61:
      61 = 16 x 2 + 29
      61 = 16 x 3 + 13
      61 = 16 x 4 – 3
      61 = 16 x 5 – 19

¿Cuál es el primer primo que tiene cinco soluciones? ¿y el primero que tiene seis?

A partir de dicho problema he escrito en LógicaMente dos relaciones de ejercicios. La primera usando una definición elemental de números primos y la segunda usando la librería Data.Numbers.Primes. Finalmente se compara la eficiencia de ambas definiciones para resolver el problema.

La primera relación es la siguiente

Enumeración de los árboles binarios en Haskell

En esta relación se definen funciones que enumeran el conjunto de los árboles binarios cuyas hojas son números naturales; es decir, funciones biyectivas f: \mathbb{N} \to A y g: A \to \mathbb{N}, donde A es el conjunto de los árboles binarios cuyas hojas son números naturales. La propiedad biyectiva se comprueba mostrando que f \cdot g y g \cdot f son la identidad.

La enumeración se basa en la de los pares de números naturales vista
en el módulo Enumeración del producto cartesiano de los naturales.

Libro de ejercicios resueltos de programación en Haskell (versión del 9 de Noviembre de 2011)

A lo largo del curso iré actualizando un libro de ejercicios resueltos de programación con Haskell con las relaciones de ejercicios del curso de Informática (de 1º del Grado en Matemáticas)

En la versión actual contiene las soluciones de las 6 primeras relaciones que tratan sobre definiciones elementales, definiciones por comprensión y definiciones por recursión.

El tipo abstracto de datos de los grafos en Haskell

Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los grafos. En los próximos, estudiaremos algoritmos sobre grafos basados en este TAD.

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos.

El contenido del este artículo es el siguiente:

  • la signatura del TAD de los grafos;
  • la implementación de los grafos mediante vectores de adyacencia y
  • la implementación de los grafos mediante matrices de adyacencia.

El tipo abstracto de datos de los montículos en Haskell

Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los montículos

Un montículo (heap en inglés) es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo,

        1              1     
       / \            / \    
      /   \          /   \   
     2     6        3     6  
    / \   / \      / \   / \ 
   3   8 9   7    4   2 9   7

el de la izquierda es un montículo, pero el de la derecha no lo es.

El contenido del resto del artículo es el siguiente:

  • la signatura del TAD de los montículos;
  • las propiedades del TAD de los montículos;
  • la implementación, en Haskell, de los montículos mediante tipos de datos algebraicos;
  • la comprobación con QuickCheck de sus propiedades y
  • la implementación de las colas de prioridad mediante montículos.