10 jul. 2009

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

5 comentarios:

Roberto Horacio dijo...

Orale! Muchas gracias! Curiosamente me acabo de embarcar en un proyecto personal en el que necesito manejar matrices, y lo penaba hacer en Java por no saber usar bien Haskell, pero creo que probaré con tus ideas.

Gracias!!!

PAGE dijo...

De nada. Espero tengas exito en tu proyecto. Si quieres algo mas detallado sobre matrices puedes checar el tutorial "una introducción agradable a haskell".

Juan dijo...

Gracias por tus oprtes, es muy importante para los que nos estamos iniciando en esto de la programación. Talves les sirva un poco:
http://www.program.webcindario.com/codigos/haskell.html
En esa página existen algunos ejemplos.

Gracias por tus aportes.

PAGE dijo...

Gracias, y gracias por el link es bueno saber que hay más entusiastas de haskell :)

Anónimo dijo...

podrias implementar esto en haskell

https://github.com/attractivechaos/plb/blob/master/sudoku/sudoku_v1.c

no se como traducir algoritmos en forma funcional

ga