Este manual contiene ejemplos de las funciones especificadas en los tipos abstractos de datos (TAD) estudiados en la asignatura de Informática de 1º del Grado en Matemáticas. Los códigos correspondientes se encuentran en esta página.

1 El TAD de las pilas (I1M.Pila)

• vacia es la pila vacía.

λ> vacia
-

• apila x p es la pila obtenida añadiendo x al principio de p.

λ> apila 3 vacia
3|-
λ> apila 2 (apila 3 vacia)
2|3|-
λ> apila 5 (apila 2 (apila 3 vacia))
5|2|3|-
λ> foldr apila vacia [5,2,3] 
5|2|3|-

• cima p es la cima de la pila p.

λ> let p1 = apila 5 (apila 2 (apila 3 vacia))
λ> cima p1
5
λ> p1
5|2|3|-

• desapila p es la pila obtenida suprimiendo la cima de p.

λ> let p1 = apila 5 (apila 2 (apila 3 vacia))
λ> desapila p1
2|3|-
λ> p1
5|2|3|-

• esVacia p se verifica si p es la pila vacía.

λ> let p2 = apila 3 vacia
λ> esVacia p2
False
λ> esVacia (desapila p2)
True

2 El TAD de las colas (I1M.Cola)

• vacia es la cola vacía.

λ> vacia
C []

• inserta x c es la cola obtenida añadiendo x al final de c.

λ> inserta 3 vacia
C [3]
λ> inserta 2 (inserta 3 vacia)
C [3,2]
λ> inserta 5 (inserta 2 (inserta 3 vacia))
C [3,2,5]
λ> foldr inserta vacia [5,2,3]
C [3,2,5]

• primero c es el primero de la cola c.

λ> let c1 = inserta 5 (inserta 2 (inserta 3 vacia))
λ> primero c1
3

• resto c es la cola obtenida eliminando el primero de c.

λ> let c1 = inserta 2 (inserta 5 (inserta 3 vacia))
λ> resto c1
C [2,5]

• esVacia c se verifica si c es la cola vacía.

λ> let c2 = inserta 3 vacia
λ> esVacia c2
False
λ> esVacia (resto c2)
True

3 El TAD de las colas de prioridad (I1M.ColaDePrioridad)

• vacia es la cola de prioridad vacía.

λ> vacia
CP []

• inserta x c añade el elemento x a la cola de prioridad c.

λ> inserta 3 vacia
CP [3]
λ> inserta 2 (inserta 3 vacia)
CP [2,3]
λ> inserta 5 (inserta 2 (inserta 3 vacia))
CP [2,3,5]
λ> foldr inserta vacia [5,2,3]
CP [2,3,5]

• primero c es el primer elemento de la cola de prioridad c.

λ> let cp1 = inserta 5 (inserta 2 (inserta 3 vacia))
λ> primero cp1
2

• resto c es el resto de la cola de prioridad c.

λ> let cp1 = inserta 5 (inserta 2 (inserta 3 vacia))
λ> resto cp1
CP [3,5]

• esVacia c se verifica si la cola de prioridad c es vacía.

λ> let cp2 = inserta 3 vacia
λ> esVacia cp2
False
λ> esVacia (resto cp2)
True

4 El TAD de los conjuntos (I1M.Conjunto)

• vacio es el conjunto vacío.

λ> vacio
{}

• inserta x c es el conjunto obtenido añadiendo el elemento x al conjunto c.

λ> inserta 3 vacio
{3}
λ> inserta 2 (inserta 3 vacio)
{2,3}
λ> inserta 5 (inserta 2 (inserta 3 vacio))
{5,2,3}
λ> foldr inserta vacio [3,2,5]
{3,2,5}
λ> let c1 = foldr inserta vacio [3,2,5]
λ> let c2 = foldr inserta vacio [5,2,3,5,3]
λ> c1 == c2
True

• elimina x c es el conjunto obtenido eliminando el elemento x del conjunto c.

λ> let c1 = inserta 5 (inserta 2 (inserta 3 vacio))
λ> elimina 2 c1
{5,3}
λ> c1
{5,2,3}
λ> elimina 7 c1
{5,2,3}

• pertenece x c se verifica si x pertenece al conjunto c.

λ> let c1 = inserta 5 (inserta 2 (inserta 3 vacio))
λ> pertenece 2 c1
True
λ> pertenece 7 c1
False

• esVacio c se verifica si c es el conjunto vacío.

λ> let c2 = inserta 3 vacio
λ> esVacio c2
False
λ> esVacio (elimina 3 c2)
True

5 El TAD de las tablas (I1M.Tabla)

• tabla ivs es la tabla correspondiente a la lista de asociación ivs (que es una lista de pares formados por los índices y los valores).

λ> tabla [(3,7),(1,5),(2,8)]
Tbl [(3,7),(1,5),(2,8)]
λ> let t1 = tabla [(3,7),(1,5),(2,8)]
λ> let t2 = tabla [(1,5),(3,7),(2,8)]
λ> t1 == t2
True

• valor t i es el valor del índice i en la tabla t.

λ> let t1 = tabla [(3,7),(1,5),(2,8)]
λ> valor t1 2
8
λ> valor t1 3
7

• modifica (i,v) t es la tabla obtenida modificando en la tabla t el valor de i por v.

λ> let t1 = tabla [(3,7),(1,5),(2,8)]
λ> modifica (1,9) t1
Tbl [(3,7),(1,9),(2,8)]

6 El TAD de los árboles binarios de búsqueda (I1M.ArbolBin)

• vacio es el ABB (árbol binario de búsqueda) vacío.

λ> vacio
 -

• inserta v a es el árbol obtenido añadiendo el valor v al ABB a, si no es uno de sus valores.

λ> inserta 3 vacio
 (3 - -)
λ> inserta 2 (inserta 3 vacio)
 (3 (2 - -) -)
λ> inserta 5 (inserta 2 (inserta 3 vacio))
 (3 (2 - -) (5 - -))
λ> inserta 3 (inserta 5 (inserta 2 (inserta 3 vacio)))
 (3 (2 - -) (5 - -))
λ> foldr inserta vacio [5,2,3]
 (3 (2 - -) (5 - -))

• crea vs es el ABB cuyos valores son vs.

λ> crea [5,2,3]
 (3 (2 - -) (5 - -))
λ> crea [3,5,2,3]
 (3 (2 - -) (5 - -))

• elementos a es la lista de los valores de los nodos del ABB en el recorrido inorden.

λ> let a1 = crea [3,5,2,3]
λ> elementos a1
[2,3,5]

• pertenece v a se verifica si v es el valor de algún nodo del ABB a.

λ> let a1 = crea [3,5,2,3]
λ> pertenece 2 a1
True
λ> pertenece 4 a1
False

• elimina v a es el ABB obtenido eliminando el valor v del ABB a.

λ> let a1 = crea [3,5,2,3]
λ> elimina 3 a1
 (5 (2 - -) -)

• menor a es el mínimo valor del ABB a.

λ> let a1 = crea [3,5,2,3]
λ> menor a1
2

7 El TAD de los montículos (I1M.Monticulo)

• vacio es el montículo vacío.

λ> vacio

• inserta x m es el montículo obtenido añadiendo el elemento x al montículo m.

λ> inserta 3 vacio
M 3 1 Vacio Vacio
λ> inserta 2 (inserta 3 vacio)
M 2 1 (M 3 1 Vacio Vacio) Vacio
λ> inserta 5 (inserta 2 (inserta 3 vacio))
M 2 2 (M 3 1 Vacio Vacio) (M 5 1 Vacio Vacio)
λ> foldr inserta vacio [5,2,3]
M 2 2 (M 3 1 Vacio Vacio) (M 5 1 Vacio Vacio)
λ> foldr inserta vacio [2,5,3]
M 2 1 (M 3 1 (M 5 1 Vacio Vacio) Vacio) Vacio
λ> let m1 = foldr inserta vacio [5,2,3]
λ> let m2 = foldr inserta vacio [2,5,3]
λ> m1 == m2
True

• menor m es el menor elemento del montículo m.

λ> let m1 = inserta 5 (inserta 2 (inserta 3 vacio))
λ> menor m1
2

• resto m es el montículo obtenido eliminando el menor elemento del montículo m.

λ> let m1 = inserta 5 (inserta 2 (inserta 3 vacio))
λ> resto m1
M 3 1 (M 5 1 Vacio Vacio) Vacio

• esVacio m se verifica si m es el montículo vacío.

λ> let m2 = inserta 3 vacio
λ> esVacio m2
False
λ> esVacio (resto m2)
True

8 El TAD de los polinomios (I1M.Pol)

• polCero es el polinomio cero.

λ> polCero
0

• consPol n b p es el polinomio .

λ> consPol 0 7 polCero
7
λ> consPol 2 5 (consPol 0 7 polCero)
5*x^2 + 7
λ> consPol 4 6 (consPol 2 5 (consPol 0 7 polCero))
6*x^4 + 5*x^2 + 7
λ> consPol 1 6 (consPol 4 5 (consPol 0 7 polCero))
5*x^4 + 6*x + 7

• grado p es el grado del polinomio p.

λ> let p1 = consPol 1 6 (consPol 4 5 (consPol 0 7 polCero))
λ> grado p1
4

• coefLider p es el coeficiente líder del polinomio p.

λ> let p1 = consPol 1 6 (consPol 4 5 (consPol 0 7 polCero))
λ> coefLider p1
5

• restoPol p es el resto del polinomio p.

λ> let p1 = consPol 1 6 (consPol 4 5 (consPol 0 7 polCero))
λ> restoPol p1
6*x + 7

• esPolCero p se verifica si p es el polinomio cero.

λ> let p2 = consPol 0 7 polCero
λ> esPolCero p2
False
λ> esPolCero (restoPol p2)
True

9 Operaciones con el TAD de polinomios (I1M.PolOperaciones)

• creaTermino n a es el término a*x^n.

λ> creaTermino 2 5
5*x^2

• termLider p es el término líder del polinomio p.

λ> let p = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
λ> termLider p
x^5

• (sumaPol p q) es la suma de los polinomios p y q.

λ> let p1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
λ> let p2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
λ> sumaPol p1 p2
x^5 + 3*x^4 + 4*x + 3

• multPorTerm t p es el producto del término t por el polinomio p.

λ> let t = consPol 1 4 polCero
λ> let p = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
λ> multPorTerm t p
4*x^6 + 20*x^3 + 16*x^2

• multPol p q es el producto de los polinomios p y q.

λ> let p1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
λ> let p2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
λ> multPol p1 p2
3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x

• polUnidad es el polinomio unidad.

λ> polUnidad
1

• valor p c es el valor del polinomio p al sustituir su variable por c.

λ> let p = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
λ> valor p 0
3
λ> valor p 1
1
λ> valor p (-2)
31

• esRaiz c p se verifica si c es una raiz del polinomio p.

λ> let p = consPol 4 6 (consPol 1 2 polCero)
λ> esRaiz 1 p
False
λ> esRaiz 0 p
True

• derivada p es la derivada del polinomio p.

λ> let p = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
λ> derivada p
5*x^4 + 10*x + 4

• resta p q es el polinomio obtenido restándole a p el q.

λ> let p1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
λ> let p2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
> restaPol p1 p2
-1*x^5 + 3*x^4 + -10*x^2 + -4*x + 3

10 El TAD de los grafos (I1M.Grafo)

• creaGrafo d cs as es un grafo (dirigido o no, según el valor de d), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).

λ> creaGrafo ND (1,3) [(1,2,5),(2,3,9),(3,1,7)]
G ND (array (1,3) [(1,[(3,7),(2,5)]),(2,[(1,5),(3,9)]),(3,[(2,9),(1,7)])])
λ> creaGrafo D (1,3) [(1,2,5),(2,3,9),(3,1,7)]
G D (array (1,3) [(1,[(2,5)]),(2,[(3,9)]),(3,[(1,7)])])

• dirigido g se verifica si g es dirigido.

λ> let g1 = creaGrafo ND (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> let g2 = creaGrafo D  (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> dirigido g1
False
λ> dirigido g2
True

• nodos g es la lista de todos los nodos del grafo g.

λ> let g1 = creaGrafo ND (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> let g2 = creaGrafo D  (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> nodos g1
[1,2,3]
λ> nodos g2
[1,2,3]

• aristas g es la lista de las aristas del grafo g.

λ> let g1 = creaGrafo ND (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> let g2 = creaGrafo D  (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> aristas g1
[(1,3,7),(1,2,5),(2,1,5),(2,3,9),(3,2,9),(3,1,7)]
λ> aristas g2
[(1,2,5),(2,3,9),(3,1,7)]

• adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.

λ> let g1 = creaGrafo ND (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> let g2 = creaGrafo D  (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> adyacentes g1 2
[1,3]
λ> adyacentes g2 2
[3]

• aristaEn g a se verifica si a es una arista del grafo g.

λ> let g1 = creaGrafo ND (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> let g2 = creaGrafo D  (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> aristaEn g1 (3,2)
True
λ> aristaEn g2 (3,2)
False

• peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.

λ> let g1 = creaGrafo ND (1,3) [(1,2,5),(2,3,9),(3,1,7)]
λ> peso 3 2 g1
9