Conjuntos de puntos enteros en regiones rectangulares
Los puntos de una cuadrícula se puede representar mediante pares de números enteros
|
1 |
type Punto = (Int,Int) |
y las regiones rectangulares mediante el siguiente tipo de dato
|
1 2 3 4 |
data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show) |
donde
- (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
- (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
- (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.
Definir la función
|
1 |
puntos :: Region -> [Punto] |
tal que (puntos r) es la lista de puntos de la región r. Por ejemplo, usando las regiones definidas por
|
1 2 3 4 |
r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2) |
se tiene
|
1 2 3 4 5 6 7 8 9 10 11 12 |
ghci> puntos r0021 [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)] ghci> puntos r3051 [(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)] ghci> puntos r4162 [(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)] ghci> puntos (Union r0021 r3051) [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)] ghci> puntos (Diferencia r3051 r4162) [(3,0),(3,1),(4,0),(5,0)] ghci> puntos (Union (Diferencia r3051 r4162) r4162) [(3,0),(3,1),(4,0),(5,0),(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)] |
Comprobar con QuickCheck, usando la función enRegion definida en el ejercicio [Puntos en regiones rectangulares](Puntos en regiones rectangulares) que (enRegion p r) es equivalente a (p elem puntos r).
Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
import Test.QuickCheck import Control.Monad type Punto = (Int,Int) data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show) r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2) puntos :: Region -> [Punto] puntos = undefined -- La propiedad es prop_puntos :: Punto -> Region -> Bool prop_puntos p r = undefined -- La comprobación es -- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos -- +++ OK, passed 100 tests. enRegion :: Punto -> Region -> Bool enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) = x1 <= x && x <= x2 && y1 <= y && y <= y2 enRegion p (Union r1 r2) = enRegion p r1 || enRegion p r2 enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2) -- Generador de regiones: instance Arbitrary Region where arbitrary = sized arb where arb 0 = liftM2 Rectangulo arbitrary arbitrary arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary, liftM2 Union sub sub, liftM2 Diferencia sub sub] where sub = arb (n `div` 2) |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import Data.List import Test.QuickCheck import Control.Monad type Punto = (Int,Int) data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show) r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2) puntos :: Region -> [Punto] puntos (Rectangulo (x1,y1) (x2,y2)) = [(x,y) | x <- [x1..x2], y <- [y1..y2]] puntos (Union r1 r2) = puntos r1 `union` puntos r2 puntos (Diferencia r1 r2) = puntos r1 \\ puntos r2 -- La propiedad es prop_puntos :: Punto -> Region -> Bool prop_puntos p r = enRegion p r == (p `elem` puntos r) -- La comprobación es -- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos -- +++ OK, passed 100 tests. enRegion :: Punto -> Region -> Bool enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) = x1 <= x && x <= x2 && y1 <= y && y <= y2 enRegion p (Union r1 r2) = enRegion p r1 || enRegion p r2 enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2) -- Generador de regiones: instance Arbitrary Region where arbitrary = sized arb where arb 0 = liftM2 Rectangulo arbitrary arbitrary arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary, liftM2 Union sub sub, liftM2 Diferencia sub sub] where sub = arb (n `div` 2) |
2 Comentarios