Enumeración del producto cartesiano de los naturales en Haskell

En esta relación se definen funciones que enumeran el conjunto de los pares de números naturales; es decir, funciones biyectivas $f: \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ y $g: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ .

Las definiciones de las funciones se hacen por comprensión y recursión. La propiedad biyectiva se comprueba mostrando que $f \cdot g$ y $g \cdot f$ son la identidad.

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir, por comprensión, la constante
--    pares :: [(Int,Int)]
-- tal que pares es la lista de los pares de números taturales ordenados
-- primero por la suma y después por la primera coordenada; es decir,
-- (x,y) es menor que (x',y') si x+y < x'+y' ó (x+y = x'+y' y x  < x'). 
-- Por ejemplo,
--    ghci> take 10 pares
--    [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]
-- ---------------------------------------------------------------------

pares :: [(Int,Int)]
pares = [(x,z-x) | z <- [0..], x <- [0..z]]

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    par :: Int -> (Int,Int)
-- tal que (par n) es el par de números naturales que ocupa la posición
-- n en la lista pares. Por ejemplo,
--    par 5  ==  (2,0)
-- ---------------------------------------------------------------------

par :: Int -> (Int,Int)
par n = pares !! n

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir, por recursión, la función
--    par :: Int -> (Int,Int)
-- tal que (par' n) es el par de números naturales que ocupa la posición
-- n en la lista pares. Por ejemplo,
--    par' 5  ==  (2,0)
-- ---------------------------------------------------------------------

par' :: Int -> (Int,Int)
par' 0 = (0,0)
par' (n+1) | y == 0    = (0,x+1)
           | otherwise = (x+1,y-1)
    where (x,y) = par' n

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    equivalencia_par :: Int -> Bool
-- (equivalencia_par n) se verifica si para todo número natural x menor
-- o igual que n se tiene que (par x) y (par' x) son iguales. Por
-- ejemplo, 
--    equivalencia_par 100  ==  True
-- ---------------------------------------------------------------------

equivalencia_par :: Int -> Bool
equivalencia_par n =
    and [par x == par' x | x <- [0..n]]

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir, por comprensión, la función
--    indice :: (Int,Int) -> Int
-- tal que (indice (x.y)) es el lugar que ocupa el par (x,y) en la lista
-- pares. Por ejemplo, 
--    indice (2,0)  ==  5
-- ---------------------------------------------------------------------

indice :: (Int,Int) -> Int
indice (x,y) = fst (head [(n,(u,v)) | (n,(u,v)) <- zip [0..] pares,
                                      (u,v) == (x,y)])


-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir, por recursión, la función
--    indice' :: (Int,Int) -> Int
-- tal que (indice' (x.y)) es el lugar que ocupa el par (x,y) en la lista
-- pares. Por ejemplo, 
--    indice' (2,0)  ==  5
-- ---------------------------------------------------------------------

indice' :: (Int,Int) -> Int
indice' (0,0)   = 0
indice' (0,y+1) = 1 + indice' (y,0)
indice' (x+1,y) = 1 + indice' (x,1+y)

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la función
--    menores :: (Int,Int) -> [(Int,Int)]
-- tal que (menores (x,y)) es la lista de los pares de números naturales
-- menores que (x,y) en el orden definido en el ejercicio 1. Por
-- ejemplo, 
--    menores (2,1) == [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2)]
-- ---------------------------------------------------------------------

menores :: (Int,Int) -> [(Int,Int)]
menores (x,y) = takeWhile (/= (x,y)) pares

-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir la función
--    equivalencia_indice :: Int -> Bool
-- (equivalencia_indice (x,y)) se verifica si para todo par de números
-- naturales (u,v) menores que (x,y) se tiene que (indice (u,v)) es
-- igual que (indice' (u,v)). Por ejemplo,
--    equivalencia_indice (14,0)  ==  True
-- ---------------------------------------------------------------------

equivalencia_indice :: (Int,Int) -> Bool
equivalencia_indice (x,y) =
    and [indice (u,v) == indice (u,v) | (u,v) <- menores (x,y)]

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la propiedad
--    prop_indice_par :: Int -> Bool
-- tal que (prop_indice_par n) se verifica si para todo número natural x
-- menor o igual que n se tiene que (indice (par x)) es igual a x. Por
-- ejemplo, 
--    prop_indice_par 100  ==  True
-- ---------------------------------------------------------------------

prop_indice_par :: Int -> Bool
prop_indice_par n =
    and [indice (par x) == x | x <- [0..n]] 

-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir la propiedad
--    prop_par_indice :: Int -> Bool
-- tal que (prop_par_indice (x,y)) se verifica si para si para todo par
-- de números naturales (u,v) menores que (x,y) se tiene que 
-- (par (indice (u,v))) es igual a (u,v). Por
-- ejemplo, 
--    prop_par_indice (14,0)  ==  True
-- ---------------------------------------------------------------------

prop_par_indice :: (Int,Int) -> Bool
prop_par_indice (x,y) =
    and [par (indice (u,v)) == (u,v) | (u,v) <- menores (x,y)]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir, por comprensión, la constante

-- pares :: [(Int,Int)]

-- tal que pares es la lista de los pares de números taturales ordenados

-- primero por la suma y después por la primera coordenada; es decir,

-- (x,y) es menor que (x',y') si x+y < x'+y' ó (x+y = x'+y' y x < x').

-- Por ejemplo,

-- ghci> take 10 pares

-- [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]

-- ---------------------------------------------------------------------

pares :: [(Int,Int)]

pares = [(x,z-x) | z <- [0..], x <- [0..z]]

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función

-- par :: Int -> (Int,Int)

-- tal que (par n) es el par de números naturales que ocupa la posición

-- n en la lista pares. Por ejemplo,

-- par 5 == (2,0)

-- ---------------------------------------------------------------------

par :: Int -> (Int,Int)

par n = pares !! n

-- ---------------------------------------------------------------------

-- Ejercicio 3. Definir, por recursión, la función

-- par :: Int -> (Int,Int)

-- tal que (par' n) es el par de números naturales que ocupa la posición

-- n en la lista pares. Por ejemplo,

-- par' 5 == (2,0)

-- ---------------------------------------------------------------------

par' :: Int -> (Int,Int)

par' 0 = (0,0)

par' (n+1) | y == 0 = (0,x+1)

| otherwise = (x+1,y-1)

where (x,y) = par' n

-- ---------------------------------------------------------------------

-- Ejercicio 4. Definir la función

-- equivalencia_par :: Int -> Bool

-- (equivalencia_par n) se verifica si para todo número natural x menor

-- o igual que n se tiene que (par x) y (par' x) son iguales. Por

-- ejemplo,

-- equivalencia_par 100 == True

-- ---------------------------------------------------------------------

equivalencia_par :: Int -> Bool

equivalencia_par n =

and [par x == par' x | x <- [0..n]]

-- ---------------------------------------------------------------------

-- Ejercicio 5. Definir, por comprensión, la función

-- indice :: (Int,Int) -> Int

-- tal que (indice (x.y)) es el lugar que ocupa el par (x,y) en la lista

-- pares. Por ejemplo,

-- indice (2,0) == 5

-- ---------------------------------------------------------------------

indice :: (Int,Int) -> Int

indice (x,y) = fst (head [(n,(u,v)) | (n,(u,v)) <- zip [0..] pares,

(u,v) == (x,y)])

-- ---------------------------------------------------------------------

-- Ejercicio 6. Definir, por recursión, la función

-- indice' :: (Int,Int) -> Int

-- tal que (indice' (x.y)) es el lugar que ocupa el par (x,y) en la lista

-- pares. Por ejemplo,

-- indice' (2,0) == 5

-- ---------------------------------------------------------------------

indice' :: (Int,Int) -> Int

indice' (0,0) = 0

indice' (0,y+1) = 1 + indice' (y,0)

indice' (x+1,y) = 1 + indice' (x,1+y)

-- ---------------------------------------------------------------------

-- Ejercicio 7. Definir la función

-- menores :: (Int,Int) -> [(Int,Int)]

-- tal que (menores (x,y)) es la lista de los pares de números naturales

-- menores que (x,y) en el orden definido en el ejercicio 1. Por

-- ejemplo,

-- menores (2,1) == [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2)]

-- ---------------------------------------------------------------------

menores :: (Int,Int) -> [(Int,Int)]

menores (x,y) = takeWhile (/= (x,y)) pares

-- ---------------------------------------------------------------------

-- Ejercicio 8. Definir la función

-- equivalencia_indice :: Int -> Bool

-- (equivalencia_indice (x,y)) se verifica si para todo par de números

-- naturales (u,v) menores que (x,y) se tiene que (indice (u,v)) es

-- igual que (indice' (u,v)). Por ejemplo,

-- equivalencia_indice (14,0) == True

-- ---------------------------------------------------------------------

equivalencia_indice :: (Int,Int) -> Bool

equivalencia_indice (x,y) =

and [indice (u,v) == indice (u,v) | (u,v) <- menores (x,y)]

-- ---------------------------------------------------------------------

-- Ejercicio 9. Definir la propiedad

-- prop_indice_par :: Int -> Bool

-- tal que (prop_indice_par n) se verifica si para todo número natural x

-- menor o igual que n se tiene que (indice (par x)) es igual a x. Por

-- ejemplo,

-- prop_indice_par 100 == True

-- ---------------------------------------------------------------------

prop_indice_par :: Int -> Bool

prop_indice_par n =

and [indice (par x) == x | x <- [0..n]]

-- ---------------------------------------------------------------------

-- Ejercicio 10. Definir la propiedad

-- prop_par_indice :: Int -> Bool

-- tal que (prop_par_indice (x,y)) se verifica si para si para todo par

-- de números naturales (u,v) menores que (x,y) se tiene que

-- (par (indice (u,v))) es igual a (u,v). Por

-- ejemplo,

-- prop_par_indice (14,0) == True

-- ---------------------------------------------------------------------

prop_par_indice :: (Int,Int) -> Bool

prop_par_indice (x,y) =

and [par (indice (u,v)) == (u,v) | (u,v) <- menores (x,y)]

Se puede imprimir o compartir con