Matrices (Haskell)

Este semestre me dejaron implementar un verificador para PCTL (CTL probabilistico). El 80% del trabajo estaba facilisimo hacerlo en Haskell. Pero había una parte enla que era necesario hacer uso de matrices para resolver sistemas de ecuaciones. Lo primero que hice fue buscar información de como manejar matrices en Haskell, así que en aras de que no se me olvide y de que le sirva a alguien más, he aqui dos formas:

Matrices con listas.

Antes de ver como representar matrices veamos como representar vectores con listas. Hacemos uso de un sinónimo de tipo, es decir:

type Vector  = [Double]

Podemos entonces definir algunas funciones usando nuestro nuevo tipo de dato Vector (fijese como se declara el tipo de la función)


ppunto :: Vector -> Vector -> Double
ppunto [] [] = 0
ppunto (x:xs) (y:ys) = x*y + (ppunto xs ys)

La función regresa el producto escalar de dos vectores de dimesión n. La definición es poco elegante, por supuesto tenemos otra opción usando listas por comprensión:

ppunto2 xs ys = sum [x*y | (x,y) <- zip xs ys] 

Donde sum es la función del preludio de haskell que suma los elementos de una lista; zip lo que hace es tomar dos listas de la misma longitud y crea una nueva lista formada de parejas. Es decir: zip "123" "abc" = [(1,a),(2,b),(c,3)]


Siguiendo esta idea para representar matrices tendriamos

type Matriz = [Vector]

c = [[1,3.0],[2,5.0]]

Entonces podemos definir algunas funciones interesantes, por ejemplo la multiplicación de matrices.... peero me da mucha flojera trabajar con lista de listas... así que mejor veamos otra alternativa.

Tipo de dato Array.

Antes de ver arreglos es necesario entender el manejo de índices en Haskell. sólo veremos índices de tipo int e Integer (curiosamente también índices booleanos y otros...). Para eso es necesario entender la función range. Suponiendo que un arreglo esta indexado
desde 1 y no de 0 como en otros lenguajes (también es posible indexarlos desde cero). Entonces los índices de un arreglo de tamaño 10 serían: 1, 2,3,4,5,6,7,8,9,10; los de un arreglo de tamaño 5: 1,2,3,4,5; y del subarreglo de tamaño cinco de uno de 10? hay varias opciones:1,2,3,4,5 y 6,7,8,9,10; etc. range nos permite crear esos índices de manera muy fácil:

 range (1,10) devuelve [1,2,3,4,5,6,7,8,9,10]
 range (1,5) devuelve [1,2,3,4,5]
 range (6,10) devuelve [6,7,8,9,10]

range ((i,k),(j,l)) produce los indices:

 (i,  k)     (i,  k+1)      (i,  k+2)     (i,  k+3)........ (i,  l)
 (i+1,k)  (i+1,k+1)   (i+1,k+2)  (i+1,k+3)......(i+1,l)
 (i+2,k)  (i+2,k+1)  (i+2,k+2)  (i+2,k+3)......(i+2,l)
  .
  .
 (j,  k)     (j,k+1)        (j,k+2)        (j,k+3).....(j,l)

Para crear un arreglo se necesita importar el módulo Array, es decir al principio del archivo hay que poner: import Array

Un arreglo esta formado por un conjuto de índices y una lista que define lo que hay en esos indices. Ejemplos:

v1 = array (1,3) [(1,1.1),(2,2.0), (3,4.5)]
v2 = array (1,3) [(1,1.5),(2,4.0), (3,7.0)]

Arreglo de dos dimensiones:

m = array ((1,1),(4,4)) [ ((1,1), 0.0), ((1,2), 1.0), ((1,3),  0.0),    ((1,4), 0.0),
((2,1), 0.0), ((2,2), 0.01),((2,3),  0.1),  ((2,4), 0.98),
((3,1), 1.0), ((3,2), 0.0), ((3,3),  0.0),   ((3,4), 0.0),
((4,1), 0.0), ((4,2), 0.0), ((4,3),  0.0),   ((4,4), 1.0) ]

Son los mismos vectores declarados al principio pero usando el tipo de dato array. observese que en la lista de contenido se dice claramente lo que esta en la posición i del vector, por ejemplo (2,2.0) de v1 dice que en la posi ción(indice) 2 del arreglo v1 hay un 2.0 como contenido. Esto parece muy tedioso, pero será de gran utlidad. Definiciones equivalentes de v1 pueden ser:

 v1 = array (1,3) [(3,4.5),(2,2.0), (1,1.1)]

Es decir puede darse en "desorden" la defincion del contenido.

Para acceder al elemento en la posicion(índice) i de un arreglo arr , hacemos arr ! i (notese que i es un índice así que puede ser una tupla)

 v1 ! 1 devuelve 1.1
 v1 ! 3 devuelve 4.5
 

Para arreglos de dos dimensiones las consultas serían:

 m ! (4,4) devuelve 1.0
 m ! (2,3) devuelve 0.01

Con todo esto ya es posible definir matrices bien fácil. Ejemplos:

crea1  n =
   array (1,n) [(i,2*i) |i <- [1..n] ] 

Crea una matriz de 1xn, con contenido 2*i en la posición i .

creaidentidad n =
   array ((1,1),(n,n)) ([( (i,j), 1) | i <- range (1,n), j <- range (1,n), i==j]++ [( (i,j), 0) | i <- range (1,n), j <- range (1,n), i/=j]) 

Crea la matriz identidad de tamaño nxn, nótese que no tengo que decir explícitamente que hay en la posicion ij (ni siquiera decir quienes son i y j), ni incrementar el valor de contadores etc etc, es tal cual la definición de la matriz identidad, si i=j entonces hay un uno, y un cero en otro caso.

Tambien es posible modificar el contenido en alguna posición de una matriz!!! si suena raro siendo Haskell, pero se puede esto se hace con el operador (//) Ejemplos aqui.

Otra función muy útil en el manejo de matrices es bounds. Aqui un archivo donde vienen todos estos ejemplos (y más) , además de ejemplos de uso de la función bounds.

El proyecto quedó bien (en algún momento lo subiré), si alguien quiere hacer algo más elaborado, por ejemplo resolver sistemas de ecuaciones lineales mediante gauss recomiendo busquen aqui unos módulos de Haskell que hacen la magia.

Hay mucha gente entusiasta que ha escrito muchas bibliotecas para Haskell. Bibliotecas que simplifican mucho la vida cuando se quiere hacer un proyecto mas o menos grande etc. Aqui una lista de esas bibliotecas que simplificaran la vida de muchos y a otros les hará decir "a poco se puede con Haskell....."