El tipo abstracto de datos de los árboles binarios de búsqueda en Haskell

Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los árboles binarios de búsqueda.

Un árbol binario de búsqueda (ABB) (binary search tree en inglés) es un árbol binario tal que el valor de cada nodo es mayor que los valores de su subárbol izquierdo y es menor que los valores de su subárbol derecho y, además, ambos subárboles son árboles binarios de búsqueda. Por ejemplo, al almacenar los valores de [2,3,4,5,6,8,9] en un ABB se puede obtener los siguientes ABB:

El objetivo principal de los ABB es reducir el tiempo de acceso a los valores.

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

  • la signatura del TAD de los árboles binarios de búsqueda;
  • las propiedades del TAD de los árboles binarios de búsqueda;
  • la implementación, en Haskell, de los árboles binarios de búsqueda mediante tipos de datos algebraicos.
  • la comprobación con QuickCheck de sus propiedades.

Read More “El tipo abstracto de datos de los árboles binarios de búsqueda en Haskell”

El tipo abstracto de datos de las tablas en Haskell

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las tablas.

Una tabla (array en inglés y tableau en francés) es una colección de elementos (valores) a los que se accede mediante sus índices.

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

  • la signatura del TAD de las tablas;
  • las propiedades del TAD de las tablas;
  • las implementaciones, en Haskell, de las tablas mediante funciones, listas de asociacón y matrices y
  • la comprobación con QuickCheck de sus propiedades.

Read More “El tipo abstracto de datos de las tablas en Haskell”

Menor elemento común en listas infinitas ordenadas en Haskell y en Clojure

El enunciado del problema 108 de 4Clojure es el siguiente

Given any number of sequences, each sorted from smallest to largest,find the smallest number which appears in each sequence. The sequences may be infinite, so be careful to search lazily.

A partir de dicho problema he elaborado las siguientes relaciones de ejercicios en Haskell y Clojure, intentando mantener la analogía entre sus soluciones.
Read More “Menor elemento común en listas infinitas ordenadas en Haskell y en Clojure”

El problema de la mayor subsucesión creciente en Haskell y en Clojure

A partir del problema 53 de 4Clojure, titulado Longest Increasing Sub-Seq, en el que se pide encontrar la subsucesión creciente más larga de elementos consecutivos de una sucesión dada, he elaborado dos relaciones de ejercicios. Una en Haskell, para la asignatura de Informática de 1º del Grado en Matemáticas, y la otra en Clojure, siguiendo el patrón de la anterior.
Read More “El problema de la mayor subsucesión creciente en Haskell y en Clojure”