Matrices de Hadamard
Las matrices de Hadamard se definen recursivamente como sigue
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
λ> hadamard 0 ( 1 ) λ> hadamard 1 ( 1 1 ) ( 1 -1 ) λ> hadamard 2 ( 1 1 1 1 ) ( 1 -1 1 -1 ) ( 1 1 -1 -1 ) ( 1 -1 -1 1 ) λ> hadamard 3 ( 1 1 1 1 1 1 1 1 ) ( 1 -1 1 -1 1 -1 1 -1 ) ( 1 1 -1 -1 1 1 -1 -1 ) ( 1 -1 -1 1 1 -1 -1 1 ) ( 1 1 1 1 -1 -1 -1 -1 ) ( 1 -1 1 -1 -1 1 -1 1 ) ( 1 1 -1 -1 -1 -1 1 1 ) ( 1 -1 -1 1 -1 1 1 -1 ) |
En general, la n-ésima matriz de Hadamard, H(n), es
|
1 2 |
( H(n-1) H(n-1) ) ( H(n-1) -H(n-1) ) |
Definir la función
|
1 |
hadamard :: Int -> Matrix Int |
tal que (hadamard n) es la n-ésima matriz de Hadamard.
Comprobar con QuickCheck que para todo número natural n, el producto de la n-ésima matriz de Hadamard y su traspuesta es igual al producto de 2^n por la matriz identidad de orden 2^n.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import Data.Matrix (Matrix, identity, joinBlocks, scaleMatrix, transpose) import Test.QuickCheck hadamard :: Int -> Matrix Int hadamard 0 = identity 1 hadamard n = joinBlocks (a, a, a, b) where a = hadamard (n-1) b = scaleMatrix (-1) a -- La propiedad es prop_Hadamard :: (Positive Int) -> Bool prop_Hadamard (Positive n) = h * transpose h == scaleMatrix (2^n) (identity (2^n)) where h = hadamard n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_Hadamard -- +++ OK, passed 100 tests. |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>