import Data.Array
type Matriz = Array (Int,Int) Int
ej :: Matriz
ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 1, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0]
-- 1ª solución
-- ===========
relleno1 :: Matriz -> Matriz
relleno1 p =
array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
where (_,(m,n)) = bounds p
f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1
| 1 `elem` [p!(k,j) | k <- [1..m]] = 1
| otherwise = 0
-- 2ª solución
-- ===========
relleno2 :: Matriz -> Matriz
relleno2 p =
array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
where (_,(m,n)) = bounds p
filas = filasConUno p
columnas = columnasConUno p
f i j | i `elem` filas = 1
| j `elem` columnas = 1
| otherwise = 0
-- (filasConUno p) es la lista de las filas de p que tienen algún
-- uno. Por ejemplo,
-- filasConUno ej == [3,4]
filasConUno :: Matriz -> [Int]
filasConUno p = [i | i <- [1..m], filaConUno p i]
where (_,(m,n)) = bounds p
-- (filaConUno p i) se verifica si p tiene algún uno en la fila i. Por
-- ejemplo,
-- filaConUno ej 3 == True
-- filaConUno ej 2 == False
filaConUno :: Matriz -> Int -> Bool
filaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]
where (_,(_,n)) = bounds p
-- (columnasConUno p) es la lista de las columnas de p que tienen algún
-- uno. Por ejemplo,
-- columnasConUno ej == [1,4]
columnasConUno :: Matriz -> [Int]
columnasConUno p = [j | j <- [1..n], columnaConUno p j]
where (_,(m,n)) = bounds p
-- (columnaConUno p i) se verifica si p tiene algún uno en la columna i. Por
-- ejemplo,
-- columnaConUno ej 1 == True
-- columnaConUno ej 2 == False
columnaConUno :: Matriz -> Int -> Bool
columnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]
where (_,(m,_)) = bounds p
-- 3ª solución
-- ===========
relleno3 :: Matriz -> Matriz
relleno3 p = p // ([((i,j),1) | i <- filas, j <- [1..n]] ++
[((i,j),1) | i <- [1..m], j <- columnas])
where (_,(m,n)) = bounds p
filas = filasConUno p
columnas = columnasConUno p
-- Comparación de eficiencia
-- =========================
-- λ> let f i j = if i == j then 1 else 0
-- λ> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]
--
-- λ> sum (elems (relleno1 (q 200)))
-- 40000
-- (6.90 secs, 1,877,369,544 bytes)
--
-- λ> sum (elems (relleno2 (q 200)))
-- 40000
-- (0.46 secs, 57,354,168 bytes)
--
-- λ> sum (elems (relleno3 (q 200)))
-- 40000
-- (0.34 secs, 80,465,144 bytes)
--
-- λ> sum (elems (relleno2 (q 500)))
-- 250000
-- (4.33 secs, 353,117,640 bytes)
--
-- λ> sum (elems (relleno3 (q 500)))
-- 250000
-- (2.40 secs, 489,630,048 bytes)