marzo 2023 – Exercitium

Relaciones simétricas

PorJosé A. Alonso 31-marzo-202310-marzo-2023

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

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

1	simetrica :: Eq a => Rel a -> Bool

tal que simetrica r se verifica si la relación r es simétrica. Por ejemplo,

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

simetrica (R ([1,3],[(1,1),(1,3),(3,1)])) == True

simetrica (R ([1,3],[(1,1),(1,3),(3,2)])) == False

simetrica (R ([1,3],[])) == True

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck

-- 1ª solución
-- ===========

simetrica :: Eq a => Rel a -> Bool
simetrica (R (_,g)) = and [(y,x) `elem` g | (x,y) <- g]

-- 2ª solución
-- ===========

simetrica2 :: Eq a => Rel a -> Bool
simetrica2 (R (_,g)) = all (\(x,y) -> (y,x) `elem` g) g

-- 3ª solución
-- ===========

simetrica3 :: Eq a => Rel a -> Bool
simetrica3 (R (_,g)) = aux g
  where aux [] = True
        aux ((x,y):ps) = (y,x) `elem` g && aux ps

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_simetrica :: Rel Int -> Bool
prop_simetrica r =
  all (== simetrica r)
      [simetrica2 r,
       simetrica3 r]

-- La comprobación es
--    λ> quickCheck prop_simetrica
--    +++ OK, passed 100 tests.

import Relaciones_binarias (Rel(R))

import Test.QuickCheck

-- 1ª solución

-- ===========

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

simetrica (R (_,g)) = and [(y,x) `elem` g | (x,y) <- g]

-- 2ª solución

-- ===========

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

simetrica2 (R (_,g)) = all (\(x,y) -> (y,x) `elem` g) g

-- 3ª solución

-- ===========

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

simetrica3 (R (_,g)) = aux g

where aux [] = True

aux ((x,y):ps) = (y,x) `elem` g && aux ps

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_simetrica :: Rel Int -> Bool

prop_simetrica r =

all (== simetrica r)

[simetrica2 r,

simetrica3 r]

-- La comprobación es

-- λ> quickCheck prop_simetrica

-- +++ OK, passed 100 tests.

Soluciones en Python

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 simetrica(r: Rel[A]) -> bool:
    (_, g) = r
    return all(((y, x) in g for (x, y) in g))

# 2ª solución
# ===========

def simetrica2(r: Rel[A]) -> bool:
    (_, g) = r
    def aux(ps: list[tuple[A, A]]) -> bool:
        if not ps:
            return True
        (x, y) = ps[0]
        return (y, x) in g and aux(ps[1:])

    return aux(g)

# 3ª solución
# ===========

def simetrica3(r: Rel[A]) -> bool:
    (_, g) = r
    for (x, y) in g:
        if (y, x) not in g:
            return False
    return True

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_simetrica(n: int) -> None:
    r = relacionArbitraria(n)
    res = simetrica(r)
    assert simetrica2(r) == res
    assert simetrica3(r) == res

# La comprobación es
#    > poetry run pytest -q Relaciones_simetricas.py
#    1 passed in 0.11s

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 simetrica(r: Rel[A]) -> bool:

(_, g) = r

return all(((y, x) in g for (x, y) in g))

# 2ª solución

# ===========

def simetrica2(r: Rel[A]) -> bool:

(_, g) = r

def aux(ps: list[tuple[A, A]]) -> bool:

if not ps:

return True

(x, y) = ps[0]

return (y, x) in g and aux(ps[1:])

return aux(g)

# 3ª solución

# ===========

def simetrica3(r: Rel[A]) -> bool:

(_, g) = r

for (x, y) in g:

if (y, x) not in g:

return False

return True

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=0, max_value=10))

def test_simetrica(n: int) -> None:

r = relacionArbitraria(n)

res = simetrica(r)

assert simetrica2(r) == res

assert simetrica3(r) == res

# La comprobación es

# > poetry run pytest -q Relaciones_simetricas.py

# 1 passed in 0.11s

Relaciones reflexivas

PorJosé A. Alonso 30-marzo-20239-marzo-2023

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

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

1	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

1 2	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.

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

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

Universo y grafo de una relación binaria

PorJosé A. Alonso 29-marzo-20236-marzo-2023

Usando el tipo de las relaciones binarias, definir las funciones

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

1 2	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]

λ> 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)]

1 2	λ> 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

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]

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]

Relaciones binarias

PorJosé A. Alonso 28-marzo-202311-marzo-2023

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

1	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

λ> 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.

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

100

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

TAD de los conjuntos: Producto cartesiano de dos conjuntos

PorJosé A. Alonso 27-marzo-20233-marzo-2023

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)

1	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)}

λ> 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.

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

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

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

TAD de los conjuntos: Algunos elementos verifican una propiedad

PorJosé A. Alonso 24-marzo-202322-febrero-2023

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

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

1	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

1 2	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.

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

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

TAD de los conjuntos: Todos los elementos verifican una propiedad

PorJosé A. Alonso 23-marzo-202322-febrero-2023

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

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

1	todos :: Ord a => (a -> Bool) -> Conj a -> Bool

tal que todos p c se verifica si todos los elemsntos de c verifican el predicado p. Por ejemplo,

   todos even (inserta 4 (inserta 6 vacio))  ==  True
   todos even (inserta 4 (inserta 7 vacio))  ==  False

1 2	todos even (inserta 4 (inserta 6 vacio)) == True todos even (inserta 4 (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
-- ===========

todos :: Ord a => (a -> Bool) -> Conj a -> Bool
todos p c
  | esVacio c = True
  | otherwise = p mc && todos p rc
  where mc = menor c
        rc = elimina mc c

-- 2ª solución
-- ===========

todos2 :: Ord a => (a -> Bool) -> Conj a -> Bool
todos2 p c = all 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_todos :: (Int -> Bool) -> [Int] -> Bool
prop_todos p xs =
  todos p c == todos2 p c
  where c = listaAconjunto xs

-- La comprobación es
--    λ> quickCheck' prop_todos
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Test.QuickCheck.HigherOrder

-- 1ª solución

-- ===========

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

todos p c

| esVacio c = True

| otherwise = p mc && todos p rc

where mc = menor c

rc = elimina mc c

-- 2ª solución

-- ===========

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

todos2 p c = all 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_todos :: (Int -> Bool) -> [Int] -> Bool

prop_todos p xs =

todos p c == todos2 p c

where c = listaAconjunto xs

-- La comprobación es

-- λ> quickCheck' prop_todos

-- +++ 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 todos(p: Callable[[A], bool], c: Conj[A]) -> bool:
    if esVacio(c):
        return True
    mc = menor(c)
    rc = elimina(mc, c)
    return p(mc) and todos(p, rc)

# 2ª solución
# ===========

def todos2(p: Callable[[A], bool], c: Conj[A]) -> bool:
    return all(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 todos3Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if not p(mc):
            return False
    return True

def todos3(p: Callable[[A], bool], c: Conj[A]) -> bool:
    _c = deepcopy(c)
    return todos3Aux(p, _c)

# 4ª solución
# ===========

def todos4Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if not p(mc):
            return False
    return True

def todos4(p: Callable[[A], bool], c: Conj[A]) -> bool:
    _c = deepcopy(c)
    return todos4Aux(p, _c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(c=conjuntoAleatorio())
def test_todos(c: Conj[int]) -> None:
    r = todos(lambda x: x % 2 == 0, c)
    assert todos2(lambda x: x % 2 == 0, c) == r
    assert todos3(lambda x: x % 2 == 0, c) == r
    assert todos4(lambda x: x % 2 == 0, c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_TodosVerificanConj.py
#    1 passed in 0.28s

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 todos(p: Callable[[A], bool], c: Conj[A]) -> bool:

if esVacio(c):

return True

mc = menor(c)

rc = elimina(mc, c)

return p(mc) and todos(p, rc)

# 2ª solución

# ===========

def todos2(p: Callable[[A], bool], c: Conj[A]) -> bool:

return all(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 todos3Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:

while not esVacio(c):

mc = menor(c)

c = elimina(mc, c)

if not p(mc):

return False

return True

def todos3(p: Callable[[A], bool], c: Conj[A]) -> bool:

_c = deepcopy(c)

return todos3Aux(p, _c)

# 4ª solución

# ===========

def todos4Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:

while not c.esVacio():

mc = c.menor()

c.elimina(mc)

if not p(mc):

return False

return True

def todos4(p: Callable[[A], bool], c: Conj[A]) -> bool:

_c = deepcopy(c)

return todos4Aux(p, _c)

# Comprobación de equivalencia de las definiciones

# ================================================

# La propiedad es

@given(c=conjuntoAleatorio())

def test_todos(c: Conj[int]) -> None:

r = todos(lambda x: x % 2 == 0, c)

assert todos2(lambda x: x % 2 == 0, c) == r

assert todos3(lambda x: x % 2 == 0, c) == r

assert todos4(lambda x: x % 2 == 0, c) == r

# La comprobación es

# src> poetry run pytest -q TAD_TodosVerificanConj.py

# 1 passed in 0.28s

TAD de los conjuntos: Aplicación de una función a los elementos de un conjunto

PorJosé A. Alonso 22-marzo-202322-febrero-2023

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

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

1	mapC :: (Ord a, Ord b) => (a -> b) -> Conj a -> Conj b

tal que map f c es el conjunto formado por las imágenes de los elementos del conjunto c, mediante la aplicación f. Por ejemplo,

   λ> mapC (*2) (inserta 3 (inserta 1 vacio))
   {2, 6}

1 2	λ> mapC (*2) (inserta 3 (inserta 1 vacio)) {2, 6}

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
-- ===========

mapC :: (Ord a, Ord b) => (a -> b) -> Conj a -> Conj b
mapC f c
  | esVacio c = vacio
  | otherwise = inserta (f mc) (mapC f rc)
  where mc = menor c
        rc = elimina mc c

-- 2ª solución
-- ===========

mapC2 :: (Ord a, Ord b) => (a -> b) -> Conj a -> Conj b
mapC2 f c = listaAconjunto (map f (conjuntoAlista c))

-- Las funciones conjuntoAlista y listaAconjunto 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_mapC :: (Int -> Int) -> [Int] -> Bool
prop_mapC f xs =
  mapC f c == mapC2 f c
  where c = listaAconjunto xs

-- La comprobación es
--    λ> quickCheck' prop_mapC
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Test.QuickCheck.HigherOrder

-- 1ª solución

-- ===========

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

mapC f c

| esVacio c = vacio

| otherwise = inserta (f mc) (mapC f rc)

where mc = menor c

rc = elimina mc c

-- 2ª solución

-- ===========

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

mapC2 f c = listaAconjunto (map f (conjuntoAlista c))

-- Las funciones conjuntoAlista y listaAconjunto 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_mapC :: (Int -> Int) -> [Int] -> Bool

prop_mapC f xs =

mapC f c == mapC2 f c

where c = listaAconjunto xs

-- La comprobación es

-- λ> quickCheck' prop_mapC

-- +++ 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,
                                                       listaAconjunto)

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
# ===========

def mapC(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    if esVacio(c):
        return vacio()
    mc = menor(c)
    rc = elimina(mc, c)
    return inserta(f(mc), mapC(f, rc))

# 2ª solución
# ===========

def mapC2(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    return listaAconjunto(list(map(f, conjuntoAlista(c))))

# Las funciones conjuntoAlista y listaAconjunto está definida en el
# ejercicio Transformaciones entre conjuntos y listas" que se encuentra
# en https://bit.ly/3RexzxH

# 3ª solución
# ===========

def mapC3Aux(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    r: Conj[B] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        r = inserta(f(mc), r)
    return r

def mapC3(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    _c = deepcopy(c)
    return mapC3Aux(f, _c)

# 4ª solución
# ===========

def mapC4Aux(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    r: Conj[B] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        r.inserta(f(mc))
    return r

def mapC4(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    _c = deepcopy(c)
    return mapC4Aux(f, _c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(c=conjuntoAleatorio())
def test_mapPila(c: Conj[int]) -> None:
    r = mapC(lambda x: 2 * x, c)
    assert mapC2(lambda x: 2 * x, c) == r
    assert mapC3(lambda x: 2 * x, c) == r
    assert mapC4(lambda x: 2 * x, c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_mapC.py
#    1 passed in 0.29s

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,

listaAconjunto)

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

# ===========

def mapC(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:

if esVacio(c):

return vacio()

mc = menor(c)

rc = elimina(mc, c)

return inserta(f(mc), mapC(f, rc))

# 2ª solución

# ===========

def mapC2(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:

return listaAconjunto(list(map(f, conjuntoAlista(c))))

# Las funciones conjuntoAlista y listaAconjunto está definida en el

# ejercicio Transformaciones entre conjuntos y listas" que se encuentra

# en https://bit.ly/3RexzxH

# 3ª solución

# ===========

def mapC3Aux(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:

r: Conj[B] = vacio()

while not esVacio(c):

mc = menor(c)

c = elimina(mc, c)

r = inserta(f(mc), r)

return r

def mapC3(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:

_c = deepcopy(c)

return mapC3Aux(f, _c)

# 4ª solución

# ===========

def mapC4Aux(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:

r: Conj[B] = Conj()

while not c.esVacio():

mc = c.menor()

c.elimina(mc)

r.inserta(f(mc))

return r

def mapC4(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:

_c = deepcopy(c)

return mapC4Aux(f, _c)

# Comprobación de equivalencia de las definiciones

# ================================================

# La propiedad es

@given(c=conjuntoAleatorio())

def test_mapPila(c: Conj[int]) -> None:

r = mapC(lambda x: 2 * x, c)

assert mapC2(lambda x: 2 * x, c) == r

assert mapC3(lambda x: 2 * x, c) == r

assert mapC4(lambda x: 2 * x, c) == r

# La comprobación es

# src> poetry run pytest -q TAD_mapC.py

# 1 passed in 0.29s

TAD de los conjuntos: Partición según un número

PorJosé A. Alonso 21-marzo-202322-febrero-2023

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

   divide :: (Ord a) => a-> Conj a -> (Conj a, Conj a)

1	divide :: (Ord a) => a-> Conj a -> (Conj a, Conj a)

tal que divide x c es el par formado por dos subconjuntos de c: el de los elementos menores o iguales que x y el de los mayores que x. Por ejemplo,

   λ> divide 5 (inserta 7 (inserta 2 (inserta 8 vacio)))
   ({2},{7, 8})

1 2	λ> divide 5 (inserta 7 (inserta 2 (inserta 8 vacio))) ({2},{7, 8})

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_Particion_por_una_propiedad (particion)
import Test.QuickCheck

-- 1ª solución
-- ===========

divide :: Ord a => a-> Conj a -> (Conj a, Conj a)
divide x c
  | esVacio c = (vacio, vacio)
  | mc <= x   = (inserta mc c1, c2)
  | otherwise = (c1, inserta mc c2)
  where
    mc       = menor c
    rc       = elimina mc c
    (c1, c2) = divide x rc

-- 2ª solución
-- ===========

divide2 :: Ord a => a-> Conj a -> (Conj a, Conj a)
divide2 x = particion (<= x)

-- La función particion está definida en el ejercicio
-- "Partición de un conjunto según una propiedad" que se encuentra en
-- https://bit.ly/3YCOah5

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_divide :: Int -> Conj Int -> Bool
prop_divide x c =
  divide x c == divide2 x c

-- La comprobación es
--    λ> quickCheck prop_divide
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)

import TAD_Particion_por_una_propiedad (particion)

import Test.QuickCheck

-- 1ª solución

-- ===========

divide :: Ord a => a-> Conj a -> (Conj a, Conj a)

divide x c

| esVacio c = (vacio, vacio)

| mc <= x = (inserta mc c1, c2)

| otherwise = (c1, inserta mc c2)

where

mc = menor c

rc = elimina mc c

(c1, c2) = divide x rc

-- 2ª solución

-- ===========

divide2 :: Ord a => a-> Conj a -> (Conj a, Conj a)

divide2 x = particion (<= x)

-- La función particion está definida en el ejercicio

-- "Partición de un conjunto según una propiedad" que se encuentra en

-- https://bit.ly/3YCOah5

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_divide :: Int -> Conj Int -> Bool

prop_divide x c =

divide x c == divide2 x c

-- La comprobación es

-- λ> quickCheck prop_divide

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, vacio)
from src.TAD_Particion_por_una_propiedad import particion

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def divide(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    if esVacio(c):
        return (vacio(), vacio())
    mc = menor(c)
    rc = elimina(mc, c)
    (c1, c2) = divide(x, rc)
    if mc <= x:
        return (inserta(mc, c1), c2)
    return (c1, inserta(mc, c2))

# 2ª solución
# ===========

def divide2(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    return particion(lambda y: y <= x, c)

# La función particion está definida en el ejercicio
# "Partición de un conjunto según una propiedad" que se encuentra en
# https://bit.ly/3YCOah5

# 3ª solución
# ===========

def divide3Aux(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    r: Conj[A] = vacio()
    s: Conj[A] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if mc <= x:
            r = inserta(mc, r)
        else:
            s = inserta(mc, s)
    return (r, s)

def divide3(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    _c = deepcopy(c)
    return divide3Aux(x, _c)

# 4ª solución
# ===========

def divide4Aux(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    r: Conj[A] = Conj()
    s: Conj[A] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if mc <= x:
            r.inserta(mc)
        else:
            s.inserta(mc)
    return (r, s)

def divide4(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    _c = deepcopy(c)
    return divide4Aux(x, _c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(x=st.integers(), c=conjuntoAleatorio())
def test_particion(x: int, c: Conj[int]) -> None:
    r = divide(x, c)
    assert divide2(x, c) == r
    assert divide3(x, c) == r
    assert divide4(x, c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_Particion_segun_un_numero.py
#    1 passed in 0.30s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, vacio)

from src.TAD_Particion_por_una_propiedad import particion

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def divide(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

if esVacio(c):

return (vacio(), vacio())

mc = menor(c)

rc = elimina(mc, c)

(c1, c2) = divide(x, rc)

if mc <= x:

return (inserta(mc, c1), c2)

return (c1, inserta(mc, c2))

# 2ª solución

# ===========

def divide2(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

return particion(lambda y: y <= x, c)

# La función particion está definida en el ejercicio

# "Partición de un conjunto según una propiedad" que se encuentra en

# https://bit.ly/3YCOah5

# 3ª solución

# ===========

def divide3Aux(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

r: Conj[A] = vacio()

s: Conj[A] = vacio()

while not esVacio(c):

mc = menor(c)

c = elimina(mc, c)

if mc <= x:

r = inserta(mc, r)

else:

s = inserta(mc, s)

return (r, s)

def divide3(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

_c = deepcopy(c)

return divide3Aux(x, _c)

# 4ª solución

# ===========

def divide4Aux(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

r: Conj[A] = Conj()

s: Conj[A] = Conj()

while not c.esVacio():

mc = c.menor()

c.elimina(mc)

if mc <= x:

r.inserta(mc)

else:

s.inserta(mc)

return (r, s)

def divide4(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

_c = deepcopy(c)

return divide4Aux(x, _c)

# Comprobación de equivalencia de las definiciones

# ================================================

# La propiedad es

@given(x=st.integers(), c=conjuntoAleatorio())

def test_particion(x: int, c: Conj[int]) -> None:

r = divide(x, c)

assert divide2(x, c) == r

assert divide3(x, c) == r

assert divide4(x, c) == r

# La comprobación es

# src> poetry run pytest -q TAD_Particion_segun_un_numero.py

# 1 passed in 0.30s

TAD de los conjuntos: Partición de un conjunto según una propiedad

PorJosé A. Alonso 20-marzo-202322-febrero-2023

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

   particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)

1	particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)

tal que particion c es el par formado por dos conjuntos: el de los elementos de c que verifican p y el de los elementos que no lo verifican. Por ejemplo,

   λ> ej = inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))
   λ> particion even ej
   ({2, 4},{5, 7})

λ> ej = inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))

λ> particion even ej

({2, 4},{5, 7})

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import TAD_Subconjunto_por_propiedad (filtra)
import Data.List (partition)
import Test.QuickCheck.HigherOrder

-- 1ª solución
-- ===========

particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)
particion p c = (filtra p c, filtra (not . p) c)

-- La función filtra está definida en el ejercicio
-- "Subconjunto determinado por una propiedad" que se encuentra en
-- https://bit.ly/3lplFoV

-- 2ª solución
-- ===========

particion2 :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)
particion2 p c = (listaAconjunto xs, listaAconjunto ys)
  where
    (xs, ys) = partition p (conjuntoAlista c)

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_particion :: (Int -> Bool) -> [Int] -> Bool
prop_particion p xs =
  particion p c == particion2 p c
  where c = listaAconjunto xs

-- La comprobación es
--    λ> quickCheck' prop_particion
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import TAD_Subconjunto_por_propiedad (filtra)

import Data.List (partition)

import Test.QuickCheck.HigherOrder

-- 1ª solución

-- ===========

particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)

particion p c = (filtra p c, filtra (not . p) c)

-- La función filtra está definida en el ejercicio

-- "Subconjunto determinado por una propiedad" que se encuentra en

-- https://bit.ly/3lplFoV

-- 2ª solución

-- ===========

particion2 :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)

particion2 p c = (listaAconjunto xs, listaAconjunto ys)

where

(xs, ys) = partition p (conjuntoAlista c)

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_particion :: (Int -> Bool) -> [Int] -> Bool

prop_particion p xs =

particion p c == particion2 p c

where c = listaAconjunto xs

-- La comprobación es

-- λ> quickCheck' prop_particion

-- +++ 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_Subconjunto_por_propiedad import filtra

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def particion(p: Callable[[A], bool],
              c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    return (filtra(p, c), filtra(lambda x: not p(x), c))

# La función filtra está definida en el ejercicio
# "Subconjunto determinado por una propiedad" que se encuentra en
# https://bit.ly/3lplFoV

# 2ª solución
# ===========

def particion2Aux(p: Callable[[A], bool],
                  c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    r: Conj[A] = vacio()
    s: Conj[A] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if p(mc):
            r = inserta(mc, r)
        else:
            s = inserta(mc, s)
    return (r, s)

def particion2(p: Callable[[A], bool],
               c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    _c = deepcopy(c)
    return particion2Aux(p, _c)

# 3ª solución
# ===========

def particion3Aux(p: Callable[[A], bool],
                  c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    r: Conj[A] = Conj()
    s: Conj[A] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if p(mc):
            r.inserta(mc)
        else:
            s.inserta(mc)
    return (r, s)

def particion3(p: Callable[[A], bool],
               c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    _c = deepcopy(c)
    return particion3Aux(p, _c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(c=conjuntoAleatorio())
def test_particion(c: Conj[int]) -> None:
    r = particion(lambda x: x % 2 == 0, c)
    assert particion2(lambda x: x % 2 == 0, c) == r
    assert particion3(lambda x: x % 2 == 0, c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_Particion_por_una_propiedad.py
#    1 passed in 0.28s

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_Subconjunto_por_propiedad import filtra

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def particion(p: Callable[[A], bool],

c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

return (filtra(p, c), filtra(lambda x: not p(x), c))

# La función filtra está definida en el ejercicio

# "Subconjunto determinado por una propiedad" que se encuentra en

# https://bit.ly/3lplFoV

# 2ª solución

# ===========

def particion2Aux(p: Callable[[A], bool],

c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

r: Conj[A] = vacio()

s: Conj[A] = vacio()

while not esVacio(c):

mc = menor(c)

c = elimina(mc, c)

if p(mc):

r = inserta(mc, r)

else:

s = inserta(mc, s)

return (r, s)

def particion2(p: Callable[[A], bool],

c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

_c = deepcopy(c)

return particion2Aux(p, _c)

# 3ª solución

# ===========

def particion3Aux(p: Callable[[A], bool],

c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

r: Conj[A] = Conj()

s: Conj[A] = Conj()

while not c.esVacio():

mc = c.menor()

c.elimina(mc)

if p(mc):

r.inserta(mc)

else:

s.inserta(mc)

return (r, s)

def particion3(p: Callable[[A], bool],

c: Conj[A]) -> tuple[Conj[A], Conj[A]]:

_c = deepcopy(c)

return particion3Aux(p, _c)

# Comprobación de equivalencia de las definiciones

# ================================================

# La propiedad es

@given(c=conjuntoAleatorio())

def test_particion(c: Conj[int]) -> None:

r = particion(lambda x: x % 2 == 0, c)

assert particion2(lambda x: x % 2 == 0, c) == r

assert particion3(lambda x: x % 2 == 0, c) == r

# La comprobación es

# src> poetry run pytest -q TAD_Particion_por_una_propiedad.py

# 1 passed in 0.28s

TAD de los conjuntos: Subconjunto determinado por una propiedad

PorJosé A. Alonso 17-marzo-202322-febrero-2023

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

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

1	filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a

tal filtra p c es el conjunto de elementos de c que verifican el predicado p. Por ejemplo,

   λ> filtra even (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {2, 4}
   λ> filtra odd (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {5, 7}

λ> filtra even (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))

{2, 4}

λ> filtra odd (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))

{5, 7}

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
-- ===========

filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a
filtra p c
  | esVacio c = vacio
  | p mc      = inserta mc (filtra p rc)
  | otherwise = filtra p rc
  where mc = menor c
        rc = elimina mc c

-- 2ª solución
-- ===========

filtra2 :: Ord a => (a -> Bool) -> Conj a -> Conj a
filtra2 p c =
  listaAconjunto (filter p (conjuntoAlista c))

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_filtra :: (Int -> Bool) -> [Int] -> Bool
prop_filtra p xs =
  filtra p c == filtra2 p c
  where c = listaAconjunto xs

-- La comprobación es
--    λ> quickCheck' prop_filtra
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Test.QuickCheck.HigherOrder

-- 1ª solución

-- ===========

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

filtra p c

| esVacio c = vacio

| p mc = inserta mc (filtra p rc)

| otherwise = filtra p rc

where mc = menor c

rc = elimina mc c

-- 2ª solución

-- ===========

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

filtra2 p c =

listaAconjunto (filter p (conjuntoAlista c))

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_filtra :: (Int -> Bool) -> [Int] -> Bool

prop_filtra p xs =

filtra p c == filtra2 p c

where c = listaAconjunto xs

-- La comprobación es

-- λ> quickCheck' prop_filtra

-- +++ 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, pertenece, vacio)
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def filtra(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    if esVacio(c):
        return vacio()
    mc = menor(c)
    rc = elimina(mc, c)
    if p(mc):
        return inserta(mc, filtra(p, rc))
    return filtra(p, rc)

# 2ª solución
# ===========

def filtra2(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    return listaAconjunto(list(filter(p, conjuntoAlista(c))))

# 3ª solución
# ===========

def filtra3Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if p(mc):
            r = inserta(mc, r)
    return r

def filtra3(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    _c = deepcopy(c)
    return filtra3Aux(p, _c)

# 4ª solución
# ===========

def filtra4Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    r: Conj[A] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if p(mc):
            r.inserta(mc)
    return r

def filtra4(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    _c = deepcopy(c)
    return filtra4Aux(p, _c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(c=conjuntoAleatorio())
def test_filtra(c: Conj[int]) -> None:
    r = filtra(lambda x: x % 2 == 0, c)
    assert filtra2(lambda x: x % 2 == 0, c) == r
    assert filtra3(lambda x: x % 2 == 0, c) == r
    assert filtra4(lambda x: x % 2 == 0, c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_Subconjunto_por_propiedad.py
#    1 passed in 0.28s

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, pertenece, vacio)

from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,

listaAconjunto)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def filtra(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:

if esVacio(c):

return vacio()

mc = menor(c)

rc = elimina(mc, c)

if p(mc):

return inserta(mc, filtra(p, rc))

return filtra(p, rc)

# 2ª solución

# ===========

def filtra2(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:

return listaAconjunto(list(filter(p, conjuntoAlista(c))))

# 3ª solución

# ===========

def filtra3Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:

r: Conj[A] = vacio()

while not esVacio(c):

mc = menor(c)

c = elimina(mc, c)

if p(mc):

r = inserta(mc, r)

return r

def filtra3(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:

_c = deepcopy(c)

return filtra3Aux(p, _c)

# 4ª solución

# ===========

def filtra4Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:

r: Conj[A] = Conj()

while not c.esVacio():

mc = c.menor()

c.elimina(mc)

if p(mc):

r.inserta(mc)

return r

def filtra4(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:

_c = deepcopy(c)

return filtra4Aux(p, _c)

# Comprobación de equivalencia de las definiciones

# ================================================

# La propiedad es

@given(c=conjuntoAleatorio())

def test_filtra(c: Conj[int]) -> None:

r = filtra(lambda x: x % 2 == 0, c)

assert filtra2(lambda x: x % 2 == 0, c) == r

assert filtra3(lambda x: x % 2 == 0, c) == r

assert filtra4(lambda x: x % 2 == 0, c) == r

# La comprobación es

# src> poetry run pytest -q TAD_Subconjunto_por_propiedad.py

# 1 passed in 0.28s

TAD de los conjuntos: Diferencia simétrica

PorJosé A. Alonso 16-marzo-202322-febrero-2023

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

   diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a

1	diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a

tal que diferenciaSimetrica c1 c2 es la diferencia simétrica de los conjuntos c1 y c2. Por ejemplo,

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

λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio)))

λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio))

λ> diferenciaSimetrica ej1 ej2

{2, 4, 5}

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_Diferencia_de_conjuntos (diferencia)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import TAD_Union_de_dos_conjuntos (union)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Test.QuickCheck

-- 1ª solución
-- ===========

diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a
diferenciaSimetrica c1 c2 =
  diferencia (union c1 c2) (interseccion c1 c2)

-- 2ª solución
-- ===========

diferenciaSimetrica2 :: Ord a => Conj a -> Conj a -> Conj a
diferenciaSimetrica2 c1 c2 =
  listaAconjunto ([x | x <- xs, x `notElem` ys] ++
                  [y | y <- ys, y `notElem` xs])
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_diferenciaSimetrica :: Conj Int -> Conj Int -> Bool
prop_diferenciaSimetrica c1 c2 =
  diferenciaSimetrica c1 c2 == diferenciaSimetrica2 c2 c1

-- La comprobación es
--    λ> quickCheck prop_diferenciaSimetrica
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta)

import TAD_Diferencia_de_conjuntos (diferencia)

import TAD_Interseccion_de_dos_conjuntos (interseccion)

import TAD_Union_de_dos_conjuntos (union)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Test.QuickCheck

-- 1ª solución

-- ===========

diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a

diferenciaSimetrica c1 c2 =

diferencia (union c1 c2) (interseccion c1 c2)

-- 2ª solución

-- ===========

diferenciaSimetrica2 :: Ord a => Conj a -> Conj a -> Conj a

diferenciaSimetrica2 c1 c2 =

listaAconjunto ([x | x <- xs, x `notElem` ys] ++

[y | y <- ys, y `notElem` xs])

where xs = conjuntoAlista c1

ys = conjuntoAlista c2

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_diferenciaSimetrica :: Conj Int -> Conj Int -> Bool

prop_diferenciaSimetrica c1 c2 =

diferenciaSimetrica c1 c2 == diferenciaSimetrica2 c2 c1

-- La comprobación es

-- λ> quickCheck prop_diferenciaSimetrica

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Diferencia_de_conjuntos import diferencia
from src.TAD_Interseccion_de_dos_conjuntos import interseccion
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)

# 1ª solución
# ===========

def diferenciaSimetrica(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return diferencia(union(c1, c2), interseccion(c1, c2))

# 2ª solución
# ===========

def diferenciaSimetrica2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return listaAconjunto([x for x in xs if x not in ys] +
                          [y for y in ys if y not in xs])

# 3ª solución
# ===========

def diferenciaSimetrica3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    while not esVacio(_c1):
        mc1 = menor(_c1)
        if not pertenece(mc1, c2):
            r = inserta(mc1, r)
        _c1 = elimina(mc1, _c1)
    while not esVacio(_c2):
        mc2 = menor(_c2)
        if not pertenece(mc2, c1):
            r = inserta(mc2, r)
        _c2 = elimina(mc2, _c2)
    return r

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_diferenciaSimetrica(c1: Conj[int], c2: Conj[int]) -> None:
    r = diferenciaSimetrica(c1, c2)
    assert diferenciaSimetrica2(c1, c2) == r
    assert diferenciaSimetrica3(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Diferencia_simetrica.py
#    1 passed in 0.30s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_Diferencia_de_conjuntos import diferencia

from src.TAD_Interseccion_de_dos_conjuntos import interseccion

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)

# 1ª solución

# ===========

def diferenciaSimetrica(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

return diferencia(union(c1, c2), interseccion(c1, c2))

# 2ª solución

# ===========

def diferenciaSimetrica2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

xs = conjuntoAlista(c1)

ys = conjuntoAlista(c2)

return listaAconjunto([x for x in xs if x not in ys] +

[y for y in ys if y not in xs])

# 3ª solución

# ===========

def diferenciaSimetrica3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

r: Conj[A] = vacio()

_c1 = deepcopy(c1)

_c2 = deepcopy(c2)

while not esVacio(_c1):

mc1 = menor(_c1)

if not pertenece(mc1, c2):

r = inserta(mc1, r)

_c1 = elimina(mc1, _c1)

while not esVacio(_c2):

mc2 = menor(_c2)

if not pertenece(mc2, c1):

r = inserta(mc2, r)

_c2 = elimina(mc2, _c2)

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_diferenciaSimetrica(c1: Conj[int], c2: Conj[int]) -> None:

r = diferenciaSimetrica(c1, c2)

assert diferenciaSimetrica2(c1, c2) == r

assert diferenciaSimetrica3(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_Diferencia_simetrica.py

# 1 passed in 0.30s

TAD de los conjuntos: Diferencia de conjuntos

PorJosé A. Alonso 15-marzo-202322-febrero-2023

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

   diferencia :: Ord a => Conj a -> Conj a -> Conj a

1	diferencia :: Ord a => Conj a -> Conj a -> Conj a

tal que diferencia c1 c2 es el conjunto de los elementos de c1 que no son elementos de c2. Por ejemplo,

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

λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio)))

λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio))

λ> diferencia ej1 ej2

{2, 5}

λ> diferencia ej2 ej1

{4}

λ> diferencia ej1 ej1

{}

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Test.QuickCheck

-- 1ª solución
-- ===========

diferencia :: Ord a => Conj a -> Conj a -> Conj a
diferencia c1 c2
  | esVacio c1       = vacio
  | pertenece mc1 c2 = diferencia rc1 c2
  | otherwise        = inserta mc1 (diferencia rc1 c2)
  where mc1 = menor c1
        rc1 = elimina mc1 c1

-- 2ª solución
-- ===========

diferencia2 :: Ord a => Conj a -> Conj a -> Conj a
diferencia2 c1 c2 =
  listaAconjunto [x | x <- conjuntoAlista c1, not (pertenece x c2)]

-- Las funciones conjuntoAlista y listaAconjunto 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_diferencia :: Conj Int -> Conj Int -> Bool
prop_diferencia c1 c2 =
  diferencia c1 c2 == diferencia2 c1 c2

-- La comprobación es
--    λ> quickCheck prop_diferencia
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Test.QuickCheck

-- 1ª solución

-- ===========

diferencia :: Ord a => Conj a -> Conj a -> Conj a

diferencia c1 c2

| esVacio c1 = vacio

| pertenece mc1 c2 = diferencia rc1 c2

| otherwise = inserta mc1 (diferencia rc1 c2)

where mc1 = menor c1

rc1 = elimina mc1 c1

-- 2ª solución

-- ===========

diferencia2 :: Ord a => Conj a -> Conj a -> Conj a

diferencia2 c1 c2 =

listaAconjunto [x | x <- conjuntoAlista c1, not (pertenece x c2)]

-- Las funciones conjuntoAlista y listaAconjunto 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_diferencia :: Conj Int -> Conj Int -> Bool

prop_diferencia c1 c2 =

diferencia c1 c2 == diferencia2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_diferencia

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def diferencia(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    if esVacio(c1):
        return vacio()
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return diferencia(rc1, c2)
    return inserta(mc1, diferencia(rc1, c2))

# 2ª solución
# ===========

def diferencia2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return listaAconjunto([x for x in conjuntoAlista(c1)
                           if not pertenece(x, c2)])

# Las funciones conjuntoAlista y listaAconjunto está definida en el
# ejercicio Transformaciones entre conjuntos y listas" que se encuentra
# en https://bit.ly/3RexzxH

# 3ª solución
# ===========

def diferencia3Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c1):
        mc1 = menor(c1)
        if not pertenece(mc1, c2):
            r = inserta(mc1, r)
        c1 = elimina(mc1, c1)
    return r

def diferencia3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return diferencia3Aux(_c1, c2)

# 4ª solución
# ===========

def diferencia4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = Conj()
    while not c1.esVacio():
        mc1 = c1.menor()
        if not c2.pertenece(mc1):
            r.inserta(mc1)
        c1.elimina(mc1)
    return r

def diferencia4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return diferencia4Aux(_c1, c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_diferencia(c1: Conj[int], c2: Conj[int]) -> None:
    r = diferencia(c1, c2)
    assert diferencia2(c1, c2) == r
    assert diferencia3(c1, c2) == r
    assert diferencia4(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Diferencia_de_conjuntos.py
#    1 passed in 0.31s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,

listaAconjunto)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def diferencia(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

if esVacio(c1):

return vacio()

mc1 = menor(c1)

rc1 = elimina(mc1, c1)

if pertenece(mc1, c2):

return diferencia(rc1, c2)

return inserta(mc1, diferencia(rc1, c2))

# 2ª solución

# ===========

def diferencia2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

return listaAconjunto([x for x in conjuntoAlista(c1)

if not pertenece(x, c2)])

# Las funciones conjuntoAlista y listaAconjunto está definida en el

# ejercicio Transformaciones entre conjuntos y listas" que se encuentra

# en https://bit.ly/3RexzxH

# 3ª solución

# ===========

def diferencia3Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

r: Conj[A] = vacio()

while not esVacio(c1):

mc1 = menor(c1)

if not pertenece(mc1, c2):

r = inserta(mc1, r)

c1 = elimina(mc1, c1)

return r

def diferencia3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

_c1 = deepcopy(c1)

return diferencia3Aux(_c1, c2)

# 4ª solución

# ===========

def diferencia4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

r: Conj[A] = Conj()

while not c1.esVacio():

mc1 = c1.menor()

if not c2.pertenece(mc1):

r.inserta(mc1)

c1.elimina(mc1)

return r

def diferencia4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

_c1 = deepcopy(c1)

return diferencia4Aux(_c1, c2)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_diferencia(c1: Conj[int], c2: Conj[int]) -> None:

r = diferencia(c1, c2)

assert diferencia2(c1, c2) == r

assert diferencia3(c1, c2) == r

assert diferencia4(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_Diferencia_de_conjuntos.py

# 1 passed in 0.31s

TAD de los conjuntos: Conjuntos disjuntos

PorJosé A. Alonso 14-marzo-202322-febrero-2023

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

   disjuntos :: Ord a => Conj a -> Conj a -> Bool

1	disjuntos :: Ord a => Conj a -> Conj a -> Bool

tal que disjuntos c1 c2 se verifica si los conjuntos c1 y c2 son disjuntos. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 5 vacio)
   λ> ej2 = inserta 4 (inserta 3 vacio)
   λ> ej3 = inserta 5 (inserta 3 vacio)
   λ> disjuntos ej1 ej2
   True
   λ> disjuntos ej1 ej3
   False

λ> ej1 = inserta 2 (inserta 5 vacio)

λ> ej2 = inserta 4 (inserta 3 vacio)

λ> ej3 = inserta 5 (inserta 3 vacio)

λ> disjuntos ej1 ej2

True

λ> disjuntos ej1 ej3

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, pertenece)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck

-- 1ª solución
-- ===========

disjuntos :: Ord a => Conj a -> Conj a -> Bool
disjuntos c1 c2 = esVacio (interseccion c1 c2)

-- La función interseccion está definida en el ejercicio
-- "Intersección de dos conjuntos" que se encuentra en
-- https://bit.ly/3jDL9xZ

-- 2ª solución
-- ===========

disjuntos2 :: Ord a => Conj a -> Conj a -> Bool
disjuntos2 c1 c2
  | esVacio c1 = True
  | pertenece mc1 c2 = False
  | otherwise        = disjuntos2 rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1

-- 3ª solución
-- ===========

disjuntos3 :: Ord a => Conj a -> Conj a -> Bool
disjuntos3 c1 c2 =
  all (`notElem` ys) xs
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2

-- 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_disjuntos :: Conj Int -> Conj Int -> Bool
prop_disjuntos c1 c2 =
  all (== disjuntos c1 c2)
      [disjuntos2 c1 c2,
       disjuntos3 c1 c2]

-- La comprobación es
--    λ> quickCheck prop_disjuntos
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina, pertenece)

import TAD_Interseccion_de_dos_conjuntos (interseccion)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)

import Test.QuickCheck

-- 1ª solución

-- ===========

disjuntos :: Ord a => Conj a -> Conj a -> Bool

disjuntos c1 c2 = esVacio (interseccion c1 c2)

-- La función interseccion está definida en el ejercicio

-- "Intersección de dos conjuntos" que se encuentra en

-- https://bit.ly/3jDL9xZ

-- 2ª solución

-- ===========

disjuntos2 :: Ord a => Conj a -> Conj a -> Bool

disjuntos2 c1 c2

| esVacio c1 = True

| pertenece mc1 c2 = False

| otherwise = disjuntos2 rc1 c2

where mc1 = menor c1

rc1 = elimina mc1 c1

-- 3ª solución

-- ===========

disjuntos3 :: Ord a => Conj a -> Conj a -> Bool

disjuntos3 c1 c2 =

all (`notElem` ys) xs

where xs = conjuntoAlista c1

ys = conjuntoAlista c2

-- 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_disjuntos :: Conj Int -> Conj Int -> Bool

prop_disjuntos c1 c2 =

all (== disjuntos c1 c2)

[disjuntos2 c1 c2,

disjuntos3 c1 c2]

-- La comprobación es

-- λ> quickCheck prop_disjuntos

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Interseccion_de_dos_conjuntos import interseccion
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 disjuntos(c1: Conj[A], c2: Conj[A]) -> bool:
    return esVacio(interseccion(c1, c2))

# 2ª solución
# ===========

def disjuntos2(c1: Conj[A], c2: Conj[A]) -> bool:
    if esVacio(c1):
        return True
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return False
    return disjuntos2(rc1, c2)

# 3ª solución
# ===========

def disjuntos3(c1: Conj[A], c2: Conj[A]) -> bool:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return all((x not in ys for x in xs))

# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra en
# https://bit.ly/3RexzxH

# 4ª solución
# ===========

def disjuntos4Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not esVacio(c1):
        mc1 = menor(c1)
        if pertenece(mc1, c2):
            return False
        c1 = elimina(mc1, c1)
    return True

def disjuntos4(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return disjuntos4Aux(_c1, c2)

# 5ª solución
# ===========

def disjuntos5Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not c1.esVacio():
        mc1 = c1.menor()
        if c2.pertenece(mc1):
            return False
        c1.elimina(mc1)
    return True

def disjuntos5(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return disjuntos5Aux(_c1, c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_disjuntos(c1: Conj[int], c2: Conj[int]) -> None:
    r = disjuntos(c1, c2)
    assert disjuntos2(c1, c2) == r
    assert disjuntos3(c1, c2) == r
    assert disjuntos4(c1, c2) == r
    assert disjuntos5(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Conjuntos_disjuntos.py
#    1 passed in 0.34s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_Interseccion_de_dos_conjuntos import interseccion

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 disjuntos(c1: Conj[A], c2: Conj[A]) -> bool:

return esVacio(interseccion(c1, c2))

# 2ª solución

# ===========

def disjuntos2(c1: Conj[A], c2: Conj[A]) -> bool:

if esVacio(c1):

return True

mc1 = menor(c1)

rc1 = elimina(mc1, c1)

if pertenece(mc1, c2):

return False

return disjuntos2(rc1, c2)

# 3ª solución

# ===========

def disjuntos3(c1: Conj[A], c2: Conj[A]) -> bool:

xs = conjuntoAlista(c1)

ys = conjuntoAlista(c2)

return all((x not in ys for x in xs))

# La función conjuntoAlista está definida en el ejercicio

# "Transformaciones entre conjuntos y listas" que se encuentra en

# https://bit.ly/3RexzxH

# 4ª solución

# ===========

def disjuntos4Aux(c1: Conj[A], c2: Conj[A]) -> bool:

while not esVacio(c1):

mc1 = menor(c1)

if pertenece(mc1, c2):

return False

c1 = elimina(mc1, c1)

return True

def disjuntos4(c1: Conj[A], c2: Conj[A]) -> bool:

_c1 = deepcopy(c1)

return disjuntos4Aux(_c1, c2)

# 5ª solución

# ===========

def disjuntos5Aux(c1: Conj[A], c2: Conj[A]) -> bool:

while not c1.esVacio():

mc1 = c1.menor()

if c2.pertenece(mc1):

return False

c1.elimina(mc1)

return True

def disjuntos5(c1: Conj[A], c2: Conj[A]) -> bool:

_c1 = deepcopy(c1)

return disjuntos5Aux(_c1, c2)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_disjuntos(c1: Conj[int], c2: Conj[int]) -> None:

r = disjuntos(c1, c2)

assert disjuntos2(c1, c2) == r

assert disjuntos3(c1, c2) == r

assert disjuntos4(c1, c2) == r

assert disjuntos5(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_Conjuntos_disjuntos.py

# 1 passed in 0.34s

TAD de los conjuntos: Intersección de varios conjuntos

PorJosé A. Alonso 13-marzo-202322-febrero-2023

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

   interseccionG :: Ord a => [Conj a] -> Conj a

1	interseccionG :: Ord a => [Conj a] -> Conj a

tal que interseccionG cs es la intersección de la lista de conjuntos cs. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 3 (inserta 5 vacio))
   λ> ej2 = inserta 5 (inserta 2 (inserta 7 vacio))
   λ> ej3 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> interseccionG [ej1, ej2, ej3]
   {2, 5}

λ> ej1 = inserta 2 (inserta 3 (inserta 5 vacio))

λ> ej2 = inserta 5 (inserta 2 (inserta 7 vacio))

λ> ej3 = inserta 3 (inserta 2 (inserta 5 vacio))

λ> interseccionG [ej1, ej2, ej3]

{2, 5}

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import Test.QuickCheck

-- 1ª solución
-- ===========

interseccionG :: Ord a => [Conj a] -> Conj a
interseccionG [c]      = c
interseccionG (cs:css) = interseccion cs (interseccionG css)

-- 2ª solución
-- ===========

interseccionG2 :: Ord a => [Conj a] -> Conj a
interseccionG2 = foldr1 interseccion

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_interseccionG :: NonEmptyList (Conj Int) -> Bool
prop_interseccionG (NonEmpty cs) =
  interseccionG cs == interseccionG2 cs

-- La comprobación es
--    λ> quickCheck prop_interseccionG1
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta)

import TAD_Interseccion_de_dos_conjuntos (interseccion)

import Test.QuickCheck

-- 1ª solución

-- ===========

interseccionG :: Ord a => [Conj a] -> Conj a

interseccionG [c] = c

interseccionG (cs:css) = interseccion cs (interseccionG css)

-- 2ª solución

-- ===========

interseccionG2 :: Ord a => [Conj a] -> Conj a

interseccionG2 = foldr1 interseccion

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_interseccionG :: NonEmptyList (Conj Int) -> Bool

prop_interseccionG (NonEmpty cs) =

interseccionG cs == interseccionG2 cs

-- La comprobación es

-- λ> quickCheck prop_interseccionG1

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from functools import reduce
from typing import Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.conjunto import Conj, conjuntoAleatorio, inserta, vacio
from src.TAD_Interseccion_de_dos_conjuntos import interseccion

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def interseccionG(cs: list[Conj[A]]) -> Conj[A]:
    if len(cs) == 1:
        return cs[0]
    return interseccion(cs[0], interseccionG(cs[1:]))

# 2ª solución
# ===========

def interseccionG2(cs: list[Conj[A]]) -> Conj[A]:
    return reduce(interseccion, cs[1:], cs[0])

# 3ª solución
# ===========

def interseccionG3(cs: list[Conj[A]]) -> Conj[A]:
    r = cs[0]
    for c in cs[1:]:
        r = interseccion(c, r)
    return r

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(conjuntoAleatorio(), min_size=1, max_size=10))
def test_interseccionG(cs: list[Conj[int]]) -> None:
    r = interseccionG(cs)
    assert interseccionG2(cs) == r
    assert interseccionG3(cs) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Interseccion_de_varios_conjuntos.py
#    1 passed in 0.60s

from __future__ import annotations

from abc import abstractmethod

from functools import reduce

from typing import Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.conjunto import Conj, conjuntoAleatorio, inserta, vacio

from src.TAD_Interseccion_de_dos_conjuntos import interseccion

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def interseccionG(cs: list[Conj[A]]) -> Conj[A]:

if len(cs) == 1:

return cs[0]

return interseccion(cs[0], interseccionG(cs[1:]))

# 2ª solución

# ===========

def interseccionG2(cs: list[Conj[A]]) -> Conj[A]:

return reduce(interseccion, cs[1:], cs[0])

# 3ª solución

# ===========

def interseccionG3(cs: list[Conj[A]]) -> Conj[A]:

r = cs[0]

for c in cs[1:]:

r = interseccion(c, r)

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(conjuntoAleatorio(), min_size=1, max_size=10))

def test_interseccionG(cs: list[Conj[int]]) -> None:

r = interseccionG(cs)

assert interseccionG2(cs) == r

assert interseccionG3(cs) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_Interseccion_de_varios_conjuntos.py

# 1 passed in 0.60s

TAD de los conjuntos: Intersección de dos conjuntos

PorJosé A. Alonso 10-marzo-202322-febrero-2023

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

   interseccion :: Ord a => Conj a -> Conj a -> Conj a

1	interseccion :: Ord a => Conj a -> Conj a -> Conj a

tal que interseccion c1 c2 es la intersección de los conjuntos c1 y c2. Por ejemplo,

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

λ> ej1 = inserta 3 (inserta 5 (inserta 2 vacio))

λ> ej2 = inserta 2 (inserta 4 (inserta 3 vacio))

λ> interseccion ej1 ej2

{2, 3}

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Data.List (intersect)
import Test.QuickCheck

-- 1ª solución
-- ===========

interseccion :: Ord a => Conj a -> Conj a -> Conj a
interseccion c1 c2
  | esVacio c1       = vacio
  | pertenece mc1 c2 = inserta mc1 (interseccion rc1 c2)
  | otherwise        = interseccion rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1

-- 2ª solución
-- ===========

interseccion2 :: Ord a => Conj a -> Conj a -> Conj a
interseccion2 c1 c2 =
  listaAconjunto [x | x <- conjuntoAlista c1, x `pertenece` c2]

-- Las funciones conjuntoAlista y listaAconjunto está definida en el
-- ejercicio Transformaciones entre conjuntos y listas" que se encuentra
-- en https://bit.ly/3RexzxH

-- 3ª solución
-- ===========

interseccion3 :: Ord a => Conj a -> Conj a -> Conj a
interseccion3 c1 c2 =
  listaAconjunto (conjuntoAlista c1 `intersect` conjuntoAlista c2)

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_interseccion :: Conj Int -> Conj Int -> Bool
prop_interseccion c1 c2 =
  all (== interseccion c1 c2)
      [interseccion2 c1 c2,
       interseccion3 c1 c2]

-- La comprobación es
--    λ> quickCheck prop_interseccion
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Data.List (intersect)

import Test.QuickCheck

-- 1ª solución

-- ===========

interseccion :: Ord a => Conj a -> Conj a -> Conj a

interseccion c1 c2

| esVacio c1 = vacio

| pertenece mc1 c2 = inserta mc1 (interseccion rc1 c2)

| otherwise = interseccion rc1 c2

where mc1 = menor c1

rc1 = elimina mc1 c1

-- 2ª solución

-- ===========

interseccion2 :: Ord a => Conj a -> Conj a -> Conj a

interseccion2 c1 c2 =

listaAconjunto [x | x <- conjuntoAlista c1, x `pertenece` c2]

-- Las funciones conjuntoAlista y listaAconjunto está definida en el

-- ejercicio Transformaciones entre conjuntos y listas" que se encuentra

-- en https://bit.ly/3RexzxH

-- 3ª solución

-- ===========

interseccion3 :: Ord a => Conj a -> Conj a -> Conj a

interseccion3 c1 c2 =

listaAconjunto (conjuntoAlista c1 `intersect` conjuntoAlista c2)

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_interseccion :: Conj Int -> Conj Int -> Bool

prop_interseccion c1 c2 =

all (== interseccion c1 c2)

[interseccion2 c1 c2,

interseccion3 c1 c2]

-- La comprobación es

-- λ> quickCheck prop_interseccion

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def interseccion(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    if esVacio(c1):
        return vacio()
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return inserta(mc1, interseccion(rc1, c2))
    return interseccion(rc1, c2)

# 2ª solución
# ===========

def interseccion2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return listaAconjunto([x for x in conjuntoAlista(c1)
                           if pertenece(x, c2)])
#
# Las funciones conjuntoAlista y listaAconjunto está definida en el
# ejercicio Transformaciones entre conjuntos y listas" que se encuentra
# en https://bit.ly/3RexzxH

# 3ª solución
# ===========

def interseccion3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c1):
        mc1 = menor(c1)
        c1 = elimina(mc1, c1)
        if pertenece(mc1, c2):
            r = inserta(mc1, r)
    return r

# 4ª solución
# ===========

def interseccion4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not c1.esVacio():
        mc1 = c1.menor()
        c1.elimina(mc1)
        if c2.pertenece(mc1):
            r.inserta(mc1)
    return r

def interseccion4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return interseccion4Aux(_c1, c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_interseccion(c1: Conj[int], c2: Conj[int]) -> None:
    r = interseccion(c1, c2)
    assert interseccion2(c1, c2) == r
    assert interseccion3(c1, c2) == r
    assert interseccion4(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Interseccion_de_dos_conjuntos.py
#    1 passed in 0.30s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,

listaAconjunto)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def interseccion(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

if esVacio(c1):

return vacio()

mc1 = menor(c1)

rc1 = elimina(mc1, c1)

if pertenece(mc1, c2):

return inserta(mc1, interseccion(rc1, c2))

return interseccion(rc1, c2)

# 2ª solución

# ===========

def interseccion2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

return listaAconjunto([x for x in conjuntoAlista(c1)

if pertenece(x, c2)])

# Las funciones conjuntoAlista y listaAconjunto está definida en el

# ejercicio Transformaciones entre conjuntos y listas" que se encuentra

# en https://bit.ly/3RexzxH

# 3ª solución

# ===========

def interseccion3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

r: Conj[A] = vacio()

while not esVacio(c1):

mc1 = menor(c1)

c1 = elimina(mc1, c1)

if pertenece(mc1, c2):

r = inserta(mc1, r)

return r

# 4ª solución

# ===========

def interseccion4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

r: Conj[A] = vacio()

while not c1.esVacio():

mc1 = c1.menor()

c1.elimina(mc1)

if c2.pertenece(mc1):

r.inserta(mc1)

return r

def interseccion4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

_c1 = deepcopy(c1)

return interseccion4Aux(_c1, c2)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_interseccion(c1: Conj[int], c2: Conj[int]) -> None:

r = interseccion(c1, c2)

assert interseccion2(c1, c2) == r

assert interseccion3(c1, c2) == r

assert interseccion4(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_Interseccion_de_dos_conjuntos.py

# 1 passed in 0.30s

TAD de los conjuntos: Unión de varios conjuntos

PorJosé A. Alonso 9-marzo-202322-febrero-2023

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

   unionG:: Ord a => [Conj a] -> Conj a

1	unionG:: Ord a => [Conj a] -> Conj a

tal unionG cs calcule la unión de la lista de conjuntos cs. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 vacio)
   λ> ej2 = inserta 5 (inserta 6 vacio)
   λ> ej3 = inserta 3 (inserta 6 vacio)
   λ> unionG [ej1, ej2, ej3]
   {3, 5, 6}

λ> ej1 = inserta 3 (inserta 5 vacio)

λ> ej2 = inserta 5 (inserta 6 vacio)

λ> ej3 = inserta 3 (inserta 6 vacio)

λ> unionG [ej1, ej2, ej3]

{3, 5, 6}

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_Union_de_dos_conjuntos (union)
import Test.QuickCheck

-- 1ª solución
-- ===========

unionG :: Ord a => [Conj a] -> Conj a
unionG []          = vacio
unionG (c:cs) = c `union` unionG cs

-- 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
-- ===========

unionG2 :: Ord a => [Conj a] -> Conj a
unionG2 = foldr union vacio

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_unionG :: [Conj Int] -> Bool
prop_unionG cs =
  unionG cs == unionG2 cs

-- La comprobación es
--    λ> quickCheck prop_unionG
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta)

import TAD_Union_de_dos_conjuntos (union)

import Test.QuickCheck

-- 1ª solución

-- ===========

unionG :: Ord a => [Conj a] -> Conj a

unionG [] = vacio

unionG (c:cs) = c `union` unionG cs

-- 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

-- ===========

unionG2 :: Ord a => [Conj a] -> Conj a

unionG2 = foldr union vacio

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_unionG :: [Conj Int] -> Bool

prop_unionG cs =

unionG cs == unionG2 cs

-- La comprobación es

-- λ> quickCheck prop_unionG

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from functools import reduce
from typing import Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.conjunto import Conj, conjuntoAleatorio, inserta, vacio
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)

# 1ª solución
# ===========

def unionG(cs: list[Conj[A]]) -> Conj[A]:
    if not cs:
        return vacio()
    return union(cs[0], unionG(cs[1:]))

# 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 unionG2(cs: list[Conj[A]]) -> Conj[A]:
    return reduce(union, cs, vacio())

# 3ª solución
# ===========

def unionG3(cs: list[Conj[A]]) -> Conj[A]:
    r: Conj[A] = vacio()
    for c in cs:
        r = union(c, r)
    return r

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(conjuntoAleatorio(), max_size=10))
def test_union(cs: list[Conj[int]]) -> None:
    r = unionG(cs)
    assert unionG2(cs) == r
    assert unionG3(cs) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Union_de_varios_conjuntos.py
#    1 passed in 0.75s

from __future__ import annotations

from abc import abstractmethod

from functools import reduce

from typing import Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.conjunto import Conj, conjuntoAleatorio, inserta, vacio

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)

# 1ª solución

# ===========

def unionG(cs: list[Conj[A]]) -> Conj[A]:

if not cs:

return vacio()

return union(cs[0], unionG(cs[1:]))

# 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 unionG2(cs: list[Conj[A]]) -> Conj[A]:

return reduce(union, cs, vacio())

# 3ª solución

# ===========

def unionG3(cs: list[Conj[A]]) -> Conj[A]:

r: Conj[A] = vacio()

for c in cs:

r = union(c, r)

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(conjuntoAleatorio(), max_size=10))

def test_union(cs: list[Conj[int]]) -> None:

r = unionG(cs)

assert unionG2(cs) == r

assert unionG3(cs) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_Union_de_varios_conjuntos.py

# 1 passed in 0.75s

TAD de los conjuntos: Unión de dos conjuntos

PorJosé A. Alonso 8-marzo-202322-febrero-2023

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

   union :: Ord a => Conj a -> Conj a -> Conj a

1	union :: Ord a => Conj a -> Conj a -> Conj a

tal union c1 c2 es la unión de ambos conjuntos. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 vacio)
   λ> ej2 = inserta 4 (inserta 3 vacio)
   λ> union ej1 ej2
   {3, 4, 5}

λ> ej1 = inserta 3 (inserta 5 vacio)

λ> ej2 = inserta 4 (inserta 3 vacio)

λ> union ej1 ej2

{3, 4, 5}

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import qualified Data.List as L (union)
import Test.QuickCheck

-- 1ª solución
-- ===========

union :: Ord a => Conj a -> Conj a -> Conj a
union c1 c2
  | esVacio c1 = c2
  | otherwise  = inserta mc1 (rc1 `union` c2)
  where mc1 = menor c1
        rc1 = elimina mc1 c1

-- 2ª solución
-- ===========

union2 :: Ord a => Conj a -> Conj a -> Conj a
union2 c1 c2 =
  foldr inserta c2 (conjuntoAlista c1)

-- 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
-- ===========

union3 :: Ord a => Conj a -> Conj a -> Conj a
union3 c1 c2 =
  listaAconjunto (conjuntoAlista c1 `L.union` conjuntoAlista c2)

-- La función listaAconjunto 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_union :: Conj Int -> Conj Int -> Bool
prop_union c1 c2 =
  all (== union c1 c2)
      [union2 c1 c2,
       union3 c1 c2]

-- La comprobación es
--    λ> quickCheck prop_union
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, esVacio)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import qualified Data.List as L (union)

import Test.QuickCheck

-- 1ª solución

-- ===========

union :: Ord a => Conj a -> Conj a -> Conj a

union c1 c2

| esVacio c1 = c2

| otherwise = inserta mc1 (rc1 `union` c2)

where mc1 = menor c1

rc1 = elimina mc1 c1

-- 2ª solución

-- ===========

union2 :: Ord a => Conj a -> Conj a -> Conj a

union2 c1 c2 =

foldr inserta c2 (conjuntoAlista c1)

-- 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

-- ===========

union3 :: Ord a => Conj a -> Conj a -> Conj a

union3 c1 c2 =

listaAconjunto (conjuntoAlista c1 `L.union` conjuntoAlista c2)

-- La función listaAconjunto 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_union :: Conj Int -> Conj Int -> Bool

prop_union c1 c2 =

all (== union c1 c2)

[union2 c1 c2,

union3 c1 c2]

-- La comprobación es

-- λ> quickCheck prop_union

-- +++ 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

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def union(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    if esVacio(c1):
        return c2
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    return inserta(mc1, union(rc1, c2))

# 2ª solución
# ===========

def union2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return reduce(lambda c, x: inserta(x, c), conjuntoAlista(c1), c2)

# 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 union3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r = c2
    while not esVacio(c1):
        mc1 = menor(c1)
        r = inserta(mc1, r)
        c1 = elimina(mc1, c1)
    return r

# 4ª solución
# ===========

def union4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    while not c1.esVacio():
        mc1 = menor(c1)
        c2.inserta(mc1)
        c1.elimina(mc1)
    return c2

def union4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    return union4Aux(_c1, _c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_union(c1: Conj[int], c2: Conj[int]) -> None:
    r = union(c1, c2)
    assert union2(c1, c2) == r
    assert union3(c1, c2) == r
    assert union4(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Union_de_dos_conjuntos.py
#    1 passed in 0.35s

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

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def union(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

if esVacio(c1):

return c2

mc1 = menor(c1)

rc1 = elimina(mc1, c1)

return inserta(mc1, union(rc1, c2))

# 2ª solución

# ===========

def union2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

return reduce(lambda c, x: inserta(x, c), conjuntoAlista(c1), c2)

# 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 union3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

r = c2

while not esVacio(c1):

mc1 = menor(c1)

r = inserta(mc1, r)

c1 = elimina(mc1, c1)

return r

# 4ª solución

# ===========

def union4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

while not c1.esVacio():

mc1 = menor(c1)

c2.inserta(mc1)

c1.elimina(mc1)

return c2

def union4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:

_c1 = deepcopy(c1)

_c2 = deepcopy(c2)

return union4Aux(_c1, _c2)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_union(c1: Conj[int], c2: Conj[int]) -> None:

r = union(c1, c2)

assert union2(c1, c2) == r

assert union3(c1, c2) == r

assert union4(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_Union_de_dos_conjuntos.py

# 1 passed in 0.35s

TAD de los conjuntos: Número de elementos de un conjunto

PorJosé A. Alonso 7-marzo-202322-febrero-2023

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

   cardinal :: Conj a -> Int

1	cardinal :: Conj a -> Int

tal que cardinal c es el número de elementos del conjunto c. Por ejemplo,

   cardinal (inserta 4 (inserta 5 vacio))             == 2
   cardinal (inserta 4 (inserta 5 (inserta 4 vacio))) == 2

1 2	cardinal (inserta 4 (inserta 5 vacio)) == 2 cardinal (inserta 4 (inserta 5 (inserta 4 vacio))) == 2

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck

-- 1ª solución
-- ===========

cardinal :: Ord a => Conj a -> Int
cardinal c
  | esVacio c = 0
  | otherwise = 1 + cardinal (elimina (menor c) c)

-- 2ª solución
-- ===========

cardinal2 :: Ord a => Conj a -> Int
cardinal2 = length . conjuntoAlista

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_cardinal :: Conj Int -> Bool
prop_cardinal c =
  cardinal c == cardinal2 c

-- La comprobación es
--    λ> quickCheck prop_cardinal
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, esVacio)

import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)

import Test.QuickCheck

-- 1ª solución

-- ===========

cardinal :: Ord a => Conj a -> Int

cardinal c

| esVacio c = 0

| otherwise = 1 + cardinal (elimina (menor c) c)

-- 2ª solución

-- ===========

cardinal2 :: Ord a => Conj a -> Int

cardinal2 = length . conjuntoAlista

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_cardinal :: Conj Int -> Bool

prop_cardinal c =

cardinal c == cardinal2 c

-- La comprobación es

-- λ> quickCheck prop_cardinal

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
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

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def cardinal(c: Conj[A]) -> int:
    if esVacio(c):
        return 0
    return 1 + cardinal(elimina(menor(c), c))

# 2ª solución
# ===========

def cardinal2(c: Conj[A]) -> int:
    return len(conjuntoAlista(c))

# 3ª solución
# ===========

def cardinal3(c: Conj[A]) -> int:
    r = 0
    while not esVacio(c):
        r = r + 1
        c = elimina(menor(c), c)
    return r

# 4ª solución
# ===========

def cardinal4Aux(c: Conj[A]) -> int:
    r = 0
    while not c.esVacio():
        r = r + 1
        c.elimina(menor(c))
    return r

def cardinal4(c: Conj[A]) -> int:
    _c = deepcopy(c)
    return cardinal4Aux(_c)

# Comprobación de equivalencia
# ============================

@given(c=conjuntoAleatorio())
def test_cardinal(c: Conj[int]) -> None:
    r = cardinal(c)
    assert cardinal2(c) == r
    assert cardinal3(c) == r
    assert cardinal3(c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_Numero_de_elementos_de_un_conjunto.py
#    1 passed in 0.33s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

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

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def cardinal(c: Conj[A]) -> int:

if esVacio(c):

return 0

return 1 + cardinal(elimina(menor(c), c))

# 2ª solución

# ===========

def cardinal2(c: Conj[A]) -> int:

return len(conjuntoAlista(c))

# 3ª solución

# ===========

def cardinal3(c: Conj[A]) -> int:

r = 0

while not esVacio(c):

r = r + 1

c = elimina(menor(c), c)

return r

# 4ª solución

# ===========

def cardinal4Aux(c: Conj[A]) -> int:

r = 0

while not c.esVacio():

r = r + 1

c.elimina(menor(c))

return r

def cardinal4(c: Conj[A]) -> int:

_c = deepcopy(c)

return cardinal4Aux(_c)

# Comprobación de equivalencia

# ============================

@given(c=conjuntoAleatorio())

def test_cardinal(c: Conj[int]) -> None:

r = cardinal(c)

assert cardinal2(c) == r

assert cardinal3(c) == r

# La comprobación es

# src> poetry run pytest -q TAD_Numero_de_elementos_de_un_conjunto.py

# 1 passed in 0.33s

TAD de los conjuntos: Conjunto unitario

PorJosé A. Alonso 6-marzo-202322-febrero-2023

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

   unitario :: Ord a => a -> Conj a

1	unitario :: Ord a => a -> Conj a

tal que unitario x es el conjunto {x}. Por ejemplo,

   unitario 5 == {5}

1	unitario 5 == {5}

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)

unitario :: Ord a => a -> Conj a
unitario x = inserta x vacio

import TAD.Conjunto (Conj, vacio, inserta)

unitario :: Ord a => a -> Conj a

unitario x = inserta x vacio

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from typing import Protocol, TypeVar

from src.TAD.conjunto import Conj, inserta, vacio

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

def unitario(x: A) -> Conj[A]:
    return inserta(x, vacio())

from __future__ import annotations

from abc import abstractmethod

from typing import Protocol, TypeVar

from src.TAD.conjunto import Conj, inserta, vacio

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

def unitario(x: A) -> Conj[A]:

return inserta(x, vacio())

TAD de los conjuntos: Reconocimiento de subconjunto propio

PorJosé A. Alonso 3-marzo-202322-febrero-2023

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

   subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

1	subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

tal subconjuntoPropio c1 c2 se verifica si c1 es un subconjunto propio de c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> ej4 = inserta 2 (inserta 5 vacio)
   λ> subconjuntoPropio ej1 ej2
   True
   λ> subconjuntoPropio ej1 ej3
   False
   λ> subconjuntoPropio ej1 ej4
   False

λ> ej1 = inserta 5 (inserta 2 vacio)

λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))

λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))

λ> ej4 = inserta 2 (inserta 5 vacio)

λ> subconjuntoPropio ej1 ej2

True

λ> subconjuntoPropio ej1 ej3

False

λ> subconjuntoPropio ej1 ej4

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)
import TAD_subconjunto (subconjunto)

subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool
subconjuntoPropio c1 c2 =
  subconjunto c1 c2 && c1 /= c2

-- La función subconjunto está definida en el ejercicio
-- "Reconocimiento de subconjuntos" que se encuentra en
-- https://bit.ly/3wPBtU5

import TAD.Conjunto (Conj, vacio, inserta)

import TAD_subconjunto (subconjunto)

subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

subconjuntoPropio c1 c2 =

subconjunto c1 c2 && c1 /= c2

-- La función subconjunto está definida en el ejercicio

-- "Reconocimiento de subconjuntos" que se encuentra en

-- https://bit.ly/3wPBtU5

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from typing import Protocol, TypeVar

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_subconjunto import subconjunto

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

def subconjuntoPropio(c1: Conj[A], c2: Conj[A]) -> bool:
    return subconjunto(c1, c2) and c1 != c2

# La función subconjunto está definida en el ejercicio
# "Reconocimiento de subconjuntos" que se encuentra en
# https://bit.ly/3wPBtU5

from __future__ import annotations

from abc import abstractmethod

from typing import Protocol, TypeVar

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_subconjunto import subconjunto

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

def subconjuntoPropio(c1: Conj[A], c2: Conj[A]) -> bool:

return subconjunto(c1, c2) and c1 != c2

# La función subconjunto está definida en el ejercicio

# "Reconocimiento de subconjuntos" que se encuentra en

# https://bit.ly/3wPBtU5

TAD de los conjuntos: Reconocimiento de subconjuntos

PorJosé A. Alonso 2-marzo-202322-febrero-2023

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

   subconjunto :: Ord a => Conj a -> Conj a -> Bool

1	subconjunto :: Ord a => Conj a -> Conj a -> Bool

tal que subconjunto c1 c2 se verifica si todos los elementos de c1 pertenecen a c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> subconjunto ej1 ej2
   True
   λ> subconjunto ej1 ej3
   False

λ> ej1 = inserta 5 (inserta 2 vacio)

λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))

λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))

λ> subconjunto ej1 ej2

True

λ> subconjunto ej1 ej3

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, menor, elimina, pertenece, esVacio)
import Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck

-- 1ª solución
-- ===========

subconjunto :: Ord a => Conj a -> Conj a -> Bool
subconjunto c1 c2
  | esVacio c1 = True
  | otherwise  =  pertenece mc1 c2 && subconjunto rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1

-- 2ª solución
-- ===========

subconjunto2 :: Ord a => Conj a -> Conj a -> Bool
subconjunto2 c1 c2 =
  and [pertenece x c2 | x <- conjuntoAlista c1]

-- 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
-- ===========

subconjunto3 :: Ord a => Conj a -> Conj a -> Bool
subconjunto3 c1 c2 =
  all (`pertenece` c2) (conjuntoAlista c1)

-- 4ª solución
-- ===========

subconjunto4 :: Ord a => Conj a -> Conj a -> Bool
subconjunto4 c1 c2 =
  sublista (conjuntoAlista c1) (conjuntoAlista c2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por
-- ejemplo,
--    sublista [5, 2] [3, 2, 5]  ==  True
--    sublista [5, 2] [3, 4, 5]  ==  False
sublista :: Ord a => [a] -> [a] -> Bool
sublista [] _      = True
sublista (x:xs) ys = elem x ys && sublista xs ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_subconjunto :: Conj Int -> Conj Int -> Bool
prop_subconjunto c1 c2 =
  all (== subconjunto c1 c2)
      [subconjunto2 c1 c2,
       subconjunto3 c1 c2,
       subconjunto4 c1 c2]

-- La comprobación es
--    λ> quickCheck prop_subconjunto
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import Transformaciones_conjuntos_listas (conjuntoAlista)

import Test.QuickCheck

-- 1ª solución

-- ===========

subconjunto :: Ord a => Conj a -> Conj a -> Bool

subconjunto c1 c2

| esVacio c1 = True

| otherwise = pertenece mc1 c2 && subconjunto rc1 c2

where mc1 = menor c1

rc1 = elimina mc1 c1

-- 2ª solución

-- ===========

subconjunto2 :: Ord a => Conj a -> Conj a -> Bool

subconjunto2 c1 c2 =

and [pertenece x c2 | x <- conjuntoAlista c1]

-- 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

-- ===========

subconjunto3 :: Ord a => Conj a -> Conj a -> Bool

subconjunto3 c1 c2 =

all (`pertenece` c2) (conjuntoAlista c1)

-- 4ª solución

-- ===========

subconjunto4 :: Ord a => Conj a -> Conj a -> Bool

subconjunto4 c1 c2 =

sublista (conjuntoAlista c1) (conjuntoAlista c2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por

-- ejemplo,

-- sublista [5, 2] [3, 2, 5] == True

-- sublista [5, 2] [3, 4, 5] == False

sublista :: Ord a => [a] -> [a] -> Bool

sublista [] _ = True

sublista (x:xs) ys = elem x ys && sublista xs ys

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_subconjunto :: Conj Int -> Conj Int -> Bool

prop_subconjunto c1 c2 =

all (== subconjunto c1 c2)

[subconjunto2 c1 c2,

subconjunto3 c1 c2,

subconjunto4 c1 c2]

-- La comprobación es

-- λ> quickCheck prop_subconjunto

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, 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 subconjunto(c1: Conj[A], c2: Conj[A]) -> bool:
    if esVacio(c1):
        return True
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    return pertenece(mc1, c2) and subconjunto(rc1, c2)

# 2ª solución
# ===========

def subconjunto2(c1: Conj[A], c2: Conj[A]) -> bool:
    return all((pertenece(x, c2) for x in conjuntoAlista(c1)))

# 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
# ===========

# (sublista xs ys) se verifica si xs es una sublista de ys. Por
# ejemplo,
#    sublista [5, 2] [3, 2, 5]  ==  True
#    sublista [5, 2] [3, 4, 5]  ==  False
def sublista(xs: list[A], ys: list[A]) -> bool:
    if not xs:
        return True
    return xs[0] in ys and sublista(xs[1:], ys)

def subconjunto3(c1: Conj[A], c2: Conj[A]) -> bool:
    return sublista(conjuntoAlista(c1), conjuntoAlista(c2))

# 4ª solución
# ===========

def subconjunto4(c1: Conj[A], c2: Conj[A]) -> bool:
    while not esVacio(c1):
        mc1 = menor(c1)
        if not pertenece(mc1, c2):
            return False
        c1 = elimina(mc1, c1)
    return True

# 5ª solución
# ===========

def subconjunto5Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not c1.esVacio():
        mc1 = c1.menor()
        if not c2.pertenece(mc1):
            return False
        c1.elimina(mc1)
    return True

def subconjunto5(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return subconjunto5Aux(_c1, c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_subconjunto(c1: Conj[int], c2: Conj[int]) -> None:
    r = subconjunto(c1, c2)
    assert subconjunto2(c1, c2) == r
    assert subconjunto3(c1, c2) == r
    assert subconjunto4(c1, c2) == r
    assert subconjunto5(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_subconjunto.py
#    1 passed in 0.37s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, 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 subconjunto(c1: Conj[A], c2: Conj[A]) -> bool:

if esVacio(c1):

return True

mc1 = menor(c1)

rc1 = elimina(mc1, c1)

return pertenece(mc1, c2) and subconjunto(rc1, c2)

# 2ª solución

# ===========

def subconjunto2(c1: Conj[A], c2: Conj[A]) -> bool:

return all((pertenece(x, c2) for x in conjuntoAlista(c1)))

# 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

# ===========

# (sublista xs ys) se verifica si xs es una sublista de ys. Por

# ejemplo,

# sublista [5, 2] [3, 2, 5] == True

# sublista [5, 2] [3, 4, 5] == False

def sublista(xs: list[A], ys: list[A]) -> bool:

if not xs:

return True

return xs[0] in ys and sublista(xs[1:], ys)

def subconjunto3(c1: Conj[A], c2: Conj[A]) -> bool:

return sublista(conjuntoAlista(c1), conjuntoAlista(c2))

# 4ª solución

# ===========

def subconjunto4(c1: Conj[A], c2: Conj[A]) -> bool:

while not esVacio(c1):

mc1 = menor(c1)

if not pertenece(mc1, c2):

return False

c1 = elimina(mc1, c1)

return True

# 5ª solución

# ===========

def subconjunto5Aux(c1: Conj[A], c2: Conj[A]) -> bool:

while not c1.esVacio():

mc1 = c1.menor()

if not c2.pertenece(mc1):

return False

c1.elimina(mc1)

return True

def subconjunto5(c1: Conj[A], c2: Conj[A]) -> bool:

_c1 = deepcopy(c1)

return subconjunto5Aux(_c1, c2)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_subconjunto(c1: Conj[int], c2: Conj[int]) -> None:

r = subconjunto(c1, c2)

assert subconjunto2(c1, c2) == r

assert subconjunto3(c1, c2) == r

assert subconjunto4(c1, c2) == r

assert subconjunto5(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_subconjunto.py

# 1 passed in 0.37s

TAD de los conjuntos: Transformaciones entre conjuntos y listas

PorJosé A. Alonso 1-marzo-202322-febrero-2023

Utilizando el tipo abstracto de datos de los conjuntos definir las funciones

   listaAconjunto :: [a] -> Conj a
   conjuntoAlista :: Conj a -> [a]

1 2	listaAconjunto :: [a] -> Conj a conjuntoAlista :: Conj a -> [a]

tales que
+ listaAconjunto xs es el conjunto formado por los elementos de xs. Por ejemplo,

     λ> listaAconjunto [3, 2, 5]
     {2, 3, 5}

1 2	λ> listaAconjunto [3, 2, 5] {2, 3, 5}

conjuntoAlista c es la lista formada por los elementos del conjunto c. Por ejemplo,

     λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio)))
     [2,3,5]

1 2	λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio))) [2,3,5]

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

   conjuntoAlista (listaAconjunto xs) = sort (nub xs)
   listaAconjunto (conjuntoAlista c)  = c

1 2	conjuntoAlista (listaAconjunto xs) = sort (nub xs) listaAconjunto (conjuntoAlista c) = c

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import Data.List (sort, nub)
import Test.QuickCheck

-- 1ª definición de listaAconjunto
-- ===============================

listaAconjunto :: Ord a => [a] -> Conj a
listaAconjunto []     = vacio
listaAconjunto (x:xs) = inserta x (listaAconjunto xs)

-- 2ª definición de listaAconjunto
-- ===============================

listaAconjunto2 :: Ord a => [a] -> Conj a
listaAconjunto2 = foldr inserta vacio

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_listaAconjunto :: [Int] -> Bool
prop_listaAconjunto xs =
  listaAconjunto xs == listaAconjunto2 xs

-- La comprobación es
--    λ> quickCheck prop_listaAconjunto
--    +++ OK, passed 100 tests.

-- Definición de conjuntoAlista
-- ============================

conjuntoAlista :: Ord a => Conj a -> [a]
conjuntoAlista c
  | esVacio c = []
  | otherwise = mc : conjuntoAlista rc
  where mc = menor c
        rc = elimina mc c

-- Comprobación de las propiedades
-- ===============================

-- La primera propiedad es
prop_1_listaAconjunto :: [Int] -> Bool
prop_1_listaAconjunto xs =
  conjuntoAlista (listaAconjunto xs) == sort (nub xs)

-- La comprobación es
--    λ> quickCheck prop_1_listaAconjunto
--    +++ OK, passed 100 tests.

-- La segunda propiedad es
prop_2_listaAconjunto :: Conj Int -> Bool
prop_2_listaAconjunto c =
  listaAconjunto (conjuntoAlista c) == c

-- La comprobación es
--    λ> quickCheck prop_2_listaAconjunto
--    +++ OK, passed 100 tests.

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import Data.List (sort, nub)

import Test.QuickCheck

-- 1ª definición de listaAconjunto

-- ===============================

listaAconjunto :: Ord a => [a] -> Conj a

listaAconjunto [] = vacio

listaAconjunto (x:xs) = inserta x (listaAconjunto xs)

-- 2ª definición de listaAconjunto

-- ===============================

listaAconjunto2 :: Ord a => [a] -> Conj a

listaAconjunto2 = foldr inserta vacio

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_listaAconjunto :: [Int] -> Bool

prop_listaAconjunto xs =

listaAconjunto xs == listaAconjunto2 xs

-- La comprobación es

-- λ> quickCheck prop_listaAconjunto

-- +++ OK, passed 100 tests.

-- Definición de conjuntoAlista

-- ============================

conjuntoAlista :: Ord a => Conj a -> [a]

conjuntoAlista c

| esVacio c = []

| otherwise = mc : conjuntoAlista rc

where mc = menor c

rc = elimina mc c

-- Comprobación de las propiedades

-- ===============================

-- La primera propiedad es

prop_1_listaAconjunto :: [Int] -> Bool

prop_1_listaAconjunto xs =

conjuntoAlista (listaAconjunto xs) == sort (nub xs)

-- La comprobación es

-- λ> quickCheck prop_1_listaAconjunto

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_2_listaAconjunto :: Conj Int -> Bool

prop_2_listaAconjunto c =

listaAconjunto (conjuntoAlista c) == c

-- La comprobación es

-- λ> quickCheck prop_2_listaAconjunto

-- +++ 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 hypothesis import strategies as st

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª definición de listaAconjunto
# ===============================

def listaAconjunto(xs: list[A]) -> Conj[A]:
    if not xs:
        return vacio()
    return inserta(xs[0], listaAconjunto(xs[1:]))

# 2ª definición de listaAconjunto
# ===============================

def listaAconjunto2(xs: list[A]) -> Conj[A]:
    return reduce(lambda ys, y: inserta(y, ys), xs, vacio())

# 3ª solución de listaAconjunto
# =============================

def listaAconjunto3(xs: list[A]) -> Conj[A]:
    c: Conj[A] = Conj()
    for x in xs:
        c.inserta(x)
    return c

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()))
def test_listaAconjunto(xs: list[int]) -> None:
    r = listaAconjunto(xs)
    assert listaAconjunto2(xs) == r
    assert listaAconjunto3(xs) == r

# 1ª definición de conjuntoAlista
# ===============================

def conjuntoAlista(c: Conj[A]) -> list[A]:
    if esVacio(c):
        return []
    mc = menor(c)
    rc = elimina(mc, c)
    return [mc] + conjuntoAlista(rc)

# 2ª definición de conjuntoAlista
# ===============================

def conjuntoAlista2Aux(c: Conj[A]) -> list[A]:
    if c.esVacio():
        return []
    mc = c.menor()
    c.elimina(mc)
    return [mc] + conjuntoAlista2Aux(c)

def conjuntoAlista2(c: Conj[A]) -> list[A]:
    c1 = deepcopy(c)
    return conjuntoAlista2Aux(c1)

# 3ª definición de conjuntoAlista
# ===============================

def conjuntoAlista3Aux(c: Conj[A]) -> list[A]:
    r = []
    while not c.esVacio():
        mc = c.menor()
        r.append(mc)
        c.elimina(mc)
    return r

def conjuntoAlista3(c: Conj[A]) -> list[A]:
    c1 = deepcopy(c)
    return conjuntoAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de conjuntoAlista
# ==============================================================

@given(c=conjuntoAleatorio())
def test_conjuntoAlista(c: Conj[int]) -> None:
    r = conjuntoAlista(c)
    assert conjuntoAlista2(c) == r
    assert conjuntoAlista3(c) == r

# Comprobación de las propiedades
# ===============================

# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaAconjunto(xs: list[int]) -> None:
    assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))

# La segunda propiedad es
@given(c=conjuntoAleatorio())
def test_2_listaAconjunto(c: Conj[int]) -> None:
    assert listaAconjunto(conjuntoAlista(c)) == c

# La comprobación de las propiedades es
#    > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py
#       test_listaAconjunto PASSED
#       test_conjuntoAlista PASSED
#       test_1_listaAconjunto PASSED
#       test_2_listaAconjunto PASSED

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

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 hypothesis import strategies as st

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª definición de listaAconjunto

# ===============================

def listaAconjunto(xs: list[A]) -> Conj[A]:

if not xs:

return vacio()

return inserta(xs[0], listaAconjunto(xs[1:]))

# 2ª definición de listaAconjunto

# ===============================

def listaAconjunto2(xs: list[A]) -> Conj[A]:

return reduce(lambda ys, y: inserta(y, ys), xs, vacio())

# 3ª solución de listaAconjunto

# =============================

def listaAconjunto3(xs: list[A]) -> Conj[A]:

c: Conj[A] = Conj()

for x in xs:

c.inserta(x)

return c

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()))

def test_listaAconjunto(xs: list[int]) -> None:

r = listaAconjunto(xs)

assert listaAconjunto2(xs) == r

assert listaAconjunto3(xs) == r

# 1ª definición de conjuntoAlista

# ===============================

def conjuntoAlista(c: Conj[A]) -> list[A]:

if esVacio(c):

return []

mc = menor(c)

rc = elimina(mc, c)

return [mc] + conjuntoAlista(rc)

# 2ª definición de conjuntoAlista

# ===============================

def conjuntoAlista2Aux(c: Conj[A]) -> list[A]:

if c.esVacio():

return []

mc = c.menor()

c.elimina(mc)

return [mc] + conjuntoAlista2Aux(c)

def conjuntoAlista2(c: Conj[A]) -> list[A]:

c1 = deepcopy(c)

return conjuntoAlista2Aux(c1)

# 3ª definición de conjuntoAlista

# ===============================

def conjuntoAlista3Aux(c: Conj[A]) -> list[A]:

r = []

while not c.esVacio():

mc = c.menor()

r.append(mc)

c.elimina(mc)

return r

def conjuntoAlista3(c: Conj[A]) -> list[A]:

c1 = deepcopy(c)

return conjuntoAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de conjuntoAlista

# ==============================================================

@given(c=conjuntoAleatorio())

def test_conjuntoAlista(c: Conj[int]) -> None:

r = conjuntoAlista(c)

assert conjuntoAlista2(c) == r

assert conjuntoAlista3(c) == r

# Comprobación de las propiedades

# ===============================

# La primera propiedad es

@given(st.lists(st.integers()))

def test_1_listaAconjunto(xs: list[int]) -> None:

assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))

# La segunda propiedad es

@given(c=conjuntoAleatorio())

def test_2_listaAconjunto(c: Conj[int]) -> None:

assert listaAconjunto(conjuntoAlista(c)) == c

# La comprobación de las propiedades es

# > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py

# test_listaAconjunto PASSED

# test_conjuntoAlista PASSED

# test_1_listaAconjunto PASSED

# test_2_listaAconjunto PASSED

Meses: marzo 2023

Relaciones simétricas

Relaciones reflexivas

Universo y grafo de una relación binaria

Relaciones binarias

TAD de los conjuntos: Producto cartesiano de dos conjuntos

TAD de los conjuntos: Algunos elementos verifican una propiedad

TAD de los conjuntos: Todos los elementos verifican una propiedad

TAD de los conjuntos: Aplicación de una función a los elementos de un conjunto

TAD de los conjuntos: Partición según un número

TAD de los conjuntos: Partición de un conjunto según una propiedad

TAD de los conjuntos: Subconjunto determinado por una propiedad

TAD de los conjuntos: Diferencia simétrica

TAD de los conjuntos: Diferencia de conjuntos

TAD de los conjuntos: Conjuntos disjuntos

TAD de los conjuntos: Intersección de varios conjuntos

TAD de los conjuntos: Intersección de dos conjuntos

TAD de los conjuntos: Unión de varios conjuntos

TAD de los conjuntos: Unión de dos conjuntos

TAD de los conjuntos: Número de elementos de un conjunto

TAD de los conjuntos: Conjunto unitario

TAD de los conjuntos: Reconocimiento de subconjunto propio

TAD de los conjuntos: Reconocimiento de subconjuntos

TAD de los conjuntos: Transformaciones entre conjuntos y listas

Entradas recientes

Buscar

Correo electrónico