Conjuntos de puntos enteros en regiones rectangulares
Los puntos de una cuadrícula se puede representar mediante pares de números enteros
type Punto = (Int,Int)
y las regiones rectangulares mediante el siguiente tipo de dato
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
puntos :: Region -> [Punto]
tal que (puntos r) es la lista de puntos de la región r. Por ejemplo, usando las regiones definidas por
r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2)
se tiene
λ> puntos r0021 [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)] λ> puntos r3051 [(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)] λ> puntos r4162 [(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)] λ> 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)] λ> puntos (Diferencia r3051 r4162) [(3,0),(3,1),(4,0),(5,0)] λ> 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" 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
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 -- λ> 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
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 -- λ> 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)