Programación funcional como ejemplo de trabajo con matrices desde la teoría del álgebra lineal.

Introducción

La base para trabajar con matrices (en este artículo consideraremos solo matrices bidimensionales) es una poderosa teoría matemática del campo del álgebra lineal. Una definición o acción se sigue de otra; una función llama a otra. Por lo tanto, para la implementación funcional del funcionamiento de operaciones matemáticas en matrices, los lenguajes funcionales se ajustan muy bien. En este artículo, veremos ejemplos específicos en F # y daremos comentarios detallados sobre cómo funciona esto. Dado que F # es parte de la familia .NET, la funcionalidad resultante se puede usar sin problemas en otros lenguajes imperativos, por ejemplo C #.

Definición de matriz e implementación en F #

Las matrices son la parte básica y más importante del álgebra lineal. Las matrices se usan a menudo en programación, por ejemplo, en modelado 3D o desarrollo de juegos. Por supuesto, la bicicleta ha sido inventada por mucho tiempo y los marcos necesarios para trabajar con matrices ya están listos, y pueden y deben usarse. Este artículo no tiene como objetivo inventar un nuevo marco, sino que muestra la implementación de operaciones matemáticas básicas para trabajar con matrices en un estilo funcional utilizando el lenguaje de programación F #. A medida que examinemos el material, pasaremos a la teoría matemática de las matrices y veremos cómo se puede implementar en el código.

Primero, recordemos qué es una matriz? La teoría nos dice lo siguiente

Una tabla rectangular de números que contiene m filas yn columnas se denomina matriz de tamaño mxn

Las matrices generalmente se denotan con letras mayúsculas del alfabeto latino y se escriben como

$$

$$A=\begin{pmatrix}a11&a12&...&a1n\\a21&a22&...&a2n\\...&...&...&...\\am1&am2&...&amn\end{pmatrix}$$

O en breve

$$

$$A=(aij)$$

Para trabajar con matrices en F # crearemos un registro basado en una tabla bidimensional, que ampliaremos aún más con métodos útiles para realizar las operaciones matemáticas necesarias en él.

type Matrix = { values: int[,] }
    with
        //    
    end

Agregue un método auxiliar para inicializar la grabación con una matriz bidimensional

static member ofArray2D (values: int [,]) = 
    { values = values }

El argumento de entrada a la función será una matriz bidimensional y, a su salida, un registro de tipo Matrix . A continuación se muestra un ejemplo de inicialización de registros.

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

Dos matrices A = (aij) y B = (bij) se llaman iguales si coinciden en elementos, es decir aij = bij para todos i = 1,2 ..., m y j = 1,2 ... n

Para implementar esta regla, utilizaremos el operador anulado == y agregaremos un par de funciones útiles, que también necesitaremos en el futuro.

static member sizes matrix =
    let rows = matrix.values.[*,0].Length
    let cols = matrix.values.[0,*].Length
    (rows, cols)

static member isEquallySized matrix1 matrix2 =
    let dim1 = Matrix.sizes matrix1
    let dim2 = Matrix.sizes matrix2
    (dim1 = dim2)

static member (==) (matrix1, matrix2) =
    if not (Matrix.isEquallySized matrix1 matrix2) then false
    else
        not (matrix1.values
               |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
               |> Seq.cast<bool>
               |> Seq.contains false)

Echemos un vistazo más de cerca al código anterior. Como puede ver, hay tres funciones. La función de primeros tamaños devuelve la dimensión de la matriz como una tupla. Como solo trabajamos con matrices rectangulares, para obtener el número de filas, tomamos una porción completa de la primera columna y devolvemos su longitud.

let rows = matrix.values.[*,0].Length

Determinar el número de columnas funciona de manera similar: obtenemos una porción completa de la primera fila y devolvemos su longitud.

La siguiente función isEquallySized compara la dimensión de dos matrices y devuelve verdadero si son iguales. Para hacer esto, utiliza la función de tamaños listos para usar y simplemente compara los resultados.

El operador == para comparar dos matrices por elementos parece más complicado, pero ahora verá que también es simple.

Antes de comparar dos matrices, comparamos su dimensión. Si no son iguales, entonces no hay otro punto en la comprobación, ya que está claro que las matrices no serán iguales.

if not (Matrix.isEquallySized matrix1 matrix2) then false

Además, sobre la base de las matrices originales matriz1 y matriz2, formamos una nueva matriz llena de verdadero o falso , dependiendo de si las celdas correspondientes de ambas matrices coinciden.

matrix1.values
|> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true

La función Array2D.mapi itera sobre todos los elementos de matriz1 y pasa tres parámetros
x al controlador - índice de fila
y - índice de columna
v -
contenido de celda Comparamos el contenido de la celda v con la matriz de celda2 correspondiente y, si son iguales, escribimos verdadero , de lo contrario falso .

Si hay al menos una celda con el elemento falso , entonces esto significa que las matrices no son iguales entre sí.

Como Array2D no contiene métodos para filtrar o buscar, lo implementaremos nosotros mismos. Para hacer esto, descomponemos la matriz en una lista lineal

|> Seq.cast<bool>

Y encuentra al menos un desajuste

|> Seq.contains false

La función Seq.contains devolverá verdadero si se encuentra al menos un valor falso en la lista expandida . Por lo tanto, necesitamos invertir el resultado para que el operador == funcione de la manera que queremos

else
    not (matrix1.values
           |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
           |> Seq.cast<bool>
           |> Seq.contains false)

Una matriz O se llama matriz cero o cero si todos sus elementos son iguales a cero.

static member O rows cols =
    let array2d = Array2D.zeroCreate rows cols
    { values = array2d }

Un ejemplo del uso de esta función.

let AO = Matrix.O 5 5

Creo que no hay nada complicado que requiera explicación, por lo que continuamos.

Una matriz cuyo número de filas es igual al número de columnas e igual a n se llama matriz cuadrada de orden n

Por lo tanto, la matriz cuadrada tiene la forma.

$$

$$A=\begin{bmatrix}a11&a12&...&a1n\\a21&a22&...&a2n\\...&...&...&...\\an1&an2&...&ann\end{bmatrix}$$

Como parte de esta regla, crearemos una función que transforma una matriz rectangular en una matriz cuadrada cortando todos los elementos que no caen dentro del cuadrado.

static member toSquare matrix =

    //    
    let dim = Matrix.sizes matrix

    //   
    let colCount: int = snd dim
    //   
    let rowCount: int = fst dim

    //    
    let length = System.Math.Min (colCount, rowCount)

    //      
    //     
    let zero = Array2D.zeroCreate length length

    //     
    let square = zero |> Array2D.mapi (fun x y _ -> matrix.values.[x, y])

    //   
    { values = square }

Los comentarios en el código fuente explican cómo funciona la función, así que continuemos.

Una matriz cuadrada se llama triangular si todos sus elementos debajo de la diagonal principal son iguales a cero, es decir. la matriz triangular tiene la forma

$$

$$T=\begin{pmatrix}a11&a12&...&a1n\\0&a22&...&a2n\\...&...&...&...\\0&0&...&ann\end{pmatrix}$$

A continuación se muestra el código de función que convierte la matriz original en una triangular. Pero en nuestra función trabajaremos con una matriz rectangular, es decir, puede que no sea cuadrada. El lector puede modificar fácilmente el código de función para que devuelva una matriz triangular cuadrada utilizando la función que examinamos anteriormente.

static member T matrix =
    let values = matrix.values |> Array2D.mapi (fun x y v -> if y < x then 0 else v)
    { values = values }

La función Array2D.mapi convierte la matriz bidimensional original en una nueva utilizando un controlador que toma tres parámetros

x - número de fila
y - número de columna
v - contenido de la celda

if y < x then 0 else v

Aquí verificamos si el elemento está debajo de la diagonal principal y, de ser así, llenamos la celda 0. De lo contrario, el valor inicial de la matriz de entrada.

El siguiente es un ejemplo del uso de esta función.

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.triangular A
printfn "origin = \n %A" A.values
printfn "triangular = \n %A" R.values

Obtenemos el siguiente resultado

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
triangular = 
 [[1; 2; 3]
 [0; 5; 6]
 [0; 0; 9]
 [0; 0; 0]]

Una matriz cuadrada se llama diagonal si todos sus elementos ubicados fuera de la diagonal principal son iguales a cero

static member D matrix =
    let diagonal = matrix.values |> Array2D.mapi (fun x y v -> if x <> y then 0 else v)
    { values = diagonal }

Esta función es muy similar a la anterior, solo la condición de verificación es diferente. A continuación se muestra un ejemplo de uso

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.D A
printfn "origin = \n %A" A.values
printfn "diagonal = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
diagonal = 
 [[1; 0; 0]
 [0; 5; 0]
 [0; 0; 9]
 [0; 0; 0]]

La matriz diagonal es unidad y se denota con E si todos sus elementos ubicados en la diagonal principal son iguales a la unidad

$$

$$E=\begin{pmatrix}1&0&...&0\\0&1&...&0\\...&...&...&...\\0&0&...&1\end{pmatrix}$$

La implementación de dicha matriz en F # se ve así

static member E rows cols =
    let array2d = Array2D.init rows cols (fun x y -> if x = y then 1 else 0)
    { values = array2d }

Operaciones matriciales con F #

Se pueden realizar varias acciones en matrices, así como en números, algunas de las cuales son similares a las operaciones en números, y algunas son específicas.

La suma de dos matrices Amn = (aij) y Bmn = (bij) del mismo tamaño es la matriz del mismo tamaño A + B = Cmn = (cij) , cuyos elementos son iguales a la suma de los elementos de las matrices A y B , ubicados

$$

$$cij=aij+bij, i=1,2,...,m, j=1,2,...,n$$

Ejemplo, para las matrices dadas A y B, encontramos la suma A + B

$$

$$A=\begin{pmatrix}2&3\\1&-5\\0&6\end{pmatrix}, B=\begin{pmatrix}-3&3\\1&7\\2&0\end{pmatrix}, A+B=\begin{pmatrix}-1&6\\2&2\\2&6\end{pmatrix}$$

Considere el código para agregar dos matrices

static member (+) (matrix1, matrix2) =
    if Matrix.isEquallySized matrix1 matrix2 then
        let array2d = matrix1.values |> Array2D.mapi (fun x y v -> matrix2.values.[x, y] + v)
        { values = array2d }
    else failwith "matrix1 is not equal to matrix2"

Antes de agregar matrices, debe asegurarse de que su dimensión coincida, de lo contrario, la función arroja una excepción. A continuación se muestra un ejemplo del uso de esta función.

let a = array2D [[2;3]
                 [1;-5]
                 [0;6]]
let A = Matrix.ofArray2D a

let b = array2D [[-3;3]
                 [1;7]
                 [2;0]]
let B = Matrix.ofArray2D b

let R = A+B
printfn "A+B =\n %A" R.values

A+B =
 [[-1; 6]
 [2; 2]
 [2; 6]]

El producto de la matriz A = (aij) por el número k es la matriz kA = (kaij) del mismo tamaño que la matriz A obtenida multiplicando todos los elementos de la matriz A por el número k

Ejemplo, para una matriz A dada , encontramos la matriz 3A

$$

$$A=\begin{pmatrix}2&3&0\\1&5&4\end{pmatrix}, 3A=\begin{pmatrix}6&9&0\\3&15&12\end{pmatrix}$$

static member (*) (value, matrix) = 
    let array2d = matrix.values |> Array2D.mapi (fun _ _ v -> v * value)
    { values = array2d }

Matrix -A = (- 1) * A será llamada la matriz opuesta A . De esta definición, procedemos sin problemas a la siguiente

La diferencia de las matrices A y B de igual tamaño es la suma de la matriz A y la matriz opuesta a B

static member (-) (matrix1: Matrix, matrix2: Matrix) = 
    if Matrix.isEquallySized matrix1 matrix2 then
        matrix1 + (-1)*matrix2
    else failwith "matrix1 is not equal to matrix2"

Dos matrices se llaman consistentes si el número de columnas de la primera es igual al número de filas de la segunda

$$

$$A=\begin{pmatrix}2&1\\0&3\end{pmatrix}, B=\begin{pmatrix}0&5&2&1\\1&4&3&7\end{pmatrix}$$

static member isMatched matrix1 matrix2 = 
    let row1Count = matrix1.values.[0,*].Length
    let col2Count = matrix2.values.[*,0].Length

    row1Count = col2Count

Se requiere una comprobación de consistencia de la matriz para multiplicarlos.

El producto AB matriz coherente Amn = (aij) y Bnp = (bjk) es la matriz Cmn = (cik) , el elemento cik se calcula como la suma de los elementos i -ésima fila de la matriz A y los elementos correspondientes de la k ésima columna de la matriz B

Calcular el producto de matrices

$$

$$A=\begin{pmatrix}1&0&2\\3&1&0\end{pmatrix}, B=\begin{pmatrix}-1&0\\5&1\\-2&0\end{pmatrix}$$

Decisión de determinar el producto de matrices

$$

$$AB=\begin{pmatrix}1(-1)+0*5+2(-2)&1*0+0*1+2*0\\3(-1)+1*5+0(-2)&3*0+1*1+0*0\end{pmatrix}= \begin{pmatrix}-5&0\\2&1\end{pmatrix}$$

Considere el código para multiplicar dos matrices.

static member (*) (matrix1, (matrix2: Matrix)) =
    if Matrix.isMatched matrix1 matrix2 then
        let row1Count = matrix1.values.[*,0].Length
        let col2Count = matrix2.values.[0,*].Length

        let values = Array2D.zeroCreate row1Count col2Count

        for r in 0..row1Count-1 do
            for c in 0..col2Count-1 do
                let row = Array.toList matrix1.values.[r,*]
                let col = Array.toList matrix2.values.[*,c]

                let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col
                values.[r,c] <- cell

        { values = values }

    else failwith "matrix1 is not matched to matrix2"

Veamos el código con más detalle.
Antes de la multiplicación, debe asegurarse de que las matrices sean consistentes

if Matrix.isMatched matrix1 matrix2 then

La matriz resultante tendrá una dimensión en la que el número de filas es el mismo que el de la primera matriz y el número de columnas es el mismo que el de la segunda matriz.

let row1Count = matrix1.values.[*,0].Length
let col2Count = matrix2.values.[0,*].Length

//        
let values = Array2D.zeroCreate row1Count col2Count

Después de eso, recorremos todas las filas y todas las columnas de las matrices originales.

for r in 0..row1Count-1 do
    for c in 0..col2Count-1 do
        let row = Array.toList matrix1.values.[r,*]
        let col = Array.toList matrix2.values.[*,c]

Calculamos el valor total de cada celda

let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col

La función List.fold2 recibe dos listas en la entrada (fila y columna) y pasa los siguientes parámetros al controlador

según el acumulador que contiene el resultado del cálculo anterior
val1 , el contenido de la celda de la primera matriz. En nuestro caso, esta es la fila de la primera matriz
val2 : el contenido de la celda de la segunda matriz, es decir, las columnas de la segunda matriz.

Dado que las matrices son consistentes, estamos seguros de que no iremos más allá de las matrices.

El controlador agrega al acumulador un producto de celdas de filas y una columna, y el valor resultante se pasará a la siguiente iteración. Por lo tanto, el resultado final de la función List.fold2será el valor final de los productos de dos matrices. Solo queda llenarlos con la matriz vacía previamente creada

values.[r,c] <- cell

Que volverá como resultado

{ values = values }

A continuación se muestra un ejemplo del uso de esta función.

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

let b = array2D [[-1;0]
                 [5;1]
                 [-2;0]]
let B = Matrix.ofArray2D b

let R = A*B

printfn "A*B =\n %A" R.values

A1*B1 =
 [[-5; 0]
 [2; 1]]

Si k ∈ N, entonces la potencia enésima de una matriz cuadrada A es el producto de k matrices A

$$

$$A^k=A*A*...A (k- )$$

Considere el código en F # para el producto de una matriz a una potencia. La recursión de cola se usará aquí para no desbordar la pila con grandes poderes. La recursión de cola es una recursión que el compilador finalmente convierte en un bucle. Si es posible, se recomienda que siempre use la recursividad de cola en lugar de la habitual, pero para esto necesita que cada cuadro de recursión devuelva el valor calculado final. Este valor generalmente se denomina acumulador y se pasa al siguiente cuadro de recursión. Es decir, a diferencia de la recursión regular, que devuelve el valor calculado en la pila, la recursión de cola pasa el valor calculado a la pila. Cada nuevo cuadro de recursión realiza sus propios cálculos y los agrega al valor calculado previamente, que se almacena en la batería. Después de esto,Como el último fotograma de la recursión funcionó, el acumulador ya tiene un valor calculado, que simplemente devuelve como resultado.

Por lo tanto, el compilador puede optimizar el código y convertirlo en un bucle regular.

//    
// matrix -  
// value -  
static member (^^) (matrix, value) =

    //  ,    
    // m - 
    // p =  
    let inRecPow m p =

        //  
        // acc -  .   Matrix
        // p -     
        //         
        let rec recPow acc p =
            //   
            match p with
            | x when x > 0 ->
                //    
                //      ,      
                let nextAcc = acc*m
                //           
                recPow nextAcc (x-1)
            //    ,    
            | _ -> acc

        //   ,         
        let dim = Matrix.sizes matrix
        let colCount = snd dim
        let rowCount = fst dim

        let u = Matrix.E rowCount colCount
        //           
        recPow u p

    //  ,      
    let powMatrix = inRecPow matrix value
    //   
    { values = powMatrix.values }

El código contiene comentarios detallados sobre cómo funciona. Requiere una pequeña explicación, ¿por qué se usa la matriz unitaria? Es necesario para el primer cuadro de recursión y sirve como el valor base del acumulador, en el que se acumulará el resultado final.
A continuación se muestra un ejemplo del uso de nuestra función.

$$

$$A=\begin{pmatrix}1&0\\2&-1\end{pmatrix}$$

$$

$$A^2=AA=\begin{pmatrix}1&0\\2&-1\end{pmatrix}\begin{pmatrix}1&0\\2&-1\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}$$

$$

$$A^3=AA^2=\begin{pmatrix}1&0\\2&-1\end{pmatrix}\begin{pmatrix}1&0\\0&1\end{pmatrix}=\begin{pmatrix}1&0\\2&-1\end{pmatrix}$$

Calculamos el siguiente producto

$$

$$f(A)=2A^3-4A^2+3E$$

Donde E es la matriz de identidad. Como no podemos agregar un número a la matriz, debemos agregar 3E .

$$

$$2\begin{pmatrix}1&0\\2&-1\end{pmatrix}- 4\begin{pmatrix}1&0\\0&1\end{pmatrix}+ 3\begin{pmatrix}1&0\\0&1\end{pmatrix}= \begin{pmatrix}1&0\\4&-3\end{pmatrix}$$

//     
static member (+) (matrix, (value: int)) =
    let dim = Matrix.sizes matrix
    let r = fst dim
    let c = snd dim

    //   
    let unit = Matrix.E r c
    //          
    value*unit + matrix

let a = array2D [[1;0]
                 [2;-1]]
let A = Matrix.ofArray2D a

let R = 2*(A^^3) - 4*(A^^2) + 3
printfn "2*A^3 - 4*A^2 + 3 =\n %A" R.values

2*A5^3 - 4*A5^2 + 3 =
 [[1; 0]
 [4; -3]]

La matriz A ^T cuyas columnas están compuestas por filas de la matriz A con los mismos números y la misma secuencia de elementos se denomina transpuesta a la matriz A

static member transpose matrix =
    let dim = Matrix.sizes matrix
    let rows = fst dim
    let cols = snd dim

    //      
    let tMatrix = Matrix.O cols rows
    //       
    matrix.values |> Array2D.iteri(fun x y v -> tMatrix.values.[y, x] <- v)

    //  
    tMatrix

Ejemplo de uso

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R6 = Matrix.T A
printfn "origin = \n %A" A.values
printfn "transpose = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
transpose = 
 [[1; 4; 7; 10]
 [2; 5; 8; 11]
 [3; 6; 9; 12]]

Resumen

En este artículo, examinamos ejemplos de la implementación y uso de matrices de la teoría del álgebra lineal. Además de las operaciones matemáticas básicas sobre ellos, utilizando un enfoque funcional en F #. Espero que el lector pueda apreciar la flexibilidad que proporcionan los lenguajes funcionales.

El código fuente completo del módulo de matriz, cuyos fragmentos se consideraron en el marco del artículo, se puede encontrar en el github.

Github Matrix.fs