Relación 18 Sol

-- 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)]
-- ----------------------------------------------------------------------------

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)]
-- ----------------------------------------------------------------------------

listaMatriz :: [[a]] -> Matriz a
listaMatriz xss = listArray ((1,1),(length xss,length (xss !! 0))) (concat 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
-- ----------------------------------------------------------------------------

numFilas :: Matriz a -> Int
numFilas = fst . snd . bounds

-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------

numColumnas :: Matriz a -> Int
numColumnas = snd . snd . bounds

-- ----------------------------------------------------------------------------
-- 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)
-- ----------------------------------------------------------------------------

dimension :: Matriz a -> (Int,Int)
dimension = snd . bounds

-- ----------------------------------------------------------------------------
-- 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]
-- ----------------------------------------------------------------------------

vectorLista :: Vector a -> [a]
vectorLista t = elems t

-- ----------------------------------------------------------------------------
-- 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]]
-- ----------------------------------------------------------------------------

separa :: Int -> [a] -> [[a]]
separa n [] = []
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]]
-- ----------------------------------------------------------------------------

matrizLista :: Matriz a -> [[a]]
matrizLista t = separa (numColumnas t) (elems t)

-- ----------------------------------------------------------------------------
-- 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]]
-- ----------------------------------------------------------------------------

sumaMatrices :: Num a => Matriz a -> Matriz a -> Matriz a
sumaMatrices a b | dimension a /= dimension b = error "Las matrices deben tener la misma dimension"
                 | otherwise = listArray ((1,1),dimension a) [ea + eb | (ea,eb) <- zip (elems a) (elems b)]

-- ----------------------------------------------------------------------------
-- 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]
-- ----------------------------------------------------------------------------

filaMat :: Int -> Matriz a -> Vector a
filaMat i m = listArray (1,numColumnas m) (map snd (filter (\ p -> (fst (fst p)) == i) (assocs m)))

filaMat' :: Int -> Matriz a -> Vector a
filaMat' i m = listArray (1,numColumnas m) (map snd (filter ((==i) . fst . fst) (assocs m)))

-- Mi preferida:
filaMat'' :: Int -> Matriz a -> Vector a
filaMat'' i m = listArray (1,c) [m ! (i,j) | j <- [1..c]]
  where c = numColumnas m

-- ----------------------------------------------------------------------------
-- 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]
-- ----------------------------------------------------------------------------

columnaMat :: Int -> Matriz a -> Vector a
columnaMat j m = listArray (1,f) [m ! (i,j) | i <- [1..f]]
  where f = numFilas m

-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------

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]]
-- ----------------------------------------------------------------------------

prodEscalarMatriz :: Num a => a -> Matriz a -> Matriz a
prodEscalarMatriz x m = listArray ((1,1),(dimension m)) (map (*x) (elems 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]]
-- ----------------------------------------------------------------------------

prodMatrices :: Num a => Matriz a -> Matriz a -> Matriz a
prodMatrices a b | ca /= fb = error "Las dimensiones no son compatibles"
                 | otherwise = listArray ((1,1),(fa,cb)) [prodEscalar (filaMat i a) (columnaMat j b)
                                                         | i <- [1..fa], j <- [1..cb]]
  where ca = numColumnas a
        cb = numColumnas b
        fa = numFilas a
        fb = numFilas b

-- ----------------------------------------------------------------------------
-- 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?
-- ----------------------------------------------------------------------------

potencia :: Num a => Matriz a -> Int -> Matriz a
potencia m n | numFilas m /= numColumnas m = error "La matriz debe ser cuadrada"
             | n == 1 = m
             | otherwise = prodMatrices m (potencia m (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]]
-- ----------------------------------------------------------------------------

traspuesta :: Matriz a -> Matriz a
traspuesta m = listArray ((1,1),(c,f)) [m ! (j,i) | i <- [1..c], j <- [1..f]]
  where c = numColumnas m
        f = numFilas 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]]
-- ----------------------------------------------------------------------------

submatriz :: Int -> Int -> Matriz a -> Matriz a
submatriz fila columna m = listArray ((1,1),(f-1,c-1)) [m ! (i,j) | i <- [1..f], j <- [1..c], i /= fila, j /= columna]
  where c = numColumnas m
        f = numFilas m

-- ----------------------------------------------------------------------------
-- 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.

determinante :: Num a => Matriz a -> a
determinante m | f /= c = error "La matriz no es cuadrada"
               | f == 1 = m ! (1,1)
               | otherwise = sum [(-1)^(j+1)*(m ! (1,j)) * (determinante (submatriz 1 j m))
                                 | j <- [1..c]]
  where (f,c) = dimension 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
-- ----------------------------------------------------------------------------

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
-- ----------------------------------------------------------------------------

esSimetrica :: Eq a => Matriz a -> Bool
esSimetrica m = m == traspuesta m

-- Si no se cae en esto:
esSimetrica' :: Eq a => Matriz a -> Bool
esSimetrica' m = esCuadrada m && and [m ! (i,j) == m ! (j,i) | i <- [1..f], j <- [1..c]]
  where c = numColumnas m
        f = numFilas 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
-- ----------------------------------------------------------------------------

esTriangularSuperior :: (Num a, Eq a) => Matriz a -> Bool
esTriangularSuperior m = esCuadrada m && and [m ! (i,j) == 0 | i <- [2..f], j <- [1..(i-1)]]
  where f = numFilas m

-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------

esTriangularInferior :: (Num a, Eq a) => Matriz a -> Bool
esTriangularInferior m = esCuadrada m && and [m ! (i,j) == 0 | j <- [2..c], i <- [1..(j-1)]]
  where c = 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
-- ----------------------------------------------------------------------------

esEscalar :: (Num a, Eq a) => Matriz a -> Bool
esEscalar m = esTriangularInferior m &&
              esTriangularSuperior m &&
              and [m ! (i,i) == m ! (1,1) | i <- [1..f]]
  where f = 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]
-- ----------------------------------------------------------------------------

diagonalPrincipal :: Matriz a -> Vector a
diagonalPrincipal m = listArray (1,min f c) [m ! (i,i) | i <- [1..(min f c)]]
  where (f,c) = dimension 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]
-- ----------------------------------------------------------------------------

diagonalSecundaria :: Matriz a -> Vector a
diagonalSecundaria m | not (esCuadrada m) = error "La matriz debe ser cuadrada"
                     | otherwise = listArray (1,f) [m ! (i,f - i + 1) | i <- [1..f]]
  where f = numFilas 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
-- ----------------------------------------------------------------------------

antidiagonal :: (Num a, Eq a) => Matriz a -> Bool
antidiagonal m = esCuadrada m && and [m ! (i,j) == 0 | i <- [1..n], j <- [1..n], i + j /= n + 1]
  where n = numFilas 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]])  ==  []
-- ----------------------------------------------------------------------------

posiciones :: Eq a => a -> Matriz a -> [(Int,Int)]
posiciones x m = map fst (filter ((==x).snd) (assocs m))

-- Otra opción:
posiciones' :: Eq a => a -> Matriz a -> [(Int,Int)]
posiciones' x m = filter (\ pos -> m ! pos == x ) (indices m)

-- ----------------------------------------------------------------------------
-- 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)]
-- ----------------------------------------------------------------------------

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]]
-- ----------------------------------------------------------------------------

creaTridiagonal :: Int -> Matriz Int
creaTridiagonal n = listArray ((1,1),(n,n)) [seleccionaElemento i j | i <- [1..n], j <- [1..n]]
  where seleccionaElemento i j | i == j     = i
                               | i == j - 1 = i
                               | i == j + 1 = j
                               | otherwise = 0

-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------

esTridiagonal :: (Num a, Eq a) => Matriz a -> Bool
esTridiagonal m = and [m ! (i,j) == 0 | i <- [1..f], j <- [1..c], i /= j && i /= j + 1 && i /= j - 1]
  where (f,c) = dimension m

-- ============================================================================