PDF de programación - Tema 18: El TAD de las tablas - Informática (2016–17)

Tema 18: El TAD de las tablas

Informática (2016–17)

José A. Alonso Jiménez

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

IM Tema 18: El TAD de las tablas

Tema 18: El TAD de las tablas
1. El tipo predefinido de las tablas (“arrays”)

La clase de los índices de las tablas
El tipo predefinido de las tablas (“arrays”)

2. Especificación del TAD de las tablas
Signatura del TAD de las tablas
Propiedades del TAD de las tablas

3. Implementaciones del TAD de las tablas

Las tablas como funciones
Las tablas como listas de asociación
Las tablas como matrices

4. Comprobación de las implementaciones con QuickCheck

Librerías auxiliares
Generador de tablas
Especificación de las propiedades de las tablas
Comprobación de las propiedades

2 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

La clase de los índices de las tablas

Tema 18: El TAD de las tablas

1. El tipo predefinido de las tablas (“arrays”)

La clase de los índices de las tablas
El tipo predefinido de las tablas (“arrays”)

2. Especificación del TAD de las tablas

3. Implementaciones del TAD de las tablas

4. Comprobación de las implementaciones con QuickCheck

3 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

La clase de los índices de las tablas

La clase de los índices de las tablas

La clase de los índices de las tablas es Ix.
Ix se encuentra en la librería Data.Ix
Información de la clase Ix:

ghci> :info Ix
class (Ord a) => Ix a where

range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int

instance Ix Ordering -- Defined in GHC.Arr
instance Ix Integer -- Defined in GHC.Arr
instance Ix Int -- Defined in GHC.Arr
instance Ix Char -- Defined in GHC.Arr
instance Ix Bool -- Defined in GHC.Arr
instance (Ix a, Ix b) => Ix (a, b)

4 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

La clase de los índices de las tablas

La clase de los índices de las tablas

(range (m,n)) es la lista de los índices desde m hasta n, en el

orden del índice. Por ejemplo,
range (0,4)
range (3,9)
range ('b','f')
range ((0,0),(1,2)) [(0,0),(0,1),(0,2),

[0,1,2,3,4]
[3,4,5,6,7,8,9]
"bcdef"

(1,0),(1,1),(1,2)]
(index (m,n) i) es el ordinal del índice i dentro del rango

(m,n). Por ejemplo,
2
index (3,9) 5
3
index ('b','f') 'e'
index ((0,0),(1,2)) (1,1) 4

5 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

La clase de los índices de las tablas

La clase de los índices de las tablas

(inRange (m,n) i) se verifica si el índice i está dentro del

rango limitado por m y n. Por ejemplo,
True
inRange (0,4) 3
False
inRange (0,4) 7
inRange ((0,0),(1,2)) (1,1) True
inRange ((0,0),(1,2)) (1,5) False

(rangeSize (m,n)) es el número de elementos en el rango

limitado por m y n. Por ejemplo,
7
rangeSize (3,9)
5
rangeSize ('b','f')
rangeSize ((0,0),(1,2)) 6

6 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Tema 18: El TAD de las tablas

1. El tipo predefinido de las tablas (“arrays”)

La clase de los índices de las tablas
El tipo predefinido de las tablas (“arrays”)

2. Especificación del TAD de las tablas

3. Implementaciones del TAD de las tablas

4. Comprobación de las implementaciones con QuickCheck

7 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

La librería de las tablas es Data.Array.
Para usar las tablas hay que escribir al principio del fichero

import Data.Array

Al importar Data.Array también se importa Data.Ix.
(Array i v) es el tipo de las tablas con índice en i y valores en

v.

8 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Creación de tablas

(array (m,n) ivs) es la tabla de índices en el rango limitado
por m y n definida por la lista de asociación ivs (cuyos elementos
son pares de la forma (índice, valor)). Por ejemplo,
ghci> array (1,3) [(3,6),(1,2),(2,4)]
array (1,3) [(1,2),(2,4),(3,6)]
ghci> array (1,3) [(i,2*i) | i <- [1..3]]
array (1,3) [(1,2),(2,4),(3,6)]

9 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Ejemplos de definiciones de tablas

(cuadrados n) es un vector de n+1 elementos tal que su

elemento i–ésimo es i2. Por ejemplo,
ghci> cuadrados 5
array (0,5) [(0,0),(1,1),(2,4),(3,9),(4,16),(5,25)]

cuadrados :: Int -> Array Int Int
cuadrados n = array (0,n) [(i,i^2) | i <- [0..n]]

v es un vector con 4 elementos de tipo carácter. Por ejemplo,

v :: Array Integer Char
v = array (1,4) [(3,'c'),(2,'a'), (1,'f'), (4,'e')]

10 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Ejemplos de definiciones de tablas

m es la matriz con 2 filas y 3 columnas tal que el elemento de la

posición (i,j) es el producto de i por j.

m :: Array (Int, Int) Int
m = array ((1,1),(2,3)) [((i,j),i*j)) | i<-[1..2],j<-[1..3]]

Una tabla está indefinida si algún índice está fuera de rango.

ghci> array (1,4) [(i , i*i) | i <- [1..4]]
array (1,4) [(1,1),(2,4),(3,9),(4,16)]
ghci> array (1,4) [(i , i*i) | i <- [1..5]]
array *** Exception: Error in array index
ghci> array (1,4) [(i , i*i) | i <- [1..3]]
array (1,4) [(1,1),(2,4),(3,9),(4,***
Exception: (Array.!): undefined array element

11 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Descomposición de tablas

(t ! i) es el valor del índice i en la tabla t. Por ejemplo,

ghci> v
array (1,4) [(1,'f'),(2,'a'),(3,'c'),(4,'e')]
ghci> v!3
'c'
ghci> m
array ((1,1),(2,3)) [((1,1),1),((1,2),2),((1,3),3),
((2,1),2),((2,2),4),((2,3),6)]

(bounds t) es el rango de la tabla t. Por ejemplo,

ghci> m!(2,3)
6
bounds m ((1,1),(2,3))
(indices t) es la lista de los índices de la tabla t. Por ejemplo,
indices m [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]

12 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Descomposición de tablas

(elems t) es la lista de los elementos de la tabla t. Por ejemplo,

elems m [1,2,3,2,4,6]

(assocs t) es la lista de asociaciones de la tabla t. Por ejemplo,

ghci> assocs m
[((1,1),1),((1,2),2),((1,3),3),
((2,1),2),((2,2),4),((2,3),6)]

13 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Modificación de tablas

(t // ivs) es la tabla t asignándole a los índices de la lista de

asociación ivs sus correspondientes valores. Por ejemplo,
ghci> m // [((1,1),4), ((2,2),8)]
array ((1,1),(2,3))

[((1,1),4),((1,2),2),((1,3),3),
((2,1),2),((2,2),8),((2,3),6)]

ghci> m
array ((1,1),(2,3))

[((1,1),1),((1,2),2),((1,3),3),
((2,1),2),((2,2),4),((2,3),6)]

14 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Definición de tabla por recursión

(fibs n) es el vector formado por los n primeros términos de la

sucesión de Fibonacci. Por ejemplo,
ghci> fibs 7
array (0,7) [(0,1),(1,1),(2,2),(3,3),

(4,5),(5,8),(6,13),(7,21)]

fibs :: Int -> Array Int Int
fibs n = a where

a = array (0,n)

([(0,1),(1,1)] ++

[(i,a!(i-1)+a!(i-2)) | i <- [2..n]])

15 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Otras funciones de creación de tablas

(listArray (m,n) vs) es la tabla cuyo rango es (m,n) y cuya

lista de valores es vs. Por ejemplo,
ghci> listArray (2,5) "Roma"
array (2,5) [(2,'R'),(3,'o'),(4,'m'),(5,'a')]
ghci> listArray ((1,2),(2,4)) [5..12]
array ((1,2),(2,4)) [((1,2),5),((1,3),6),((1,4),7),

((2,2),8),((2,3),9),((2,4),10)]

16 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Construcción acumulativa de tablas

(accumArray f v (m,n) ivs) es la tabla de rango (m,n) tal
que el valor del índice i se obtiene acumulando la aplicación de
la función f al valor inicial v y a los valores de la lista de
asociación ivs cuyo índice es i. Por ejemplo,
ghci> accumArray (+) 0 (1,3) [(1,4),(2,5),(1,2)]
array (1,3) [(1,6),(2,5),(3,0)]
ghci> accumArray (*) 1 (1,3) [(1,4),(2,5),(1,2)]
array (1,3) [(1,8),(2,5),(3,1)]

17 / 51

IM Tema 18: El TAD de las tablas

El tipo predefinido de las tablas (“arrays”)

El tipo predefinido de las tablas (“arrays”)

Construcción acumulativa de tablas

(histograma r is) es el vector formado contando cuantas

veces aparecen los elementos del rango r en la lista de índices is.
Por ejemplo,
ghci> histograma (0,5) [3,1,4,1,5,4,2,7]
array (0,5) [(0,0),(1,2),(2,1),(3,1),(4,2),(5,1)]

histograma :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
histograma r is =

accumArray (+) 0 r [(i,1) | i <- is, inRange r i]

18 / 51

IM Tema 18: El TAD de las tablas

Especificación del TAD de las tablas
Signatura del TAD de las tablas

Tema 18: El TAD de las tablas

1. El tipo predefinido de las tablas (“arrays”)

2. Especificación del TAD de las tablas
Signatura del TAD de las tablas
Propiedades del TAD de las tablas

3. Implementaciones del TAD de las tablas

4. Comprobación de las implementaciones con QuickCheck

19 / 51

IM Tema 18: El TAD de las tablas

Especificación del TAD de las tablas
Signatura del TAD de las tabl