Introdução a Haskell

Matrizes

De forma simplificada, podemos definir uma matriz no Haskell como uma lista de listas, em que cada elemento da lista principal corresponde a uma linha e cada elemento de cada uma dessas listas corresponde a uma coluna da matriz.

matriz = [ [1,2], [3,4] ]

Para trabalharmos adequadamente com as listas é importante definir funções básicas (nota: essas funções não são padrões do Haskell, porém existe como utilizar módulos externos que contém tais funções.):

tamanhoMtx      :: [[a]] -> (Int, Int)
somaMtx         :: Num a => [[a]] -> [[a]] -> [[a]]
subMtx          :: Num a => [[a]] -> [[a]] -> [[a]]
somaConstMtx    :: Num a => a -> [[a]] -> [[a]]
multConstMtx    :: Num a => a -> [[a]] -> [[a]]
transpostaMtx   :: [[a]] -> [[a]]
multMtx         :: Num a => [[a]] -> [[a]] -> [[a]]

Repare que as funções que tratam de operações numéricas são restringidas à classe Num.

A primeira função, tamanhoMtx recebe uma matriz como parâmetro e retorna uma tupla com as dimensões da matriz, basta definirmos os tamanhos m e n como o tamanho da lista externa e interna:

tamanhoMtx mtx = (m, n)
  where
    m = length mtx
    n = length $ head mtx

As funções de soma e subtração entre matrizes podem ser definidas através de uma sequência de zipWith. Simplificando o problema, imagine que temos uma função somaListas que soma duas listas:

somaListas l1 l2 = zipWith (+) l1 l2

Uma vez que os parâmetros são apenas repassados para a função zipWith, podemos definir tal função resumidamente como:

somaListas = zipWith (+)

A soma de matrizes nada mais é do que a soma de listas para cada par de lista extraída de cada uma das matrizes:

somaMtx m1 m2 = zipWith somaListas m1 m2

ou:

somaMtx = zipWith (zipWith (+))

Exercício 01: Modifique a função somaMtx para definir a função subMtx.

Para somar uma constante x a uma matriz precisamos aplicar a soma de x em cada elemento da linha para cada linha. Simplificando novamente, para somar uma constante a uma linha definimos:

somaConst x = map (+x)

E para aplicar essa função em cada linha da matriz:

somaConstMtx x = map (map (+x))

Exercício 02: Modifique a função somaConstMtx para definir a função multConstMtx.

A função transposta transforma todas as linhas em colunas. Para simplificar o problema, vamos criar uma função chamada primeiraCol que extrairá a primeira coluna de uma matriz qualquer. Dado que cada linha da matriz é representada por uma lista, a primeira coluna é a junção dos primeiros elementos de cada lista:

primeiraCol m = map head m

Da mesma forma podemos criar a função removePrimeiraCol que retorna a matriz sem a primeira coluna:

removePrimeiraCol m = map tail m

A função transposta pode ser definida facilmente como a composição da primeira coluna e a chamada recursiva sobre o restante da matriz:

transpostaMtx m = primeiraCol m : primeiraCol (removePrimeiraCol m) : primeiraCol (removePrimeiraCol (removePrimeiraCol m)) ...

Finalmente temos:

transpostaMtx ([]:_) = []
transpostaMtx m = (map head m) : transpostaMtx (map tail m)

O primeiro padrão faz-se necessário para o caso base, em que a cabeça da lista é vazia.

A função multMtx deve ser capaz de multiplicar duas matrizes, m1, m2, cujas dimensões internas são as mesmas. Basicamente, o elemento (i, j) resultante dessa multiplicação é o produto interno da linha i de m1 e da coluna j de m2. O primeiro passo é definir a função prodInterno:

prodInterno l1 l2 = sum $ zipWith (*) l1 l2

Então temos que a multiplicação pode ser definida como:

multMtx m1 m2 = [ [prodInterno (row i m1) (col j m2) | j <- [0..ncols m2 - 1]] | i <- [0..nrows m1 - 1] ]

A expressão ainda necessita de algumas funções suportes e está muito complexa. Podemos simplificar assumindo que a dimensão da matriz resultante será (m,n):

multMtx m1 m2 = [ [prodInterno (row i m1) (col j m2) | j <- [0..n]] | i <- [0..m] ]
  where
    m = fst $ tamanhoMtx m1
    n = snd $ tamanhoMtx m2

A extração da linha i de m1 pode ser feita como m1 !! i, ou seja, o i-ésimo elemento de m1. Para poder fazermos o mesmo com m2 teremos que trabalhar com sua transposta:

multMtx m1 m2 = [ [prodInterno (m1 !! i) (m2' !! j) | j <- [0..n-1]] | i <- [0..m-1] ]
  where
    m   = fst $ tamanhoMtx m1
    n   = snd $ tamanhoMtx m2
    m2' = transpostaMtx m2

Ao invés de usarmos os índices, podemos capturar cada linha diretamente com:

multMtx m1 m2 = [ [prodInterno ri rj | rj <- m2'] | ri <- m1 ]
  where
    m2' = transpostaMtx m2
    prodInterno l1 l2 = sum $ zipWith (*) l1 l2

Note que caso as dimensões internas das matrizes não sejam iguais, devemos emitir uma mensagem de erro:

multMtx m1 m2 
  | k1 /= k2  = error "Matrizes incompativeis!"
  | otherwise = [ [prodInterno ri rj | rj <- m2'] | ri <- m1 ]
  where
    m2' = transpostaMtx m2
    prodInterno l1 l2 = sum $ zipWith (*) l1 l2
    k1 = snd $ tamanhoMtx m1
    k2 = fst $ tamanhoMtx m2

Com isso temos as operações básicas para trabalharmos com matrizes em Haskell.