Conjuntos – Exercitium

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

El tipo abstracto de datos de los conjuntos

PorJosé A. Alonso 28-febrero-202322-febrero-2023

1. El tipo abstracto de datos de los conjuntos

Un conjunto es una estructura de datos, caracterizada por ser una colección de elementos en la que no importe ni el orden ni la repetición de elementos.

Las operaciones que definen al tipo abstracto de datos (TAD) de los conjuntos (cuyos elementos son del tipo a) son las siguientes:

   vacio      :: Conj a
   inserta    :: Ord a => a -> Conj a -> Conj a
   menor      :: Ord a => Conj a -> a
   elimina    :: Ord a => a -> Conj a -> Conj a
   pertenece  :: Ord a => a -> Conj a -> Bool
   esVacio    :: Conj a -> Bool

vacio :: Conj a

inserta :: Ord a => a -> Conj a -> Conj a

menor :: Ord a => Conj a -> a

elimina :: Ord a => a -> Conj a -> Conj a

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

esVacio :: Conj a -> Bool

tales que

vacio es el conjunto vacío.
(inserta x c) es el conjunto obtenido añadiendo el elemento x al
conjunto c.
(menor c) es el menor elemento del conjunto c.
(elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c.
(pertenece x c) se verifica si x pertenece al conjunto c.
(esVacio c) se verifica si c es el conjunto vacío.

Las operaciones tienen que verificar las siguientes propiedades:

inserta x (inserta x c) == inserta x c
inserta x (inserta y c) == inserta y (inserta x c)
not (pertenece x vacio)
pertenece y (inserta x c) == (x==y) || pertenece y c
elimina x vacio == vacio
Si x == y, entonces elimina x (inserta y c) == elimina x c
Si x /= y, entonces elimina x (inserta y c) == inserta y (elimina x c)
esVacio vacio
not (esVacio (inserta x c))

2. Los conjuntos en Haskell

2.1. El tipo abstracto de datos de los conjuntos en Haskell

El TAD de los conjuntos se encuentra en el módulo Conjunto.hs cuyo contenido es el siguiente:

module TAD.Conjunto
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import TAD.ConjuntoConListasNoOrdenadasConDuplicados
-- import TAD.ConjuntoConListasNoOrdenadasSinDuplicados
-- import TAD.ConjuntoConListasOrdenadasSinDuplicados
-- import TAD.ConjuntosConLibreria

module TAD.Conjunto

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import TAD.ConjuntoConListasNoOrdenadasConDuplicados

-- import TAD.ConjuntoConListasNoOrdenadasSinDuplicados

-- import TAD.ConjuntoConListasOrdenadasSinDuplicados

-- import TAD.ConjuntosConLibreria

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

mediante listas no ordenadas con duplicados,
mediante listas no ordenadas sin duplicados,
mediante listas ordenadas sin duplicados y
mediante la librería de conjuntos.

2.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

La implementación se encuentra en el módulo ConjuntoConListasNoOrdenadasConDuplicados.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConListasNoOrdenadasConDuplicados
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.List (intercalate, nub, sort)
import Test.QuickCheck

-- Conjuntos como listas no ordenadas con repeticiones:
newtype Conj a = Cj [a]

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj [])
--    "{}"
--    λ> escribeConjunto (Cj [5])
--    "{5}"
--    λ> escribeConjunto (Cj [2, 5])
--    "{2, 5}"
--    λ> escribeConjunto (Cj [5, 2, 5])
--    "{2, 5}"
escribeConjunto :: (Show a, Ord a) => Conj a -> String
escribeConjunto (Cj xs) =
  "{" ++ intercalate ", " (map show (sort (nub xs))) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance (Show a, Ord a) => Show (Conj a) where
  show = escribeConjunto

-- Nota: Aunque el conjunto no está ordenado y tenga repeticiones, al
-- escribirlo se hará sin repeticiones y ordenando sus elementos.

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Eq a => a -> Conj a -> Conj a
inserta x (Cj ys) = Cj (x:ys)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj []) = error "conjunto vacío"
menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj ys) = Cj (filter (/= x) ys)

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Eq a => a -> Conj a -> Bool
pertenece x (Cj xs) = x `elem` xs

-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por
-- ejemplo,
--    subconjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
--    subconjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False
subconjunto :: Ord a => Conj a -> Conj a -> Bool
subconjunto (Cj xs) (Cj ys) = sublista xs ys
  where sublista [] _      = True
        sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son
-- iguales. Por ejemplo,
--    igualConjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
--    igualConjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False
igualConjunto :: Ord a => Conj a -> Conj a -> Bool
igualConjunto c c' =
  subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.
instance Ord a => Eq (Conj a) where
  (==) = igualConjunto

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {1}
--    {0, 2, 3}
--    {-6, 5}
--    {2, 5}
--    {-9, -6, 4, 8}
--    {0, 1}
--    {-13, -11, -5, -2, -1, 0, 4, 6, 7, 8, 9, 14}
--    {-7, -5, -2, -1, 1, 2, 10, 13, 15}
--    {-18, -17, -16, -10, -9, 0, 1, 3, 4, 13, 16}
--    {-20, -15, -7, -1, 2, 8, 10, 15, 20}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

module TAD.ConjuntoConListasNoOrdenadasConDuplicados

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.List (intercalate, nub, sort)

import Test.QuickCheck

-- Conjuntos como listas no ordenadas con repeticiones:

newtype Conj a = Cj [a]

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por

-- ejemplo,

-- λ> escribeConjunto (Cj [])

-- "{}"

-- λ> escribeConjunto (Cj [5])

-- "{5}"

-- λ> escribeConjunto (Cj [2, 5])

-- "{2, 5}"

-- λ> escribeConjunto (Cj [5, 2, 5])

-- "{2, 5}"

escribeConjunto :: (Show a, Ord a) => Conj a -> String

escribeConjunto (Cj xs) =

"{" ++ intercalate ", " (map show (sort (nub xs))) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance (Show a, Ord a) => Show (Conj a) where

show = escribeConjunto

-- Nota: Aunque el conjunto no está ordenado y tenga repeticiones, al

-- escribirlo se hará sin repeticiones y ordenando sus elementos.

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Eq a => a -> Conj a -> Conj a

inserta x (Cj ys) = Cj (x:ys)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj []) = error "conjunto vacío"

menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Eq a => a -> Conj a -> Conj a

elimina x (Cj ys) = Cj (filter (/= x) ys)

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

pertenece :: Eq a => a -> Conj a -> Bool

pertenece x (Cj xs) = x `elem` xs

-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por

-- ejemplo,

-- subconjunto (Cj [1,3,2,1]) (Cj [3,1,3,2]) == True

-- subconjunto (Cj [1,3,4,1]) (Cj [3,1,3,2]) == False

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

subconjunto (Cj xs) (Cj ys) = sublista xs ys

where sublista [] _ = True

sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son

-- iguales. Por ejemplo,

-- igualConjunto (Cj [1,3,2,1]) (Cj [3,1,3,2]) == True

-- igualConjunto (Cj [1,3,4,1]) (Cj [3,1,3,2]) == False

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

igualConjunto c c' =

subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.

instance Ord a => Eq (Conj a) where

(==) = igualConjunto

-- Generador de conjuntos --

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

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {1}

-- {0, 2, 3}

-- {-6, 5}

-- {2, 5}

-- {-9, -6, 4, 8}

-- {0, 1}

-- {-13, -11, -5, -2, -1, 0, 4, 6, 7, 8, 9, 14}

-- {-7, -5, -2, -1, 1, 2, 10, 13, 15}

-- {-18, -17, -16, -10, -9, 0, 1, 3, 4, 13, 16}

-- {-20, -15, -7, -1, 2, 8, 10, 15, 20}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

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

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

2.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

La implementación se encuentra en el módulo ConjuntoConListasNoOrdenadasSinDuplicados.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConListasNoOrdenadasSinDuplicados
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.List (intercalate, sort)
import Test.QuickCheck

-- Los conjuntos como listas no ordenadas sin repeticiones.
newtype Conj a = Cj [a]

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj [])
--    "{}"
--    λ> escribeConjunto (Cj [5])
--    "{5}"
--    λ> escribeConjunto (Cj [2, 5])
--    "{2, 5}"
--    λ> escribeConjunto (Cj [5, 2])
--    "{2, 5}"
escribeConjunto :: (Show a, Ord a) => Conj a -> String
escribeConjunto (Cj xs) =
  "{" ++ intercalate ", " (map show (sort xs)) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance (Show a, Ord a) => Show (Conj a) where
  show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Eq a => a -> Conj a -> Conj a
inserta x s@(Cj xs) | pertenece x s = s
                    | otherwise     = Cj (x:xs)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj []) = error "conjunto vacío"
menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj [y | y <- s, y /= x]

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Eq a => a -> Conj a -> Bool
pertenece x (Cj xs) = x `elem` xs

-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por
-- ejemplo,
--    subconjunto (Cj [1,3,2]) (Cj [3,1,2])    ==  True
--    subconjunto (Cj [1,3,4,1]) (Cj [1,3,2])  ==  False
subconjunto :: Ord a => Conj a -> Conj a -> Bool
subconjunto (Cj xs) (Cj ys) = sublista xs ys
  where sublista [] _      = True
        sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son
-- iguales. Por ejemplo,
--    igualConjunto (Cj [3,2,1]) (Cj [1,3,2])  ==  True
--    igualConjunto (Cj [1,3,4]) (Cj [1,3,2])  ==  False
igualConjunto :: Ord a => Conj a -> Conj a -> Bool
igualConjunto c c' =
  subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.
instance Ord a => Eq (Conj a) where
  (==) = igualConjunto

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {-1, 0}
--    {-4, 1, 2}
--    {-3, 0, 2, 3, 4}
--    {-7}
--    {-10, -7, -5, -2, -1, 2, 5, 8}
--    {5, 7, 8, 10}
--    {-9, -6, -3, 8}
--    {-8, -6, -5, -1, 7, 9, 14}
--    {-18, -15, -14, -13, -3, -2, 1, 2, 4, 8, 12, 17}
--    {-17, -16, -13, -12, -11, -9, -6, -3, 0, 1, 3, 5, 6, 7, 16, 18}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

module TAD.ConjuntoConListasNoOrdenadasSinDuplicados

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.List (intercalate, sort)

import Test.QuickCheck

-- Los conjuntos como listas no ordenadas sin repeticiones.

newtype Conj a = Cj [a]

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por

-- ejemplo,

-- λ> escribeConjunto (Cj [])

-- "{}"

-- λ> escribeConjunto (Cj [5])

-- "{5}"

-- λ> escribeConjunto (Cj [2, 5])

-- "{2, 5}"

-- λ> escribeConjunto (Cj [5, 2])

-- "{2, 5}"

escribeConjunto :: (Show a, Ord a) => Conj a -> String

escribeConjunto (Cj xs) =

"{" ++ intercalate ", " (map show (sort xs)) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance (Show a, Ord a) => Show (Conj a) where

show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Eq a => a -> Conj a -> Conj a

inserta x s@(Cj xs) | pertenece x s = s

| otherwise = Cj (x:xs)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj []) = error "conjunto vacío"

menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Eq a => a -> Conj a -> Conj a

elimina x (Cj s) = Cj [y | y <- s, y /= x]

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

pertenece :: Eq a => a -> Conj a -> Bool

pertenece x (Cj xs) = x `elem` xs

-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por

-- ejemplo,

-- subconjunto (Cj [1,3,2]) (Cj [3,1,2]) == True

-- subconjunto (Cj [1,3,4,1]) (Cj [1,3,2]) == False

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

subconjunto (Cj xs) (Cj ys) = sublista xs ys

where sublista [] _ = True

sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son

-- iguales. Por ejemplo,

-- igualConjunto (Cj [3,2,1]) (Cj [1,3,2]) == True

-- igualConjunto (Cj [1,3,4]) (Cj [1,3,2]) == False

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

igualConjunto c c' =

subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.

instance Ord a => Eq (Conj a) where

(==) = igualConjunto

-- Generador de conjuntos --

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

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {-1, 0}

-- {-4, 1, 2}

-- {-3, 0, 2, 3, 4}

-- {-7}

-- {-10, -7, -5, -2, -1, 2, 5, 8}

-- {5, 7, 8, 10}

-- {-9, -6, -3, 8}

-- {-8, -6, -5, -1, 7, 9, 14}

-- {-18, -15, -14, -13, -3, -2, 1, 2, 4, 8, 12, 17}

-- {-17, -16, -13, -12, -11, -9, -6, -3, 0, 1, 3, 5, 6, 7, 16, 18}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

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

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

2.4. Implementación de los conjuntos mediante listas ordenadas sin repeticiones

La implementación se encuentra en el módulo ConjuntoConListasOrdenadasSinDuplicados.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConListasOrdenadasSinDuplicados
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.List (intercalate)
import Test.QuickCheck

-- Los conjuntos como listas ordenadas sin repeticiones.
newtype Conj a = Cj [a]
  deriving Eq

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj [])
--    "{}"
--    λ> escribeConjunto (Cj [5])
--    "{5}"
--    λ> escribeConjunto (Cj [2, 5])
--    "{2, 5}"
--    λ> escribeConjunto (Cj [5, 2])
--    "{2, 5}"
escribeConjunto :: Show a => Conj a -> String
escribeConjunto (Cj xs) =
  "{" ++ intercalate ", " (map show xs) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance Show a => Show (Conj a) where
  show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Ord a => a -> Conj a -> Conj a
inserta x (Cj s) = Cj (agrega x s)
  where agrega z []                     = [z]
        agrega z s'@(y:ys) | z > y      = y : agrega z ys
                           | z < y      = z : s'
                           | otherwise  = s'

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj [])    = error "conjunto vacío"
menor (Cj (x:_)) = x

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Ord a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj (elimina' x s)
  where elimina' _ []                    = []
        elimina' z s'@(y:ys) | z > y     = y : elimina' z ys
                             | z < y     = s'
                             | otherwise = ys

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Ord a => a -> Conj a -> Bool
pertenece x (Cj s) = x `elem` takeWhile (<= x) s

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {1}
--    {2}
--    {}
--    {-5, -1}
--    {-9, -8, 2, 3, 10}
--    {4}
--    {-13, -7, 1, 14}
--    {-12, -10, -9, -4, 1, 2, 5, 14, 16}
--    {-18, -15, -14, -13, -10, -7, -6, -4, -1, 1, 10, 11, 12, 16}
--    {-16, -9, -6, -5, -4, -2, 3, 6, 9, 13, 17}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

module TAD.ConjuntoConListasOrdenadasSinDuplicados

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.List (intercalate)

import Test.QuickCheck

-- Los conjuntos como listas ordenadas sin repeticiones.

newtype Conj a = Cj [a]

deriving Eq

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por

-- ejemplo,

-- λ> escribeConjunto (Cj [])

-- "{}"

-- λ> escribeConjunto (Cj [5])

-- "{5}"

-- λ> escribeConjunto (Cj [2, 5])

-- "{2, 5}"

-- λ> escribeConjunto (Cj [5, 2])

-- "{2, 5}"

escribeConjunto :: Show a => Conj a -> String

escribeConjunto (Cj xs) =

"{" ++ intercalate ", " (map show xs) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance Show a => Show (Conj a) where

show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Ord a => a -> Conj a -> Conj a

inserta x (Cj s) = Cj (agrega x s)

where agrega z [] = [z]

agrega z s'@(y:ys) | z > y = y : agrega z ys

| z < y = z : s'

| otherwise = s'

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj []) = error "conjunto vacío"

menor (Cj (x:_)) = x

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Ord a => a -> Conj a -> Conj a

elimina x (Cj s) = Cj (elimina' x s)

where elimina' _ [] = []

elimina' z s'@(y:ys) | z > y = y : elimina' z ys

| z < y = s'

| otherwise = ys

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

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

pertenece x (Cj s) = x `elem` takeWhile (<= x) s

-- Generador de conjuntos --

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

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {1}

-- {2}

-- {}

-- {-5, -1}

-- {-9, -8, 2, 3, 10}

-- {4}

-- {-13, -7, 1, 14}

-- {-12, -10, -9, -4, 1, 2, 5, 14, 16}

-- {-18, -15, -14, -13, -10, -7, -6, -4, -1, 1, 10, 11, 12, 16}

-- {-16, -9, -6, -5, -4, -2, 3, 6, 9, 13, 17}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

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

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

2.5. Implementación de los conjuntos mediante librería

La implementación se encuentra en el módulo ConjuntoConLibreria.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConLibreria
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.Set as S (Set, empty, insert, findMin, delete, member, null,
                      fromList, toList)
import Data.List (intercalate)
import Test.QuickCheck

-- Los conjuntos como conjuntos de la librería Data.Set
newtype Conj a = Cj (Set a)
  deriving (Eq, Ord)

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj (fromList []))
--    "{}"
--    λ> escribeConjunto (Cj (fromList [5]))
--    "{5}"
--    λ> escribeConjunto (Cj (fromList [2, 5]))
--    "{2, 5}"
--    λ> escribeConjunto (Cj (fromList [5, 2]))
--    "{2, 5}"
escribeConjunto :: Show a => Conj a -> String
escribeConjunto (Cj s) =
  "{" ++ intercalate ", " (map show (toList s)) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance Show a => Show (Conj a) where
  show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj empty

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Ord a => a -> Conj a -> Conj a
inserta x (Cj s) = Cj (insert x s)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj s) = findMin s

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Ord a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj (delete x s)

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj s) = S.null s

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Ord a => a -> Conj a -> Bool
pertenece x (Cj s) = member x s

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {-2, 0}
--    {-1, 3}
--    {-3, 2}
--    {-5, -4, -3, 2, 4, 6, 7}
--    {-4, 4}
--    {-9, -6, -3, 1, 5, 11, 12}
--    {-10, -8, -7, -3, 1, 2, 8, 9, 10, 13}
--    {-13, -8, -7, -6, -1, 0, 1, 6, 7, 9, 11, 14, 16}
--    {-15, -12, -9, 1, 2, 9, 13, 15, 16, 18}
--    {-16}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (Cj (fromList xs))

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

module TAD.ConjuntoConLibreria

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.Set as S (Set, empty, insert, findMin, delete, member, null,

fromList, toList)

import Data.List (intercalate)

import Test.QuickCheck

-- Los conjuntos como conjuntos de la librería Data.Set

newtype Conj a = Cj (Set a)

deriving (Eq, Ord)

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por

-- ejemplo,

-- λ> escribeConjunto (Cj (fromList []))

-- "{}"

-- λ> escribeConjunto (Cj (fromList [5]))

-- "{5}"

-- λ> escribeConjunto (Cj (fromList [2, 5]))

-- "{2, 5}"

-- λ> escribeConjunto (Cj (fromList [5, 2]))

-- "{2, 5}"

escribeConjunto :: Show a => Conj a -> String

escribeConjunto (Cj s) =

"{" ++ intercalate ", " (map show (toList s)) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance Show a => Show (Conj a) where

show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj empty

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Ord a => a -> Conj a -> Conj a

inserta x (Cj s) = Cj (insert x s)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj s) = findMin s

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Ord a => a -> Conj a -> Conj a

elimina x (Cj s) = Cj (delete x s)

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj s) = S.null s

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

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

pertenece x (Cj s) = member x s

-- Generador de conjuntos --

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

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {-2, 0}

-- {-1, 3}

-- {-3, 2}

-- {-5, -4, -3, 2, 4, 6, 7}

-- {-4, 4}

-- {-9, -6, -3, 1, 5, 11, 12}

-- {-10, -8, -7, -3, 1, 2, 8, 9, 10, 13}

-- {-13, -8, -7, -6, -1, 0, 1, 6, 7, 9, 11, 14, 16}

-- {-15, -12, -9, 1, 2, 9, 13, 15, 16, 18}

-- {-16}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (Cj (fromList xs))

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

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

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

3. Los conjuntos en Python

3.1. El tipo abstracto de los conjuntos en Python

La implementación se encuentra en el módulo conjunto.py cuyo contenido es el siguiente:

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

# from src.TAD.conjuntoConListasNoOrdenadasConDuplicados import (
#     Conj, conjuntoAleatorio, elimina, esVacio, inserta,
#     menor, pertenece, vacio)

# from src.TAD.conjuntoConListasNoOrdenadasSinDuplicados import (
#     Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,
#     vacio)

from src.TAD.conjuntoConListasOrdenadasSinDuplicados import (
    Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,
    vacio)

# from src.TAD.conjuntoConLibreria import (
#     Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,
#     vacio)

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

# from src.TAD.conjuntoConListasNoOrdenadasConDuplicados import (

# Conj, conjuntoAleatorio, elimina, esVacio, inserta,

# menor, pertenece, vacio)

# from src.TAD.conjuntoConListasNoOrdenadasSinDuplicados import (

# Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,

# vacio)

from src.TAD.conjuntoConListasOrdenadasSinDuplicados import (

Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,

vacio)

# from src.TAD.conjuntoConLibreria import (

# Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,

# vacio)

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

mediante listas no ordenadas con duplicados,
mediante listas no ordenadas sin duplicados,
mediante listas ordenadas sin duplicados y
mediante la librería de conjuntos.

3.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

La implementación se encuentra en el módulo conjuntoConListasNoOrdenadasConDuplicados.py en el que se define la clase Conj con los siguientes métodos:

inserta(x) añade x al conjunto.
menor() es el menor elemento del conjunto.
elimina(x) elimina las ocurrencias de x en el conjunto.
pertenece(x) se verifica si x pertenece al conjunto.
esVacia() se verifica si la cola es vacía.

Por ejemplo,

   >>> c = Conj()
   >>> c
   {}
   >>> c.inserta(5)
   >>> c.inserta(2)
   >>> c.inserta(3)
   >>> c.inserta(4)
   >>> c.inserta(5)
   >>> c
   {2, 3, 4, 5}
   >>> c.menor()
   2
   >>> c.elimina(3)
   >>> c
   {2, 4, 5}
   >>> c.pertenece(4)
   True
   >>> c.pertenece(3)
   False
   >>> c.esVacio()
   False
   >>> c = Conj()
   >>> c.esVacio()
   True
   >>> c = Conj()
   >>> c.inserta(2)
   >>> c.inserta(5)
   >>> d = Conj()
   >>> d.inserta(5)
   >>> d.inserta(2)
   >>> d.inserta(5)
   >>> c == d
   True

>>> c = Conj()

>>> c

{}

>>> c.inserta(5)

>>> c.inserta(2)

>>> c.inserta(3)

>>> c.inserta(4)

>>> c.inserta(5)

>>> c

{2, 3, 4, 5}

>>> c.menor()

>>> c.elimina(3)

>>> c

{2, 4, 5}

>>> c.pertenece(4)

True

>>> c.pertenece(3)

False

>>> c.esVacio()

False

>>> c = Conj()

>>> c.esVacio()

True

>>> c = Conj()

>>> c.inserta(2)

>>> c.inserta(5)

>>> d = Conj()

>>> d.inserta(5)

>>> d.inserta(2)

>>> d.inserta(5)

>>> c == d

True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacio()
   {}
   >>> inserta(5, inserta(3, inserta(2, inserta(5, vacio()))))
   {2, 3, 5}
   >>> menor(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   2
   >>> elimina(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   {2, 3}
   >>> pertenece(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   True
   >>> pertenece(1, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   False
   >>> esVacio(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   False
   >>> esVacio(vacio())
   True
   >>> inserta(5, inserta(2, vacio())) == inserta(2, inserta(5, (inserta(2, vacio()))))
   True

>>> vacio()

{}

>>> inserta(5, inserta(3, inserta(2, inserta(5, vacio()))))

{2, 3, 5}

>>> menor(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

>>> elimina(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

{2, 3}

>>> pertenece(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

True

>>> pertenece(1, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

False

>>> esVacio(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

False

>>> esVacio(vacio())

True

>>> inserta(5, inserta(2, vacio())) == inserta(2, inserta(5, (inserta(2, vacio()))))

True

Finalmente, se define un generador aleatorio de conjuntos y se comprueba que los conjuntos cumplen las propiedades de su especificación.

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

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

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

# Clase de los conjuntos mediante listas no ordenadas con duplicados
# ==================================================================

@dataclass
class Conj(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos del conjunto entre llaves
        y separados por ", ".
        """
        return '{' + ', '.join(str(x) for x in sorted(list(set(self._elementos)))) + '}'

    def __eq__(self, c: Any) -> bool:
        """
        Se verifica si el conjunto es igual a c; es decir, tienen los
        mismos elementos sin importar el orden ni las repeticiones.
        """
        return sorted(list(set(self._elementos))) == sorted(list(set(c._elementos)))

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        self._elementos.append(x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return min(self._elementos)

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        while x in self._elementos:
            self._elementos.remove(x)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in self._elementos

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Genera una estrategia de búsqueda para generar conjuntos de enteros
    de forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase cola.
    """
    return st.lists(st.integers()).map(Conj)

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    v: Conj[int] = vacio()
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, v)
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, v) == v

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

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

pass

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

# Clase de los conjuntos mediante listas no ordenadas con duplicados

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

@dataclass

class Conj(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos del conjunto entre llaves

y separados por ", ".

"""

return '{' + ', '.join(str(x) for x in sorted(list(set(self._elementos)))) + '}'

def __eq__(self, c: Any) -> bool:

"""

Se verifica si el conjunto es igual a c; es decir, tienen los

mismos elementos sin importar el orden ni las repeticiones.

"""

return sorted(list(set(self._elementos))) == sorted(list(set(c._elementos)))

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

self._elementos.append(x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return min(self._elementos)

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

while x in self._elementos:

self._elementos.remove(x)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in self._elementos

# Funciones del tipo conjunto

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

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

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

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

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

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

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

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Genera una estrategia de búsqueda para generar conjuntos de enteros

de forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase cola.

"""

return st.lists(st.integers()).map(Conj)

# Comprobación de las propiedades de los conjuntos

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

# Las propiedades son

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

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

v: Conj[int] = vacio()

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, v)

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, v) == v

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConListasNoOrdenadasConDuplicados.py

# 1 passed in 0.33s

3.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

La implementación se encuentra en el módulo conjuntoConListasNoOrdenadasSinDuplicados.py cuyo contenido es

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

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

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

# Clase de los conjuntos mediante listas no ordenadas sin duplicados
# ==================================================================

@dataclass
class Conj(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos del conjunto entre llaves
        y separados por ", ".
        """
        return '{' + ', '.join(str(x) for x in sorted(self._elementos)) + '}'

    def __eq__(self, c: Any) -> bool:
        """
        Se verifica si el conjunto es igual a c; es decir, tienen los
        mismos elementos sin importar el orden ni las repeticiones.
        """
        return sorted(self._elementos) == sorted(c._elementos)

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        if x not in self._elementos:
            self._elementos.append(x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return min(self._elementos)

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        if x in self._elementos:
            self._elementos.remove(x)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in self._elementos

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def sin_duplicados(xs: list[int]) -> list[int]:
    return list(set(xs))

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Estrategia de búsqueda para generar conjuntos de enteros de forma
    aleatoria.
    """
    xs = st.lists(st.integers()).map(sin_duplicados)
    return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, vacio())
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, vacio()) == vacio()

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

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

pass

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

# Clase de los conjuntos mediante listas no ordenadas sin duplicados

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

@dataclass

class Conj(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos del conjunto entre llaves

y separados por ", ".

"""

return '{' + ', '.join(str(x) for x in sorted(self._elementos)) + '}'

def __eq__(self, c: Any) -> bool:

"""

Se verifica si el conjunto es igual a c; es decir, tienen los

mismos elementos sin importar el orden ni las repeticiones.

"""

return sorted(self._elementos) == sorted(c._elementos)

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

if x not in self._elementos:

self._elementos.append(x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return min(self._elementos)

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

if x in self._elementos:

self._elementos.remove(x)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in self._elementos

# Funciones del tipo conjunto

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

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

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

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

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

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

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

def sin_duplicados(xs: list[int]) -> list[int]:

return list(set(xs))

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Estrategia de búsqueda para generar conjuntos de enteros de forma

aleatoria.

"""

xs = st.lists(st.integers()).map(sin_duplicados)

return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos

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

# Las propiedades son

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

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

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, vacio())

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, vacio()) == vacio()

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConListasNoOrdenadasSinDuplicados.py

# 1 passed in 0.26s

3.4. Implementación de los conjuntos mediante listas ordenadas sin duplicados

La implementación se encuentra en el módulo conjuntoConListasOrdenadasSinDuplicados.py cuyo contenido es el siguiente:

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from bisect import bisect_left, insort_left
from copy import deepcopy
from dataclasses import dataclass, field
from itertools import takewhile
from typing import Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

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

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

# Clase de los conjuntos mediante listas ordenadas sin duplicados
# ===============================================================

@dataclass
class Conj(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos del conjunto entre llaves
        y separados por ", ".
        """
        return '{' + ', '.join(str(x) for x in self._elementos) + '}'

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        if x not in self._elementos:
            insort_left(self._elementos, x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return self._elementos[0]

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        pos = bisect_left(self._elementos, x)
        if pos < len(self._elementos) and self._elementos[pos] == x:
            self._elementos.pop(pos)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in takewhile(lambda y: y <= x, self._elementos)

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def sin_duplicados_y_ordenado(xs: list[int]) -> list[int]:
    xs = list(set(xs))
    xs.sort()
    return xs

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Estrategia de búsqueda para generar conjuntos de enteros de forma
    aleatoria.
    """
    xs = st.lists(st.integers()).map(sin_duplicados_y_ordenado)
    return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, vacio())
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, vacio()) == vacio()

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from bisect import bisect_left, insort_left

from copy import deepcopy

from dataclasses import dataclass, field

from itertools import takewhile

from typing import Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

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

pass

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

# Clase de los conjuntos mediante listas ordenadas sin duplicados

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

@dataclass

class Conj(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos del conjunto entre llaves

y separados por ", ".

"""

return '{' + ', '.join(str(x) for x in self._elementos) + '}'

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

if x not in self._elementos:

insort_left(self._elementos, x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return self._elementos[0]

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

pos = bisect_left(self._elementos, x)

if pos < len(self._elementos) and self._elementos[pos] == x:

self._elementos.pop(pos)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in takewhile(lambda y: y <= x, self._elementos)

# Funciones del tipo conjunto

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

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

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

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

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

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

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

def sin_duplicados_y_ordenado(xs: list[int]) -> list[int]:

xs = list(set(xs))

xs.sort()

return xs

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Estrategia de búsqueda para generar conjuntos de enteros de forma

aleatoria.

"""

xs = st.lists(st.integers()).map(sin_duplicados_y_ordenado)

return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos

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

# Las propiedades son

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

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

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, vacio())

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, vacio()) == vacio()

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConListasOrdenadasSinDuplicados.py

# 1 passed in 0.13s

3.5. Implementación de los conjuntos mediante librería

La implementación se encuentra en el módulo conjuntoConLibreria.py cuyo contenido es el siguiente:

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

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

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

# Clase de los conjuntos mediante librería
# ========================================

@dataclass
class Conj(Generic[A]):
    _elementos: set[A] = field(default_factory=set)

    def __repr__(self) -> str:
        xs = [str(x) for x in self._elementos]
        return "{" + ", ".join(xs) + "}"

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        self._elementos.add(x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return min(self._elementos)

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        self._elementos.discard(x)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in self._elementos

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Estrategia de búsqueda para generar conjuntos de enteros de forma
    aleatoria.
    """
    return st.builds(Conj, st.lists(st.integers()).map(set))

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, vacio())
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, vacio()) == vacio()

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

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

pass

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

# Clase de los conjuntos mediante librería

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

@dataclass

class Conj(Generic[A]):

_elementos: set[A] = field(default_factory=set)

def __repr__(self) -> str:

xs = [str(x) for x in self._elementos]

return "{" + ", ".join(xs) + "}"

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

self._elementos.add(x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return min(self._elementos)

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

self._elementos.discard(x)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in self._elementos

# Funciones del tipo conjunto

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

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

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

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

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

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

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

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Estrategia de búsqueda para generar conjuntos de enteros de forma

aleatoria.

"""

return st.builds(Conj, st.lists(st.integers()).map(set))

# Comprobación de las propiedades de los conjuntos

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

# Las propiedades son

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

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

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, vacio())

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, vacio()) == vacio()

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConLibreria.py

# 1 passed in 0.22s

Subexpresiones aritméticas

PorJosé A. Alonso 4-junio-20202-enero-2021

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

   data Expr = N Int | S Expr Expr | P Expr Expr  
     deriving (Eq, Ord, Show)

1 2	data Expr = N Int \| S Expr Expr \| P Expr Expr deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

   P (N 2) (S (N 3) (N 7))

1	P (N 2) (S (N 3) (N 7))

Definir la función

   subexpresiones :: Expr -> Set Expr

1	subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

   λ> subexpresiones (S (N 2) (N 3))
   fromList [N 2,N 3,S (N 2) (N 3)]
   λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
   fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

λ> subexpresiones (S (N 2) (N 3))

fromList [N 2,N 3,S (N 2) (N 3)]

λ> subexpresiones (P (S (N 2) (N 2)) (N 7))

fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Soluciones

import Data.Set

data Expr = N Int | S Expr Expr | P Expr Expr  
  deriving (Eq, Ord, Show)

subexpresiones :: Expr -> Set Expr
subexpresiones (N x)   = singleton (N x)
subexpresiones (S i d) =
  S i d `insert` (subexpresiones i `union` subexpresiones d)
subexpresiones (P i d) =
  P i d `insert` (subexpresiones i `union` subexpresiones d)

import Data.Set

data Expr = N Int | S Expr Expr | P Expr Expr

deriving (Eq, Ord, Show)

subexpresiones :: Expr -> Set Expr

subexpresiones (N x) = singleton (N x)

subexpresiones (S i d) =

S i d `insert` (subexpresiones i `union` subexpresiones d)

subexpresiones (P i d) =

P i d `insert` (subexpresiones i `union` subexpresiones d)

Subexpresiones aritméticas

PorJosé A. Alonso 31-mayo-201825-abril-2021

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

   data Expr = N Int | S Expr Expr | P Expr Expr  
     deriving (Eq, Ord, Show)

1 2	data Expr = N Int \| S Expr Expr \| P Expr Expr deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

   P (N 2) (S (N 3) (N 7))

1	P (N 2) (S (N 3) (N 7))

Definir la función

   subexpresiones :: Expr -> Set Expr

1	subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

   λ> subexpresiones (S (N 2) (N 3))
   fromList [N 2,N 3,S (N 2) (N 3)]
   λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
   fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

λ> subexpresiones (S (N 2) (N 3))

fromList [N 2,N 3,S (N 2) (N 3)]

λ> subexpresiones (P (S (N 2) (N 2)) (N 7))

fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Soluciones

import Data.Set

data Expr = N Int | S Expr Expr | P Expr Expr  
  deriving (Eq, Ord, Show)

subexpresiones :: Expr -> Set Expr
subexpresiones (N x)   = singleton (N x)
subexpresiones (S i d) =
  S i d `insert` (subexpresiones i `union` subexpresiones d)
subexpresiones (P i d) =
  P i d `insert` (subexpresiones i `union` subexpresiones d)

import Data.Set

data Expr = N Int | S Expr Expr | P Expr Expr

deriving (Eq, Ord, Show)

subexpresiones :: Expr -> Set Expr

subexpresiones (N x) = singleton (N x)

subexpresiones (S i d) =

S i d `insert` (subexpresiones i `union` subexpresiones d)

subexpresiones (P i d) =

P i d `insert` (subexpresiones i `union` subexpresiones d)

Grafo de divisibilidad

PorJosé A. Alonso 14-mayo-201825-abril-2021

El grafo de divisibilidad de orden n es el grafo cuyos nodos son los números naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x. El coste de cada arista es el cociente entre su mayor y menor elemento.

Definir las siguientes funciones:

   grafoDivisibilidad :: Int -> Grafo Int Int
   coste              :: Int -> Int

1 2	grafoDivisibilidad :: Int -> Grafo Int Int coste :: Int -> Int

tales que

(grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,

      λ> grafoDivisibilidad 12
      G ND (array (1,12)
                  [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),
                       (8,8),(9,9),(10,10),(11,11),(12,12)]),
                   (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),
                   (3,[(1,3),(6,2),(9,3),(12,4)]),
                   (4,[(1,4),(2,2),(8,2),(12,3)]),
                   (5,[(1,5),(10,2)]),
                   (6,[(1,6),(2,3),(3,2),(12,2)]),
                   (7,[(1,7)]),
                   (8,[(1,8),(2,4),(4,2)]),
                   (9,[(1,9),(3,3)]),
                   (10,[(1,10),(2,5),(5,2)]),
                   (11,[(1,11)]),
                   (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])

λ> grafoDivisibilidad 12

G ND (array (1,12)

[(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),

(8,8),(9,9),(10,10),(11,11),(12,12)]),

(2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),

(3,[(1,3),(6,2),(9,3),(12,4)]),

(4,[(1,4),(2,2),(8,2),(12,3)]),

(5,[(1,5),(10,2)]),

(6,[(1,6),(2,3),(3,2),(12,2)]),

(7,[(1,7)]),

(8,[(1,8),(2,4),(4,2)]),

(9,[(1,9),(3,3)]),

(10,[(1,10),(2,5),(5,2)]),

(11,[(1,11)]),

(12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])

(coste n) es el coste del árbol de expansión mínimo del grafo de divisibilidad de orden n. Por ejemplo,

      coste 12        ==  41
      coste 3000      ==  605305
      coste (2*10^5)  ==  1711798835

coste 12 == 41

coste 3000 == 605305

coste (2*10^5) == 1711798835

Soluciones

import Data.Ix
import Data.List (delete, sort)
import qualified Data.Set as S
import I1M.Grafo
import I1M.Tabla
import Data.Numbers.Primes (primeFactors)

grafoDivisibilidad :: Int -> Grafo Int Int
grafoDivisibilidad n =
  creaGrafo ND (1,n) [(x,y,y `div` x) | y <- [1..n]
                                      , x <- [1..y-1]
                                      , y `mod` x == 0]

-- 1ª solución (con el algoritmo de Kruskal)
-- =========================================

coste1 :: Int -> Int
coste1 n = sum [p | (p,x,y) <- kruskal (grafoDivisibilidad n)]

-- (kruskal g) es el árbol de expansión mínimo del grafo g calculado
-- mediante el algoritmo de Kruskal. Por ejemplo,
--    λ> kruskal (grafoDivisibilidad 12)
--    [(11,1,11),(7,1,7),(5,1,5),(3,3,9),(3,1,3),(2,6,12),(2,5,10),
--     (2,4,8),(2,3,6),(2,2,4),(2,1,2)]
kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
kruskal g = kruskal' cola                           -- Cola ordenada
                     (tabla [(x,x) | x <- nodos g]) -- Tabla de raices
                     []                             -- Árbol de expansión
                     (length (nodos g) - 1)         -- Aristas por
                                                    -- colocar
    where cola = sort [(p,x,y) | (x,y,p) <- aristas g]

kruskal' ((p,x,y):as) t ae n 
  | n == 0      = ae
  | actualizado = kruskal' as t' ((p,x,y):ae) (n-1)
  | otherwise   = kruskal' as t  ae           n
  where (actualizado,t') = buscaActualiza (x,y) t

-- (raiz t n) es la raíz de n en la tabla t. Por ejemplo,
--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5  == 1
--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2  == 6
raiz:: Eq n => Tabla n n -> n -> n
raiz t x | v == x    = v
         | otherwise = raiz t v
         where v = valor t x

-- (buscaActualiza a t) es el par formado por False y la tabla t, si los
-- dos vértices de la arista a tienen la misma raíz en t y el par
-- formado por True y la tabla obtenida añadiéndole a t la arista
-- formada por el vértice de a de mayor raíz y la raíz del vértice de
-- a de menor raíz. Por ejemplo,
--    ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)]
--    ghci> buscaActualiza (2,3) t
--    (True,Tbl [(1,1),(2,1),(3,1),(4,1)])
--    ghci> buscaActualiza (3,4) t
--    (False,Tbl [(1,1),(2,2),(3,1),(4,1)])
buscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n -> (Bool,Tabla n n)
buscaActualiza (x,y) t 
  | x' == y'  = (False, t) 
  | y' <  x'  = (True, modifica (x,y') t)
  | otherwise = (True, modifica (y,x') t)
  where x' = raiz t x 
        y' = raiz t y

-- 2ª solución (con el algoritmo de Prim)
-- ======================================

coste2 :: Int -> Int
coste2 n = sum [p | (p,x,y) <- prim (grafoDivisibilidad n)]

-- (prim g) es el árbol de expansión mínimo del grafo g calculado
-- mediante el algoritmo de Prim. Por ejemplo,
--    λ> prim (grafoDivisibilidad 12)
--    [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),
--     (3,1,3),(2,4,8),(2,2,4),(2,1,2)]
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
prim g = prim' [n]              -- Nodos colocados
               ns               -- Nodos por colocar 
               []               -- Árbol de expansión
               (aristas g)      -- Aristas del grafo
         where (n:ns) = nodos g

prim' t [] ae as = ae
prim' t r  ae as = prim' (v':t) (delete v' r) (e:ae) as
  where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,
                                         u `elem` t, 
                                         v `elem` r]

-- 3ª solución (con el algoritmo de Prim con conjuntos)
-- ====================================================

coste3 :: Int -> Int
coste3 n = sum [p | (p,x,y) <- prim2 (grafoDivisibilidad n)]

-- (prim2 g) es el árbol de expansión mínimo del grafo g calculado
-- mediante el algoritmo de Prim. Por ejemplo,
--    λ> prim2 (grafoDivisibilidad 12)
--    [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),
--     (3,1,3),(2,4,8),(2,2,4),(2,1,2)]
prim2 :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
prim2 g = prim2' (S.singleton n)  -- Nodos colocados
                 (S.fromList ns)  -- Nodos por colocar 
                 []               -- Árbol de expansión
                 (aristas g)      -- Aristas del grafo
  where (n:ns) = nodos g

prim2' t r ae as
  | S.null r  = ae
  | otherwise = prim2' (S.insert v' t)
                       (S.delete v' r)
                       (e:ae)
                       as
  where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,
                                         S.member u t, 
                                         S.member v r]

-- 4ª solución
-- ===========

coste4 :: Int -> Int
coste4 n = sum [head (primeFactors x) | x <- [2..n]]

-- Comparación de eficiencia
-- =========================

--    λ> coste1 400
--    14923
--    (0.08 secs, 31,336,440 bytes)
--    λ> coste2 400
--    14923
--    (4.54 secs, 220,745,608 bytes)
--    λ> coste3 400
--    14923
--    (0.69 secs, 217,031,144 bytes)
--    λ> coste4 400
--    14923
--    (0.01 secs, 2,192,336 bytes)
--    
--    λ> coste1 2000
--    284105
--    (2.09 secs, 842,601,904 bytes)
--    λ> coste4 2000
--    284105
--    (0.02 secs, 14,586,888 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

import Data.Ix

import Data.List (delete, sort)

import qualified Data.Set as S

import I1M.Grafo

import I1M.Tabla

import Data.Numbers.Primes (primeFactors)

grafoDivisibilidad :: Int -> Grafo Int Int

grafoDivisibilidad n =

creaGrafo ND (1,n) [(x,y,y `div` x) | y <- [1..n]

, x <- [1..y-1]

, y `mod` x == 0]

-- 1ª solución (con el algoritmo de Kruskal)

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

coste1 :: Int -> Int

coste1 n = sum [p | (p,x,y) <- kruskal (grafoDivisibilidad n)]

-- (kruskal g) es el árbol de expansión mínimo del grafo g calculado

-- mediante el algoritmo de Kruskal. Por ejemplo,

-- λ> kruskal (grafoDivisibilidad 12)

-- [(11,1,11),(7,1,7),(5,1,5),(3,3,9),(3,1,3),(2,6,12),(2,5,10),

-- (2,4,8),(2,3,6),(2,2,4),(2,1,2)]

kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

kruskal g = kruskal' cola -- Cola ordenada

(tabla [(x,x) | x <- nodos g]) -- Tabla de raices

[] -- Árbol de expansión

(length (nodos g) - 1) -- Aristas por

-- colocar

where cola = sort [(p,x,y) | (x,y,p) <- aristas g]

kruskal' ((p,x,y):as) t ae n

| n == 0 = ae

| actualizado = kruskal' as t' ((p,x,y):ae) (n-1)

| otherwise = kruskal' as t ae n

where (actualizado,t') = buscaActualiza (x,y) t

-- (raiz t n) es la raíz de n en la tabla t. Por ejemplo,

-- raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5 == 1

-- raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2 == 6

raiz:: Eq n => Tabla n n -> n -> n

raiz t x | v == x = v

| otherwise = raiz t v

where v = valor t x

-- (buscaActualiza a t) es el par formado por False y la tabla t, si los

-- dos vértices de la arista a tienen la misma raíz en t y el par

-- formado por True y la tabla obtenida añadiéndole a t la arista

-- formada por el vértice de a de mayor raíz y la raíz del vértice de

-- a de menor raíz. Por ejemplo,

-- ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)]

-- ghci> buscaActualiza (2,3) t

-- (True,Tbl [(1,1),(2,1),(3,1),(4,1)])

-- ghci> buscaActualiza (3,4) t

-- (False,Tbl [(1,1),(2,2),(3,1),(4,1)])

buscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n -> (Bool,Tabla n n)

buscaActualiza (x,y) t

| x' == y' = (False, t)

| y' < x' = (True, modifica (x,y') t)

| otherwise = (True, modifica (y,x') t)

where x' = raiz t x

y' = raiz t y

-- 2ª solución (con el algoritmo de Prim)

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

coste2 :: Int -> Int

coste2 n = sum [p | (p,x,y) <- prim (grafoDivisibilidad n)]

-- (prim g) es el árbol de expansión mínimo del grafo g calculado

-- mediante el algoritmo de Prim. Por ejemplo,

-- λ> prim (grafoDivisibilidad 12)

-- [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),

-- (3,1,3),(2,4,8),(2,2,4),(2,1,2)]

prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

prim g = prim' [n] -- Nodos colocados

ns -- Nodos por colocar

[] -- Árbol de expansión

(aristas g) -- Aristas del grafo

where (n:ns) = nodos g

prim' t [] ae as = ae

prim' t r ae as = prim' (v':t) (delete v' r) (e:ae) as

where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,

u `elem` t,

v `elem` r]

-- 3ª solución (con el algoritmo de Prim con conjuntos)

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

coste3 :: Int -> Int

coste3 n = sum [p | (p,x,y) <- prim2 (grafoDivisibilidad n)]

-- (prim2 g) es el árbol de expansión mínimo del grafo g calculado

-- mediante el algoritmo de Prim. Por ejemplo,

-- λ> prim2 (grafoDivisibilidad 12)

-- [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),

-- (3,1,3),(2,4,8),(2,2,4),(2,1,2)]

prim2 :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

prim2 g = prim2' (S.singleton n) -- Nodos colocados

(S.fromList ns) -- Nodos por colocar

[] -- Árbol de expansión

(aristas g) -- Aristas del grafo

where (n:ns) = nodos g

prim2' t r ae as

| S.null r = ae

| otherwise = prim2' (S.insert v' t)

(S.delete v' r)

(e:ae)

where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,

S.member u t,

S.member v r]

-- 4ª solución

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

coste4 :: Int -> Int

coste4 n = sum [head (primeFactors x) | x <- [2..n]]

-- Comparación de eficiencia

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

-- λ> coste1 400

-- 14923

-- (0.08 secs, 31,336,440 bytes)

-- λ> coste2 400

-- 14923

-- (4.54 secs, 220,745,608 bytes)

-- λ> coste3 400

-- 14923

-- (0.69 secs, 217,031,144 bytes)

-- λ> coste4 400

-- 14923

-- (0.01 secs, 2,192,336 bytes)

-- λ> coste1 2000

-- 284105

-- (2.09 secs, 842,601,904 bytes)

-- λ> coste4 2000

-- 284105

-- (0.02 secs, 14,586,888 bytes)

Clausura respecto de una operación binaria

PorJosé A. Alonso 2-mayo-20189-mayo-2018

Se dice que una operador @ es interno en un conjunto A si al @ sobre elementos de A se obtiene como resultado otro elemento de A. Por ejemplo, la suma es un operador interno en el conjunto de los números naturales pares.

La clausura de un conjunto A con respecto a un operador @ es el menor conjunto B tal que A está contenido en B y el operador @ es interno en el conjunto B. Por ejemplo, la clausura del conjunto {2} con respecto a la suma es el conjunto de los números pares positivos:

   {2, 4, 6, 8, ...} = {2*k | k <- [1..]}

1	{2, 4, 6, 8, ...} = {2*k \| k <- [1..]}

Definir la función

   clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int

1	clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int

tal que (clausuraOperador op xs) es la clausura del conjunto xs con respecto a la operación op. Por ejemplo,

   clausuraOperador gcd (fromList [6,9,10])     ==
      fromList [1,2,3,6,9,10]
   clausuraOperador gcd (fromList [42,70,105])  ==
      fromList [7,14,21,35,42,70,105]
   clausuraOperador lcm (fromList [6,9,10])     ==
      fromList [6,9,10,18,30,90]
   clausuraOperador lcm (fromList [2,3,5,7])    ==
      fromList [2,3,5,6,7,10,14,15,21,30,35,42,70,105,210]

clausuraOperador gcd (fromList [6,9,10]) ==

fromList [1,2,3,6,9,10]

clausuraOperador gcd (fromList [42,70,105]) ==

fromList [7,14,21,35,42,70,105]

clausuraOperador lcm (fromList [6,9,10]) ==

fromList [6,9,10,18,30,90]

clausuraOperador lcm (fromList [2,3,5,7]) ==

fromList [2,3,5,6,7,10,14,15,21,30,35,42,70,105,210]

Soluciones

import Prelude hiding (map)
import Data.Set ( Set
                , elems
                , fromList
                , map
                , notMember
                , union
                , unions
                ) 

-- 1ª definición 
clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int
clausuraOperador op =
  until (\ xs -> null [(x,y) | x <- elems xs,
                               y <- elems xs,
                               notMember (op x y) xs])
        (\ xs -> union xs (fromList [op x y | x <- elems xs,
                                              y <- elems xs]))

-- 2ª definición 
clausuraOperador2 :: (Int -> Int -> Int) -> Set Int -> Set Int
clausuraOperador2 op = until ((==) <*> g) g
  where g ys = unions [map (`op` y) ys | y <- elems ys]

import Prelude hiding (map)

import Data.Set ( Set

, elems

, fromList

, map

, notMember

, union

, unions

)

-- 1ª definición

clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int

clausuraOperador op =

until (\ xs -> null [(x,y) | x <- elems xs,

y <- elems xs,

notMember (op x y) xs])

(\ xs -> union xs (fromList [op x y | x <- elems xs,

y <- elems xs]))

-- 2ª definición

clausuraOperador2 :: (Int -> Int -> Int) -> Set Int -> Set Int

clausuraOperador2 op = until ((==) <*> g) g

where g ys = unions [map (`op` y) ys | y <- elems ys]

Sumas de subconjuntos

PorJosé A. Alonso 24-abril-20181-mayo-2018

Definir la función

   sumasSubconjuntos :: Set Int -> Set Int

1	sumasSubconjuntos :: Set Int -> Set Int

tal que (sumasSubconjuntos xs) es el conjunto de las sumas de cada uno de los subconjuntos de xs. Por ejemplo,

   λ> sumasSubconjuntos (fromList [3,2,5])
   fromList [0,2,3,5,7,8,10]
   λ> length (sumasSubconjuntos (fromList [-40,-39..40]))
   1641

λ> sumasSubconjuntos (fromList [3,2,5])

fromList [0,2,3,5,7,8,10]

λ> length (sumasSubconjuntos (fromList [-40,-39..40]))

1641

Soluciones

import Data.List
import Data.Set ( Set
                , deleteFindMin
                , fromList
                , singleton
                , toList
                )
import qualified Data.Set as S

-- 1ª definición
-- =============

sumasSubconjuntos :: Set Int -> Set Int
sumasSubconjuntos xs =
  fromList (map sum (subsequences (toList xs))) 

-- 2ª definición
-- =============

sumasSubconjuntos2 :: Set Int -> Set Int
sumasSubconjuntos2 =
  fromList . sumasSubconjuntosL . toList  

sumasSubconjuntosL :: [Int] -> [Int]
sumasSubconjuntosL []     = [0]
sumasSubconjuntosL (x:xs) = ys `union` map (+x) ys
  where ys = sumasSubconjuntosL xs

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

sumasSubconjuntos3 :: Set Int -> Set Int
sumasSubconjuntos3 xs
  | S.null xs = singleton 0
  | otherwise = zs `S.union` (S.map (+y) zs)
  where (y,ys) = deleteFindMin xs
        zs     = sumasSubconjuntos2 ys

-- Comparación de eficiencia
-- =========================

--    λ> length (sumasSubconjuntos (fromList [1..22]))
--    254
--    (4.17 secs, 4,574,495,128 bytes)
--    λ> length (sumasSubconjuntos2 (fromList [1..22]))
--    254
--    (0.03 secs, 5,583,200 bytes)
--    λ> length (sumasSubconjuntos3 (fromList [1..22]))
--    254
--    (0.03 secs, 5,461,064 bytes)
--
--    λ> length (sumasSubconjuntos2 (fromList [1..60]))
--    1831
--    (2.75 secs, 611,912,128 bytes)
--    λ> length (sumasSubconjuntos3 (fromList [1..60]))
--    1831
--    (2.81 secs, 610,476,992 bytes)

import Data.List

import Data.Set ( Set

, deleteFindMin

, fromList

, singleton

, toList

)

import qualified Data.Set as S

-- 1ª definición

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

sumasSubconjuntos :: Set Int -> Set Int

sumasSubconjuntos xs =

fromList (map sum (subsequences (toList xs)))

-- 2ª definición

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

sumasSubconjuntos2 :: Set Int -> Set Int

sumasSubconjuntos2 =

fromList . sumasSubconjuntosL . toList

sumasSubconjuntosL :: [Int] -> [Int]

sumasSubconjuntosL [] = [0]

sumasSubconjuntosL (x:xs) = ys `union` map (+x) ys

where ys = sumasSubconjuntosL xs

-- 3ª solución

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

sumasSubconjuntos3 :: Set Int -> Set Int

sumasSubconjuntos3 xs

| S.null xs = singleton 0

| otherwise = zs `S.union` (S.map (+y) zs)

where (y,ys) = deleteFindMin xs

zs = sumasSubconjuntos2 ys

-- Comparación de eficiencia

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

-- λ> length (sumasSubconjuntos (fromList [1..22]))

-- 254

-- (4.17 secs, 4,574,495,128 bytes)

-- λ> length (sumasSubconjuntos2 (fromList [1..22]))

-- 254

-- (0.03 secs, 5,583,200 bytes)

-- λ> length (sumasSubconjuntos3 (fromList [1..22]))

-- 254

-- (0.03 secs, 5,461,064 bytes)

-- λ> length (sumasSubconjuntos2 (fromList [1..60]))

-- 1831

-- (2.75 secs, 611,912,128 bytes)

-- λ> length (sumasSubconjuntos3 (fromList [1..60]))

-- 1831

-- (2.81 secs, 610,476,992 bytes)

Elementos con su doble en el conjunto

PorJosé A. Alonso 17-abril-201724-abril-2017

Definir la función

   conDoble :: [Int] -> [Int]

1	conDoble :: [Int] -> [Int]

tal que (conDoble xs) es la lista de los elementos del conjunto xs (representado como una lista sin elementos repetidos) cuyo doble pertenece a xs. Por ejemplo,

   conDoble [1, 4, 3, 2, 9, 7, 18, 22]  ==  [1,2,9]
   conDoble [2, 4, 8, 10]               ==  [2,4]
   conDoble [7, 5, 11, 13, 1, 3]        ==  []
   length (conDoble4 [1..10^6])         ==  500000

conDoble [1, 4, 3, 2, 9, 7, 18, 22] == [1,2,9]

conDoble [2, 4, 8, 10] == [2,4]

conDoble [7, 5, 11, 13, 1, 3] == []

length (conDoble4 [1..10^6]) == 500000

Referencia: Basado en el problema Doubles de POJ (Peking University Online Judge System).

Soluciones

import Data.List (intersect, sort)
import qualified Data.Set as S

-- 1ª Definición
conDoble :: [Int] -> [Int]
conDoble xs =
  [x | x <- xs, 2 * x `elem` xs]

-- 2ª Definición
conDoble2 :: [Int] -> [Int]
conDoble2 xs = aux (sort xs)
  where aux [] = []
        aux (y:ys) | 2 * y `elem` xs = y : aux ys
                   | otherwise       = aux ys

-- 3ª definición
conDoble3 :: [Int] -> [Int]
conDoble3 xs =
  sort (map (`div` 2) (xs `intersect` (map (*2) xs)))

-- 4ª definición
conDoble4 :: [Int] -> [Int]
conDoble4 xs =
  S.toList (S.map (`div` 2) (ys `S.intersection` (S.map (*2) ys)))
  where ys = S.fromList xs

-- Comparación de eficiencia
--    λ> length (conDoble [1..10^4])
--    5000
--    (3.27 secs, 0 bytes)
--    λ> length (conDoble2 [1..10^4])
--    5000
--    (3.42 secs, 0 bytes)
--    λ> length (conDoble3 [1..10^4])
--    5000
--    (4.78 secs, 0 bytes)
--    λ> length (conDoble4 [1..10^4])
--    5000
--    (0.02 secs, 0 bytes)

import Data.List (intersect, sort)

import qualified Data.Set as S

-- 1ª Definición

conDoble :: [Int] -> [Int]

conDoble xs =

[x | x <- xs, 2 * x `elem` xs]

-- 2ª Definición

conDoble2 :: [Int] -> [Int]

conDoble2 xs = aux (sort xs)

where aux [] = []

aux (y:ys) | 2 * y `elem` xs = y : aux ys

| otherwise = aux ys

-- 3ª definición

conDoble3 :: [Int] -> [Int]

conDoble3 xs =

sort (map (`div` 2) (xs `intersect` (map (*2) xs)))

-- 4ª definición

conDoble4 :: [Int] -> [Int]

conDoble4 xs =

S.toList (S.map (`div` 2) (ys `S.intersection` (S.map (*2) ys)))

where ys = S.fromList xs

-- Comparación de eficiencia

-- λ> length (conDoble [1..10^4])

-- 5000

-- (3.27 secs, 0 bytes)

-- λ> length (conDoble2 [1..10^4])

-- 5000

-- (3.42 secs, 0 bytes)

-- λ> length (conDoble3 [1..10^4])

-- 5000

-- (4.78 secs, 0 bytes)

-- λ> length (conDoble4 [1..10^4])

-- 5000

-- (0.02 secs, 0 bytes)

Elemento ausente

PorJosé A. Alonso 8-marzo-20162-mayo-2016

Sea xs una lista y n su longitud. Se dice que xs es casi completa si sus elementos son los números enteros entre 0 y n excepto uno. Por ejemplo, la lista [3,0,1] es casi completa.

Definir la función

   ausente :: [Integer] -> Integer

1	ausente :: [Integer] -> Integer

tal que (ausente xs) es el único entero (entre 0 y la longitud de xs) que no pertenece a la lista casi completa xs. Por ejemplo,

   ausente [3,0,1]               ==  2
   ausente [1,2,0]               ==  3
   ausente (1+10^7:[0..10^7-1])  ==  10000000

ausente [3,0,1] == 2

ausente [1,2,0] == 3

ausente (1+10^7:[0..10^7-1]) == 10000000

Soluciones

import Data.List (foldl', genericLength)
import Data.Set (fromList, notMember)
    
-- 1ª definición
ausente1 :: [Integer] -> Integer
ausente1 xs =
    head [n | n <- [0..], n `notElem` xs]

-- 2ª definición
ausente2 :: [Integer] -> Integer
ausente2 xs =
    head [n | n <- [0..], n `notMember` ys]
    where ys = fromList xs
         
-- 3ª definición (lineal)
ausente3 :: [Integer] -> Integer
ausente3 xs =
    ((n * (n+1)) `div` 2) - sum xs
    where n = genericLength xs  

-- 4ª definición
ausente4 :: [Integer] -> Integer
ausente4 xs =
    ((n * (n+1)) `div` 2) - foldl' (+) 0 xs
    where n = genericLength xs  

-- Comparación de eficiencia
-- =========================

--    λ> let n = 10^5 in ausente1 (n+1:[0..n-1])
--    100000
--    (68.51 secs, 25,967,840 bytes)
--    λ> let n = 10^5 in ausente2 (n+1:[0..n-1])
--    100000
--    (0.12 secs, 123,488,144 bytes)
--    λ> let n = 10^5 in ausente3 (n+1:[0..n-1])
--    100000
--    (0.07 secs, 30,928,384 bytes)
--    λ> let n = 10^5 in ausente4 (n+1:[0..n-1])
--    100000
--    (0.02 secs, 23,039,904 bytes)
--    
--    λ> let n = 10^7 in ausente2 (n+1:[0..n-1])
--    10000000
--    (14.32 secs, 15,358,509,280 bytes)
--    λ> let n = 10^7 in ausente3 (n+1:[0..n-1])
--    10000000
--    (5.57 secs, 2,670,214,936 bytes)
--    λ> let n = 10^7 in ausente4 (n+1:[0..n-1])
--    10000000
--    (3.36 secs, 2,074,919,184 bytes)

import Data.List (foldl', genericLength)

import Data.Set (fromList, notMember)

-- 1ª definición

ausente1 :: [Integer] -> Integer

ausente1 xs =

head [n | n <- [0..], n `notElem` xs]

-- 2ª definición

ausente2 :: [Integer] -> Integer

ausente2 xs =

head [n | n <- [0..], n `notMember` ys]

where ys = fromList xs

-- 3ª definición (lineal)

ausente3 :: [Integer] -> Integer

ausente3 xs =

((n * (n+1)) `div` 2) - sum xs

where n = genericLength xs

-- 4ª definición

ausente4 :: [Integer] -> Integer

ausente4 xs =

((n * (n+1)) `div` 2) - foldl' (+) 0 xs

where n = genericLength xs

-- Comparación de eficiencia

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

-- λ> let n = 10^5 in ausente1 (n+1:[0..n-1])

-- 100000

-- (68.51 secs, 25,967,840 bytes)

-- λ> let n = 10^5 in ausente2 (n+1:[0..n-1])

-- 100000

-- (0.12 secs, 123,488,144 bytes)

-- λ> let n = 10^5 in ausente3 (n+1:[0..n-1])

-- 100000

-- (0.07 secs, 30,928,384 bytes)

-- λ> let n = 10^5 in ausente4 (n+1:[0..n-1])

-- 100000

-- (0.02 secs, 23,039,904 bytes)

-- λ> let n = 10^7 in ausente2 (n+1:[0..n-1])

-- 10000000

-- (14.32 secs, 15,358,509,280 bytes)

-- λ> let n = 10^7 in ausente3 (n+1:[0..n-1])

-- 10000000

-- (5.57 secs, 2,670,214,936 bytes)

-- λ> let n = 10^7 in ausente4 (n+1:[0..n-1])

-- 10000000

-- (3.36 secs, 2,074,919,184 bytes)

1. El tipo abstracto de datos de los conjuntos

2. Los conjuntos en Haskell

2.1. El tipo abstracto de datos de los conjuntos en Haskell

2.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

2.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

2.4. Implementación de los conjuntos mediante listas ordenadas sin repeticiones

2.5. Implementación de los conjuntos mediante librería

3. Los conjuntos en Python

3.1. El tipo abstracto de los conjuntos en Python

3.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

3.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

3.4. Implementación de los conjuntos mediante listas ordenadas sin duplicados

3.5. Implementación de los conjuntos mediante librería

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico