-- I1M 2021-22: Relación 18
-- Arrays: vectores y matrices
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================
-- ============================================================================
-- Librerías auxiliares
-- ============================================================================
import Data.Array
-- ============================================================================
-- Vectores y matrices
-- ============================================================================
-- Los vectores son tablas cuyos índices son números naturales.
type Vector a = Array Int a
-- Las matrices son tablas cuyos índices son pares de números naturales.
type Matriz a = Array (Int,Int) a
-- ----------------------------------------------------------------------------
-- Ejercicio 1. Definir la función
-- listaVector :: [a] -> Vector a
-- tal que '(listaVector xs)' es el vector cuyos elementos son los de la lista
-- 'xs', en el orden en que aparecen. Por ejemplo,
-- listaVector [3,2,5] == array (1,3) [(1,3),(2,2),(3,5)]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
listaVector :: [a] -> Vector a
listaVector xs = listArray (1,(length xs)) xs
-- ----------------------------------------------------------------------------
-- Ejercicio 2. Definir la función
-- listaMatriz :: [[a]] -> Matriz a
-- tal que '(listaMatriz xss)' es la matriz cuyas filas son los elementos de
-- 'xss', en el orden en que aparecen. Por ejemplo,
-- listaMatriz [[1,3,5],[2,4,7]] ==
-- array ((1,1),(2,3)) [((1,1),1),((1,2),3),((1,3),5),
-- ((2,1),2),((2,2),4),((2,3),7)]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
listaMatriz :: [[a]] -> Matriz a
listaMatriz (xs:xss) = listArray ((1,1),((length (xs:xss)),(length xs))) (concat (xs:xss))
-- ----------------------------------------------------------------------------
-- Ejercicio 3. Definir la función
-- numFilas :: Matriz a -> Int
-- tal que '(numFilas m)' es el número de filas de la matriz 'm'. Por ejemplo,
-- numFilas (listaMatriz [[1,3,5],[2,4,7]]) == 2
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
numFilas :: Matriz a -> Int
numFilas m = fst(snd(bounds m))
-- ----------------------------------------------------------------------------
-- Ejercicio 4. Definir la función
-- numColumnas :: Matriz a -> Int
-- tal que '(numColumnas m)' es el número de columnas de la matriz 'm'. Por
-- ejemplo,
-- numColumnas (listaMatriz [[1,3,5],[2,4,7]]) == 3
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
numColumnas :: Matriz a -> Int
numColumnas m = snd(snd(bounds m))
-- ----------------------------------------------------------------------------
-- Ejercicio 5. Definir la función
-- dimension :: Matriz a -> (Int,Int)
-- tal que '(dimension m)' es el par formado por el número de filas y el número
-- de columnas de la matriz 'm'. Por ejemplo,
-- dimension (listaMatriz [[1,3,5],[2,4,7]]) == (2,3)
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
dimension :: Matriz a -> (Int,Int)
dimension m = snd(bounds m)
-- ----------------------------------------------------------------------------
-- Ejercicio 6. Definir la función
-- vectorLista :: Vector a -> [a]
-- tal que '(vectorLista v)' es la lista de los elementos del vector 'v'. Por
-- ejemplo,
-- vectorLista (array (1,3) [(1,3),(2,2),(3,5)]) == [3,2,5]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
vectorLista :: Vector a -> [a]
vectorLista x = elems x
-- ----------------------------------------------------------------------------
-- Ejercicio 7. Definir la función
-- separa :: Int -> [a] -> [[a]]
-- tal que '(separa n xs)' es la lista obtenida separando los elementos de la
-- list 'xs' en grupos de 'n' elementos (salvo el último que puede tener menos
-- de 'n' elementos). Por ejemplo,
-- separa 3 [1..11] == [[1,2,3],[4,5,6],[7,8,9],[10,11]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
separa :: Int -> [a] -> [[a]]
separa _ [] = []
separa n xs = [take n xs] ++ separa n (drop n xs)
-- ----------------------------------------------------------------------------
-- Ejercicio 8. Definir la función
-- matrizLista :: Matriz a -> [[a]]
-- tal que '(matrizLista m)' es la lista de las filas de la matriz 'm'. Por
-- ejemplo,
-- matrizLista (array ((1,1),(2,3)) [((1,1),5),((1,2),1),((1,3),0),
-- ((2,1),3),((2,2),2),((2,3),6)]) ==
-- [[5,1,0],[3,2,6]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
matrizLista :: Matriz a -> [[a]]
matrizLista p = separa (numColumnas p) (elems p)
-- ----------------------------------------------------------------------------
-- Ejercicio 9. Definir la función
-- sumaMatrices :: Num a => Matriz a -> Matriz a -> Matriz a
-- tal que '(sumaMatrices m1 m2)' es la matriz suma de las matrices 'm1' y
-- 'm2'. Por ejemplo,
-- matrizLista (sumaMatrices (listaMatriz [[5,1,0],[3,2,6]])
-- (listaMatriz [[4,6,3],[1,5,2]])) ==
-- [[9,7,3],[4,7,8]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
sumaMatrices :: Num a => Matriz a -> Matriz a -> Matriz a
sumaMatrices p q = if dimension p /= dimension q then error "Las matrices no tiene la mismadimesion"
else accumArray (+) 0 ((1,1),dimension p) (assocs p ++ assocs q)
-- ----------------------------------------------------------------------------
-- Ejercicio 10. Definir la función
-- filaMat :: Int -> Matriz a -> Vector a
-- tal que '(filaMat i m)' es el vector correspondiente a la 'i'-ésima fila de
-- la matriz 'm'. Por ejemplo,
-- vectorLista (filaMat 2 (listaMatriz [[5,1,0],[3,2,6],[4,5,7]])) ==
-- [3,2,6]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
filaMat :: Int -> Matriz a -> Vector a
filaMat n p = array (1, numColumnas p) [(j,s) | ((i,j),s) <- assocs p, i == n]
-- ----------------------------------------------------------------------------
-- Ejercicio 11. Definir la función
-- columnaMat :: Int -> Matriz a -> Vector a
-- tal que '(columnaMat j m)' es el vector correspondiente a la 'j'-ésima
-- columna de la matriz 'm'. Por ejemplo,
-- vectorLista (columnaMat 2 (listaMatriz [[5,1,0],[3,2,6],[4,5,7]])) ==
-- [1,2,5]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
columnaMat :: Int -> Matriz a -> Vector a
columnaMat n p = array (1, numFilas p) [(i,s) | ((i,j),s) <- assocs p, j == n]
-- ----------------------------------------------------------------------------
-- Ejercicio 12. Definir la función
-- prodEscalar :: Num a => Vector a -> Vector a -> a
-- tal que '(prodEscalar v1 v2)' es el producto escalar de los vectores 'v1' y
-- 'v2'. Por ejemplo,
-- prodEscalar (listaVector [3,1,10]) (listaVector [3,1,10]) == 110
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
prodEscalar :: Num a => Vector a -> Vector a -> a
prodEscalar v1 v2 = sum (zipWith (*) (elems v1) (elems v2))
-- ----------------------------------------------------------------------------
-- Ejercicio 13. Definir la función
-- prodEscalarMatriz :: Num a => a -> Matriz a -> Matriz a
-- tal que '(prodEscalarMatriz x m)' es la matriz resultado de multiplicar la
-- matriz 'm' por el número 'x'. Por ejemplo,
-- matrizLista (prodEscalarMatriz 2 (listaMatriz [[3,1],[2,4]])) ==
-- [[6,2],[4,8]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
prodEscalarMatriz :: Num a => a -> Matriz a -> Matriz a
prodEscalarMatriz x m = accumArray (*) x (bounds m) (assocs m)
-- ----------------------------------------------------------------------------
-- Ejercicio 14. Definir la función
-- prodMatrices :: Num a => Matriz a -> Matriz a -> Matriz a
-- tal que '(prodMatrices m1 m2)' es la matriz producto de las matrices 'm1' y
-- 'm2'. Por ejemplo,
-- matrizLista (prodMatrices (listaMatriz [[3,1],[2,4]])
-- (listaMatriz [[3,1],[2,4]])) ==
-- [[11,7],[14,18]]
-- matrizLista (prodMatrices (listaMatriz [[3,1],[2,4]])
-- (listaMatriz [[7],[5]])) ==
-- [[26],[34]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
prodMatrices :: Num a => Matriz a -> Matriz a -> Matriz a
prodMatrices p q = if numColumnas p /= numFilas q then error "Las matrices no son compatibles para el producto de matrices"
else listArray ((1,1),(numFilas p, numColumnas q)) [prodEscalar (filaMat y p) (columnaMat x q) | y <- [1..(numFilas p)], x <- [1..(numColumnas q)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 15. Definir la función
-- potencia :: Num a => Matriz a -> Int -> Matriz a
-- tal que '(potencia m n)' es la potencia 'n'-ésima de la matriz cuadrada 'm'.
-- Por ejemplo,
-- matrizLista (potencia (listaMatriz [[1,1],[1,0]]) 2) == [[2,1],[1,1]]
-- matrizLista (potencia (listaMatriz [[1,1],[1,0]]) 3) == [[3,2],[2,1]]
-- matrizLista (potencia (listaMatriz [[1,1],[1,0]]) 4) == [[5,3],[3,2]]
-- ¿Qué relación hay entre las potencias de la matriz de los ejemplos y la
-- sucesión de Fibonacci?
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
potencia :: Num a => Matriz a -> Int -> Matriz a
potencia m n = aux m m n
where aux m1 m2 n | n == 1 = m1
| otherwise = aux (prodMatrices m1 m2) m2 (n-1)
-- ----------------------------------------------------------------------------
-- Ejercicio 16. Definir la función
-- traspuesta :: Matriz a -> Matriz a
-- tal que '(traspuesta m)' es la matriz traspuesta de la matriz 'm'. Por
-- ejemplo,
-- matrizLista (traspuesta (listaMatriz [[5,1,0],[3,2,6]])) ==
-- [[5,3],[1,2],[0,6]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
traspuesta :: Matriz a -> Matriz a
traspuesta m = array ((1,1),(numColumnas m, numFilas m)) [((j,i),n) | ((i,j),n) <- (assocs m)]
-- ----------------------------------------------------------------------------
-- Ejercicio 17. Definir la función
-- submatriz :: Int -> Int -> Matriz a -> Matriz a
-- tal que '(submatriz f c m)' es la matriz obtenida a partir de la matriz 'm'
-- eliminando la fila 'f' y la columna 'c'. Por ejemplo,
-- matrizLista (submatriz 2 3 (listaMatriz [[5,1,0],[3,2,6],[4,6,9]])) ==
-- [[5,1],[4,6]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
submatriz :: Int -> Int -> Matriz a -> Matriz a
submatriz f c m = listArray ((1,1),((numColumnas m) -1 , (numFilas m) -1)) [n | ((i,j),n) <- (assocs m), i /= f, j /= c]
-- ----------------------------------------------------------------------------
-- Ejercicio 18. Definir la función
-- determinante :: Num a => Matriz a -> a
-- tal que '(determinante m)' es el determinante de la matriz 'm' calculado por
-- adjuntos. Por ejemplo,
-- determinante (listaMatriz [[2,0,0],[0,3,0],[0,0,1]]) == 6
-- determinante (listaMatriz [[1,2,3],[4,5,6],[7,8,9]]) == 0
-- determinante (listaMatriz [[2,1,5],[1,2,3],[5,4,2]]) == -33
-- ----------------------------------------------------------------------------
-- El determinante se calcula multiplicando los elementos de su primera fila
-- por el determinante de la submatriz resultante de quitar la primera fila y
-- la columna de cada elemento. Después se suman todos alternando signos.
-- Álvaro Galisteo:
determinante :: Num a => Matriz a -> a
determinante m | numFilas m == 1 && numColumnas m == 1 = head (elems m)
| otherwise = sum [(-1)^(1+j) * (m!(1,j)) * determinante (submatriz 1 j m) | j <- [1..(numColumnas m)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 19. Definir la función
-- esCuadrada :: Matriz a -> Bool
-- tal que '(esCuadrada m)' se verifica si la matriz 'm' es cuadrada. Por
-- ejemplo,
-- esCuadrada (listaMatriz [[5,1,0],[3,2,6]]) == False
-- esCuadrada (listaMatriz [[5,1],[3,2]]) == True
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
esCuadrada :: Matriz a -> Bool
esCuadrada m = numColumnas m == numFilas m
-- ----------------------------------------------------------------------------
-- Ejercicio 20. Definir la función
-- esSimetrica :: Eq a => Matriz a -> Bool
-- tal que '(esSimetrica m)' se verifica si la matriz 'm' es simétrica. Por
-- ejemplo,
-- esSimetrica (listaMatriz [[5,1,3],[1,4,7],[3,7,2]]) == True
-- esSimetrica (listaMatriz [[5,1,3],[1,4,7],[3,4,2]]) == False
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
esSimetrica :: Eq a => Matriz a -> Bool
esSimetrica m = m == traspuesta m
-- ----------------------------------------------------------------------------
-- Ejercicio 21. Definir la función
-- esTriangularSuperior :: (Num a, Eq a) => Matriz a -> Bool
-- tal que '(esTriangularSuperior m)' se verifica si 'm' es una matriz
-- triangular superior. Por ejemplo,
-- esTriangularSuperior (listaMatriz [[1,2,1],[0,4,7],[0,0,5]]) == True
-- esTriangularSuperior (listaMatriz [[1,2,3],[1,2,4],[1,2,5]]) == False
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
esTriangularSuperior :: (Num a, Eq a) => Matriz a -> Bool
esTriangularSuperior m = and [(m!(i,j)) == 0 | i <- [2..(numFilas m)], j <- [1..(i-1)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 22. Definir la función
-- esTriangularInferior :: (Num a, Eq a) => Matriz a -> Bool
-- tal que '(esTriangularInferior m)' se verifica si 'm' es una matriz
-- triangular inferior. Por ejemplo,
-- esTriangularInferior (listaMatriz [[1,0,0],[2,4,0],[1,2,5]]) == True
-- esTriangularInferior (listaMatriz [[1,2,3],[1,2,4],[1,2,5]]) == False
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
esTriangularInferior :: (Num a, Eq a) => Matriz a -> Bool
esTriangularInferior m = and [(m!(i,j)) == 0 | i <- [1..(numFilas m - 1 )], j <- [(i+1)..(numColumnas m)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 23. Definir la función
-- esEscalar :: (Num a, Eq a) => Matriz a -> Bool
-- tal que '(esEscalar m)' se verifica si 'm' es una matriz escalar; es decir,
-- es una matriz diagonal con todos sus elementos iguales. Por ejemplo,
-- esEscalar (listaMatriz [[5,0,0],[0,5,0],[0,0,5]]) == True
-- esEscalar (listaMatriz [[5,0,0],[1,5,0],[0,0,5]]) == False
-- esEscalar (listaMatriz [[5,0,0],[0,6,0],[0,0,5]]) == False
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
esEscalar :: (Num a, Eq a) => Matriz a -> Bool
esEscalar m = esTriangularSuperior m && esTriangularInferior m && and [(m!(i,i)) == (m!(1,1)) | i <- [1..(numFilas m)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 24. Definir la función
-- diagonalPrincipal :: Matriz a -> Vector a
-- tal que '(diagonalPrincipal m)' es el vector que contiene los elementos de
-- la diagonal principal de la matriz 'm'. Por ejemplo,
-- vectorLista (diagonalPrincipal (listaMatriz [[5,1,0],[3,2,6]])) ==
-- [5,2]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
diagonalPrincipal :: Matriz a -> Vector a
diagonalPrincipal m = listArray (1,n) [(m!(i,i)) | i <- [1..n]]
where n = if numFilas m < numColumnas m then numFilas m else numColumnas m
-- ----------------------------------------------------------------------------
-- Ejercicio 25. Definir la función
-- diagonalSecundaria :: Matriz a -> Vector a
-- tal que '(diagonalSecundaria m)' es el vector que contiene los elementos de
-- la diagonal secundaria de la matriz cuadrada 'm'. Por ejemplo,
-- vectorLista (diagonalSecundaria (listaMatriz [[5,1],[3,2]])) ==
-- [1,3]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
diagonalSecundaria :: Matriz a -> Vector a
diagonalSecundaria m = listArray (1,n) [(m!(i,(numColumnas m - i + 1))) | i <- [1..n]]
where n = if numFilas m < numColumnas m then numFilas m else numColumnas m
-- ----------------------------------------------------------------------------
-- Ejercicio 26. Definir la función
-- antidiagonal :: (Num a, Eq a) => Matriz a -> Bool
-- tal que '(antidiagonal m)' se verifica si 'm' es una matriz cuadrada y todos
-- sus elementos que no están en la diagonal secundaria son nulos. Por ejemplo,
-- antidiagonal (listaMatriz [[0,0,4],[0,6,0],[0,0,0]]) == True
-- antidiagonal (listaMatriz [[7,0,4],[0,6,0],[0,0,5]]) == False
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
antidiagonal :: (Num a, Eq a) => Matriz a -> Bool
antidiagonal m = esCuadrada m && and [(m!(i,j)) == 0 | i <- [1..(numFilas m - 1)], j <- [1..(numColumnas m -i)]] && and [(m!(i,j)) == 0 | i <- [2..(numFilas m)], j <- [(numColumnas m -i+2)..(numColumnas m)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 27. Definir la función
-- posiciones :: Eq a => a -> Matriz a -> [(Int,Int)]
-- tal que '(posiciones x m)' es la lista de las posiciones de la matriz 'm'
-- cuyo valor es 'x'. Por ejemplo,
-- posiciones 2 (listaMatriz [[1,2,3],[2,4,6]]) == [(1,2),(2,1)]
-- posiciones 6 (listaMatriz [[1,2,3],[2,4,6]]) == [(2,3)]
-- posiciones 7 (listaMatriz [[1,2,3],[2,4,6]]) == []
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
posiciones :: Eq a => a -> Matriz a -> [(Int,Int)]
posiciones x m | notElem x (elems m) = []
| otherwise = [(i,j) | ((i,j),n) <- (assocs m), n == x]
-- ----------------------------------------------------------------------------
-- Ejercicio 28. Definir la función
-- indicesMaximo :: (Num a, Ord a) => Matriz a -> [(Int,Int)]
-- tal que '(indicesMaximo m)' es la lista de las posiciones en las que se
-- encuentra el elemento máximo de la matriz 'm'. Por ejemplo,
-- indicesMaximo (listaMatriz [[3,2],[3,1]]) == [(1,1),(2,1)]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
indicesMaximo :: (Num a, Ord a) => Matriz a -> [(Int,Int)]
indicesMaximo m = posiciones (maximum (elems m)) m
-- ----------------------------------------------------------------------------
-- Ejercicio 29. Una matriz tridiagonal es aquella en la que sólo hay elementos
-- distintos de 0 en la diagonal principal o en las diagonales por encima y por
-- debajo de la diagonal principal. Por ejemplo,
-- ( 1 2 0 0 0 0 )
-- ( 3 4 5 0 0 0 )
-- ( 0 6 7 8 0 0 )
-- ( 0 0 9 1 2 0 )
-- ( 0 0 0 3 4 5 )
-- ( 0 0 0 0 6 7 )
--
-- Definir la función
-- creaTridiagonal :: Int -> Matriz Int
-- tal que '(creaTridiagonal n)' es la siguiente matriz tridiagonal cuadrada
-- con 'n' filas y 'n' columnas:
-- ( 1 1 0 0 0 0 ... 0 0 )
-- ( 1 2 2 0 0 0 ... 0 0 )
-- ( 0 2 3 3 0 0 ... 0 0 )
-- ( 0 0 3 4 4 0 ... 0 0 )
-- ( 0 0 0 4 5 5 ... 0 0 )
-- ( 0 0 0 0 5 6 ... 0 0 )
-- ( ....................... )
-- ( 0 0 0 0 0 0 ... n-1 n-1 )
-- ( 0 0 0 0 0 0 ... n-1 n )
-- Por ejemplo,
-- matrizLista (creaTridiagonal 4) ==
-- [[1,1,0,0],[1,2,2,0],[0,2,3,3],[0,0,3,4]]
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
creaTridiagonal :: Int -> Matriz Int
creaTridiagonal n = listArray ((1,1),(n,n)) ([1,1]++(replicate (n-2) 0) ++ (concat [replicate (m-2) 0 ++ [m-1,m,m] ++ replicate (n - m - 1) 0 | m <- [2..(n-1)]]) ++ (replicate (n-2) 0)++[n-1,n])
-- ----------------------------------------------------------------------------
-- Ejercicio 30. Definir la función
-- esTridiagonal :: (Num a, Eq a) => Matriz a -> Bool
-- tal que '(esTridiagonal m)' se verifica si la matriz 'm' es tridiagonal. Por
-- ejemplo,
-- esTridiagonal (creaTridiagonal 5) == True
-- esTridiagonal (listArray ((1,1),(3,3)) [1..9]) == False
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
esTridiagonal :: (Num a, Eq a) => Matriz a -> Bool
esTridiagonal m = all (== 0) [m!(i,j) | i <- [1..x], j <- [1..y], abs (i-j) >= 2]
where (x,y) = snd (bounds m)
-- ============================================================================
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)