Menu Close

Relaciones reflexivas

José A. Alonso, ,

Usando el tipo de las relaciones binarias, definir la función

   reflexiva :: Eq a => Rel a -> Bool

tal que reflexiva r se verifica si la relación r es reflexiva. Por ejemplo,

   reflexiva (R ([1,3],[(1,1),(1,3),(3,3)]))    ==  True
   reflexiva (R ([1,2,3],[(1,1),(1,3),(3,3)]))  ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Relaciones_reflexivas where
 
import Relaciones_binarias (Rel(R))
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
reflexiva :: Eq a => Rel a -> Bool
reflexiva (R ([], _))   = True
reflexiva (R (x:xs, ps)) = (x, x) `elem` ps && reflexiva  (R (xs, ps))
 
-- 2ª solución
-- ===========
 
reflexiva2 :: Eq a => Rel a -> Bool
reflexiva2 (R (us,ps)) = and [(x,x) `elem` ps | x <- us]
 
-- 3ª solución
-- ===========
 
reflexiva3 :: Eq a => Rel a -> Bool
reflexiva3 (R (us,ps)) = all (`elem` ps) [(x,x) | x <- us]
 
-- 4ª solución
-- ===========
 
reflexiva4 :: Eq a => Rel a -> Bool
reflexiva4 (R (us,ps)) = all (\x -> (x,x) `elem` ps) us
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_reflexiva :: Rel Int -> Bool
prop_reflexiva r =
  all (== reflexiva r)
      [reflexiva2 r,
       reflexiva3 r,
       reflexiva4 r]
 
-- La comprobación es
--    λ> quickCheck prop_reflexiva
--    +++ OK, passed 100 tests.


Soluciones en Python

from random import choice, randint, sample
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.Relaciones_binarias import Rel, relacionArbitraria
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def reflexiva(r: Rel[A]) -> bool:
    (us, ps) = r
    if not us:
        return True
    return (us[0], us[0]) in ps and reflexiva((us[1:], ps))
 
# 2ª solución
# ===========
 
def reflexiva2(r: Rel[A]) -> bool:
    (us, ps) = r
    return all(((x,x) in ps for x in us))
 
# 3ª solución
# ===========
 
def reflexiva3(r: Rel[A]) -> bool:
    (us, ps) = r
    for x in us:
        if (x, x) not in ps:
            return False
    return True
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_reflexiva(n: int) -> None:
    r = relacionArbitraria(n)
    res = reflexiva(r)
    assert reflexiva2(r) == res
    assert reflexiva3(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_reflexivas.py
#    1 passed in 0.41s
Leer más →

Universo y grafo de una relación binaria

José A. Alonso, ,

Usando el tipo de las relaciones binarias, definir las funciones

   universo :: Eq a => Rel a -> [a]
   grafo    :: Eq a => ([a],[(a,a)]) -> [(a,a)]

tales que

  • universo r es el universo de la relación r. Por ejemplo,
     λ> r = R ([1, 3],[(3, 1), (3, 3)])
     λ> universo r
     [1,3]
  • grafo r es el grafo de la relación r. Por ejemplo,
     λ> grafo r
     [(3,1),(3,3)]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Relaciones_binarias
 
universo :: Eq a => Rel a -> [a]
universo (R (u,_)) = u
 
grafo :: Eq a => Rel a -> [(a,a)]
grafo (R (_,g)) = g


Soluciones en Python

from typing import TypeVar
 
A = TypeVar('A')
 
Rel = tuple[list[A], list[tuple[A, A]]]
 
def universo(r: Rel[A]) -> list[A]:
    return r[0]
 
def grafo(r: Rel[A]) -> list[tuple[A, A]]:
    return r[1]
Leer más →

Relaciones binarias

José A. Alonso, ,

Una relación binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R).

Definir el tipo de dato (Rel a), para representar las relaciones binarias sobre a, y la función

   esRelacionBinaria :: Eq a => Rel a -> Bool

tal que esRelacionBinaria r se verifica si r es una relación binaria. Por ejemplo,

   λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 3)]))
   True
   λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)]))
   False

Además, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Data.List (nub)
import Test.QuickCheck
 
newtype Rel a = R ([a], [(a,a)])
  deriving (Eq, Show)
 
-- 1ª solución
-- ===========
 
esRelacionBinaria :: Eq a => Rel a -> Bool
esRelacionBinaria (R (u, g)) =
  and [x `elem` u && y `elem` u | (x,y) <- g]
 
-- 2ª solución
-- ===========
 
esRelacionBinaria2 :: Eq a => Rel a -> Bool
esRelacionBinaria2 (R (u, g)) =
  all (\(x,y) -> x `elem` u && y `elem` u) g
 
-- 3ª solución
-- ===========
 
esRelacionBinaria3 :: Eq a => Rel a -> Bool
esRelacionBinaria3 (R (_, []))         = True
esRelacionBinaria3 (R (u, (x,y):g)) =
  x `elem` u &&
  y `elem` u &&
  esRelacionBinaria3 (R (u, g))
 
-- Comprobación de equivalencia
-- ============================
 
-- Generador de relaciones binarias. Por ejemplo,
--    λ> sample (relacionArbitraria :: Gen (Rel Int))
--    R ([0],[])
--    R ([0,-1,1],[(0,-1),(0,1),(-1,1),(1,0)])
--    R ([1],[])
--    R ([-5,3],[(-5,-5),(-5,3),(3,-5),(3,3)])
--    R ([-2,-7],[(-7,-7)])
--    R ([11,-7],[])
--    R ([0],[])
--    R ([-13,-11],[(-13,-13)])
relacionArbitraria :: (Arbitrary a, Eq a) => Gen (Rel a)
relacionArbitraria = do
  n <- choose (0, 10)
  u1 <- vectorOf n arbitrary
  let u = nub u1
  g <- sublistOf [(x,y) | x <- u, y <- u]
  return (R (u, g))
 
-- Relaciones es una subclase de Arbitrary.
instance (Arbitrary a, Eq a) => Arbitrary (Rel a) where
  arbitrary = relacionArbitraria
 
-- La propiedad es
prop_esRelacionBinaria :: Rel Int -> Bool
prop_esRelacionBinaria r =
  esRelacionBinaria r  &&
  esRelacionBinaria2 r &&
  esRelacionBinaria3 r
 
-- La comprobación es
--    λ> quickCheck prop_esRelacionBinaria
--    +++ OK, passed 100 tests.


Soluciones en Python

from random import choice, randint, sample
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
A = TypeVar('A')
 
Rel = tuple[list[A], list[tuple[A, A]]]
 
# 1ª solución
# ===========
 
def esRelacionBinaria(r: Rel[A]) -> bool:
    (u, g) = r
    return all((x in u and y in u for (x, y) in g))
 
# 2ª solución
# ===========
 
def esRelacionBinaria2(r: Rel[A]) -> bool:
    (u, g) = r
    if not g:
        return True
    (x, y) = g[0]
    return x in u and y in u and esRelacionBinaria2((u, g[1:]))
 
# 3ª solución
# ===========
 
def esRelacionBinaria3(r: Rel[A]) -> bool:
    (u, g) = r
    for (x, y) in g:
        if x not in u or y not in u:
            return False
    return True
 
# Generador de relaciones binarias
# ================================
 
# conjuntoArbitrario(n) es un conjunto arbitrario cuyos elementos están
# entre 0 y n-1. Por ejemplo,
#    >>> conjuntoArbitrario(10)
#    [8, 9, 4, 5]
#    >>> conjuntoArbitrario(10)
#    [1, 2, 3, 4, 5, 6, 7, 8, 9]
#    >>> conjuntoArbitrario(10)
#    [0, 1, 2, 3, 6, 7, 9]
#    >>> conjuntoArbitrario(10)
#    [8, 2, 3, 7]
def conjuntoArbitrario(n: int) -> list[int]:
    xs = sample(range(n), randint(0, n))
    return list(set(xs))
 
# productoCartesiano(xs, ys) es el producto cartesiano de xs e ys. Por
# ejemplo,
#    >>> productoCartesiano([2, 3], [1, 7, 5])
#    [(2, 1), (2, 7), (2, 5), (3, 1), (3, 7), (3, 5)]
def productoCartesiano(xs: list[int], ys: list[int]) -> list[tuple[int, int]]:
    return [(x, y) for x in xs for y in ys]
 
# sublistaArbitraria(xs) es una sublista arbitraria de xs. Por ejemplo,
#    >>> sublistaArbitraria(range(10))
#    [3, 7]
#    >>> sublistaArbitraria(range(10))
#    []
#    >>> sublistaArbitraria(range(10))
#    [4, 1, 0, 9, 8, 7, 5, 6, 2, 3]
def sublistaArbitraria(xs: list[A]) -> list[A]:
    n = len(xs)
    k = randint(0, n)
    return sample(xs, k)
 
# relacionArbitraria(n) es una relación arbitraria tal que los elementos
# de su universo están entre 0 y n-1. Por ejemplo,
#    >>> relacionArbitraria(3)
#    ([0, 1], [(1, 0), (1, 1)])
#    >>> relacionArbitraria(3)
#    ([], [])
#    >>> relacionArbitraria(5)
#    ([0, 2, 3, 4], [(2, 0), (3, 3), (2, 3), (4, 0), (3, 4), (4, 2)])
def relacionArbitraria(n: int) -> Rel[int]:
    u = conjuntoArbitrario(n)
    g = sublistaArbitraria(productoCartesiano(u, u))
    return (u, g)
 
# Comprobación de la propiedad
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_esRelacionBinaria(n: int) -> None:
    r = relacionArbitraria(n)
    assert esRelacionBinaria(r)
    assert esRelacionBinaria2(r)
    assert esRelacionBinaria3(r)
 
# La comprobación es
#    > poetry run pytest -q Relaciones_binarias.py
#    1 passed in 0.14s
Leer más →

TAD de los conjuntos: Producto cartesiano de dos conjuntos

José A. Alonso, ,

Utilizando el tipo abstracto de datos de los conjuntos (https://bit.ly/3HbB7fo) definir la función

   productoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)

tal que productoC c1 c2 es el producto cartesiano de los conjuntos c1 y c2. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 5 vacio)
   λ> ej2 = inserta 9 (inserta 4 (inserta 3 vacio))
   λ> productoC ej1 ej2
   {(2,3), (2,4), (2,9), (5,3), (5,4), (5,9)}

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import TAD_Union_de_dos_conjuntos (union)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
productoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)
productoC c1 c2
  | esVacio c1 = vacio
  | otherwise  = agrega mc1 c2 `union` productoC rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1
 
-- (agrega x c) es el conjunto de los pares de x con los elementos de
-- c. Por ejemplo,
--    λ> agrega 2 (inserta 9 (inserta 4 (inserta 3 vacio)))
--    {(2,3), (2,4), (2,9)}
agrega :: (Ord a, Ord b) => a -> Conj b -> Conj (a,b)
agrega x c
  | esVacio c = vacio
  | otherwise = inserta (x, mc) (agrega x rc)
  where mc = menor c
        rc = elimina mc c
 
-- La función union está definida en el ejercicio
-- "Unión de dos conjuntos" que se encuentra en
-- https://bit.ly/3Y1jBl8
 
-- 2ª solución
-- ===========
 
productoC2 :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)
productoC2 c1 c2 =
  foldr inserta vacio [(x,y) | x <- xs, y <- ys]
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2
 
-- 3ª solución
-- ===========
 
productoC3 :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)
productoC3 c1 c2 =
  listaAconjunto [(x,y) | x <- xs, y <- ys]
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_productoC :: Conj Int -> Conj Int -> Bool
prop_productoC c1 c2 =
  all (== productoC c1 c2)
      [productoC2 c1 c2,
       productoC3 c1 c2]
 
-- La comprobación es
--    λ> quickCheck prop_productoC
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from copy import deepcopy
from functools import reduce
from typing import Protocol, TypeVar
 
from hypothesis import given
 
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, vacio)
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)
from src.TAD_Union_de_dos_conjuntos import union
 
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
B = TypeVar('B', bound=Comparable)
 
# 1ª solución
# ===========
 
# (agrega x c) es el conjunto de los pares de x con los elementos de
# c. Por ejemplo,
#    >>> agrega(2, inserta(9, inserta(4, inserta(3, vacio()))))
#    {(2, 3), (2, 4), (2, 9)}
def agrega(x: A, c: Conj[B]) -> Conj[tuple[A, B]]:
    if esVacio(c):
        return vacio()
    mc = menor(c)
    rc = elimina(mc, c)
    return inserta((x, mc), agrega(x, rc))
 
def productoC(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]:
    if esVacio(c1):
        return vacio()
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    return union(agrega(mc1, c2), productoC(rc1, c2))
 
# La función union está definida en el ejercicio
# "Unión de dos conjuntos" que se encuentra en
# https://bit.ly/3Y1jBl8
 
# 2ª solución
# ===========
 
def productoC2(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return reduce(lambda bs, a: inserta(a, bs), [(x,y) for x in xs for y in ys], vacio())
 
# 3ª solución
# ===========
 
def productoC3(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return listaAconjunto([(x,y) for x in xs for y in ys])
 
# 4ª solución
# ===========
 
def agrega4Aux(x: A, c: Conj[B]) -> Conj[tuple[A, B]]:
    r: Conj[tuple[A, B]] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        r = inserta((x, mc), r)
    return r
 
def agrega4(x: A, c: Conj[B]) -> Conj[tuple[A, B]]:
    _c = deepcopy(c)
    return agrega4Aux(x, _c)
 
def productoC4(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]:
    r: Conj[tuple[A, B]] = vacio()
    while not esVacio(c1):
        mc1 = menor(c1)
        c1 = elimina(mc1, c1)
        r = union(agrega4(mc1, c2), r)
    return r
 
# 5ª solución
# ===========
 
def agrega5Aux(x: A, c: Conj[B]) -> Conj[tuple[A, B]]:
    r: Conj[tuple[A, B]] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        r.inserta((x, mc))
    return r
 
def agrega5(x: A, c: Conj[B]) -> Conj[tuple[A, B]]:
    _c = deepcopy(c)
    return agrega5Aux(x, _c)
 
def productoC5(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]:
    r: Conj[tuple[A, B]] = Conj()
    while not c1.esVacio():
        mc1 = c1.menor()
        c1.elimina(mc1)
        r = union(agrega5(mc1, c2), r)
    return r
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_productoC(c1: Conj[int], c2: Conj[int]) -> None:
    r = productoC(c1, c2)
    assert productoC2(c1, c2) == r
    assert productoC3(c1, c2) == r
    assert productoC4(c1, c2) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Producto_cartesiano.py
#    1 passed in 0.35s
Leer más →

TAD de los conjuntos: Algunos elementos verifican una propiedad

José A. Alonso, ,

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   algunos :: Ord a => (a -> Bool) -> Conj a -> Bool

tal que algunos p c se verifica si algún elemento de c verifica el predicado p. Por ejemplo,

   algunos even (inserta 4 (inserta 7 vacio))  ==  True
   algunos even (inserta 3 (inserta 7 vacio))  ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Test.QuickCheck.HigherOrder
 
-- 1ª solución
-- ===========
 
algunos :: Ord a => (a -> Bool) -> Conj a -> Bool
algunos p c
  | esVacio c = False
  | otherwise = p mc || algunos p rc
  where mc = menor c
        rc = elimina mc c
 
-- 2ª solución
-- ===========
 
algunos2 :: Ord a => (a -> Bool) -> Conj a -> Bool
algunos2 p c = any p (conjuntoAlista c)
 
-- La función conjuntoAlista está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra
-- en https://bit.ly/3RexzxH
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_algunos :: (Int -> Bool) -> [Int] -> Bool
prop_algunos p xs =
  algunos p c == algunos2 p c
  where c = listaAconjunto xs
 
-- La comprobación es
--    λ> quickCheck' prop_algunos
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from copy import deepcopy
from typing import Callable, Protocol, TypeVar
 
from hypothesis import given
 
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, vacio)
from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def algunos(p: Callable[[A], bool], c: Conj[A]) -> bool:
    if esVacio(c):
        return False
    mc = menor(c)
    rc = elimina(mc, c)
    return p(mc) or algunos(p, rc)
 
# 2ª solución
# ===========
 
def algunos2(p: Callable[[A], bool], c: Conj[A]) -> bool:
    return any(p(x) for x in conjuntoAlista(c))
 
# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra
# en https://bit.ly/3RexzxH
 
# 3ª solución
# ===========
 
def algunos3Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if p(mc):
            return True
    return False
 
def algunos3(p: Callable[[A], bool], c: Conj[A]) -> bool:
    _c = deepcopy(c)
    return algunos3Aux(p, _c)
 
# 4ª solución
# ===========
 
def algunos4Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if p(mc):
            return True
    return False
 
def algunos4(p: Callable[[A], bool], c: Conj[A]) -> bool:
    _c = deepcopy(c)
    return algunos4Aux(p, _c)
 
# Comprobación de equivalencia de las definiciones
# ================================================
 
# La propiedad es
@given(c=conjuntoAleatorio())
def test_algunos(c: Conj[int]) -> None:
    r = algunos(lambda x: x % 2 == 0, c)
    assert algunos2(lambda x: x % 2 == 0, c) == r
    assert algunos3(lambda x: x % 2 == 0, c) == r
    assert algunos4(lambda x: x % 2 == 0, c) == r
 
# La comprobación es
#    src> poetry run pytest -q TAD_AlgunosVerificanConj.py
#    1 passed in 0.28s
Leer más →