Estructuras de Datos y Algoritmos en Programación Funcional con SML

Implementación de Estructuras de Datos en SML

A continuación se presentan diversas implementaciones de estructuras de datos fundamentales utilizando el paradigma de programación funcional, específicamente en Standard ML (SML).

1. Estructura de Datos: Lista

Definición de un tipo de dato recursivo para una lista de enteros y sus operaciones básicas:

datatype lista = vacio
| nodo of int * lista;

load "Int";

fun mostrar (vacio) = ""
| mostrar (nodo (a, b)) = Int.toString(a) ^ "," ^ mostrar (b);

fun agregar (vacio, i) = nodo (i, vacio)
| agregar (nodo(d, vacio), i) = nodo (d, nodo(i, vacio))
| agregar (nodo(d, m), i) = nodo(d, agregar(m, i)); // m es un nodo (nodo(x, vacio))

fun buscar (vacio, i) = false
| buscar (nodo(a, b), i) = if a = i then true else buscar (b, i);

fun eliminar (n, vacio) = vacio
| eliminar (n, nodo(a, b)) = if n = a then b else agregar(eliminar(n, b), a);

2. Estructura de Datos: Árbol Binario

Operaciones para la gestión de árboles binarios de búsqueda:

fun agregar vacio j = (nodo(vacio, j, vacio))
| agregar (nodo(izq, d, der)) j = if d = j then (nodo(izq, d, der)) else if d

fun buscar vacio j = false
| buscar (nodo(izq, d, der)) j = if d = j then true else if d

fun mostrar vacio = ""
| mostrar (nodo(izq, d, der)) = Int.toString(d) ^ mostrar(izq) ^ mostrar(der);

fun listar vacio = []
| listar (node(izq, d, der)) = [d] @ listar(izq) @ listar(der);

fun busca_lista(x, []) = false
| busca_lista(x, y::ys) = if x = y then true else busca_lista(x, ys);

fun comparar(vacio, vacio) = true
| comparar(x::xs, ys) = if buscar_lista(x, ys) then comparar(xs, ys) else false;

3. Estructura de Datos: Tabla Hash

Implementación de una tabla hash utilizando listas de pares clave-valor:

datatype tabla = vacia 
| hash of (int * string) list;

// Ejemplo de instancia: [(3, "asd"), (4, "lcdtmAB")];

fun buscar (vacia, x) = false
| buscar(hash[], x) = false
| buscar(hash((r, t)::y), z) = if r = z then true else buscar(hash y, z);

fun agregar(vacia, (a, b)) = hash[(a, b)]
| agregar(hash[], (a, b)) = hash[(a, b)]
| agregar(hash x, (a, b)) = if buscar(hash x, a) then hash x else hash((a, b)::x);

fun eliminar (vacia, x) = vacia
| eliminar(hash[], x) = vacia
| eliminar(hash((w, h)::z), x) = if w = x then hash z else agregar(eliminar(hash z, x), (w, h));

4. Variante de Árbol Binario

Definición alternativa de un árbol con nodos y hojas diferenciadas:

datatype arbol = vacio
| hoja of int
| nodo of arbol * arbol;

// Ejemplos de construcción:
vacio;
hoja(5);
nodo(hoja(5), hoja(7));
nodo(nodo(hoja(5), hoja(7)), hoja(8));

fun contar

fun listar (vacio) = []
| listar(hoja(x)) = [x] 
| listar(nodo(y, z)) = listar(y) @ listar(z);

fun contar([]) = 0
| contar (h::t) = contar(t) + 1;

5. Cola de Prioridades

Implementación de una cola de prioridades basada en una lista de tuplas:

datatype cola = vacio
| work of (int * int) list;

fun agregar ((a, b), vacio) = work[(a, b)]
| agregar((a, b), work[]) = work[(a, b)]
| agregar((a, b), work((z, x)::y)) = if a < z then work((a, b)::(z, x)::y) else agregar ((a, b), work